堆其实也是树结构(或者说基于树结构)，一般可以用堆实现优先队列。
堆可以用于实现其他高层数据结构，比如优先队列
而要实现一个堆，可以借助二叉树，其实现称为: 二叉堆 (使用二叉树表示的堆)。
但是二叉堆，需要满足一些特殊性质:
其一、二叉堆一定是一棵完全二叉树 (完全二叉树可以用数组表示，见下面)
完全二叉树缺失的部分一定是在右下方。(每层一定是从左到右的顺序优先存放)
完全二叉树的结构，可以简单理解成按层安放元素的。(所以数组是不错的底层实现)
其二、父节点一定比子节点大 (针对大顶堆的情况)。
因为二叉堆是完全二叉树，又因为完全二叉树可以用数组的方式实现
(数组编号/索引，正好对应数组的索引/下标)
故而这里完全二叉树的实现就可以绕过二叉树的定义(不用使用 left, right 这样的定义)。
这样表示的好处是可以根据索引来判断父子关系(而不用 left, right关系):
具体关系，可以用数学归纳法证明。
注意一下，0 这个位置要空出来，如果从 0 开始存储的话，规律是这样的:
数组实现:
基本的框架很简单，大致如下:
package maxheap;import array.AdvanceDynamicArray;public class MaxHeap<E extends Comparable<E>> { //用动态数组进行实现 private AdvanceDynamicArray<E> data; //构造函数 public MaxHeap(int capacity) { data = new AdvanceDynamicArray<>(capacity); } public MaxHeap() { data = new AdvanceDynamicArray<>(); } //2个简单的方法 public int getSize() { return data.getSize(); } public boolean isEmpty() { return data.isEmpty(); } //三个辅助函数，根据索引计算父，子存储位置索引 private int parent(int index) { if (index == 0) { //根索引没有父亲 throw new IllegalArgumentException("index 0 没有父亲节点"); } return (index - 1) / 2; } private int leftChild(int index) { return index * 2 1; } private int rightChild(int index) { return index * 2 2; } //存取元素 //外部的 add，对于堆来说就是 sift up (上浮)}但是增删的时候，涉及到重新调整树结构，需要分析一下。
直接说结论: 先添加，后调整。
首先、只是放上去存储，则比较简单，见下图:
树的视角，本层放的下，则放在本层(从左至右的末尾)；本层放不下，那么就放在下一层。
数组的角度，就是放在index末尾，图上就是 index 为 10 的地方。
但是放上去还没有完。
其次、一般还要进行相关的调整，否则不满足二叉堆的第二个性质: 父节点大于子节点。
怎么调整？上浮。
即、只需要调整新节点的父节点，父节点的父节点。。。这一条线上的父节点即可。
(这里最后一次和根节点比较，不用交换)
也就是说，总共过程就两个:
1.末尾添加
2.不停的交换，直到不再大于其父节点
代码如下(就是一个循环替换，比较的过程):
//外部的 add，对于堆来说就是 sift up (上浮) public void add(E e) { data.append(e); //先向数组末尾添加元素 //维护上浮 (队数组进行交换) siftUp(data.getSize()-1); } private void siftUp(int index) { //给定 index 的元素不断和父节点比较 while (index > 0 && data.get(parent(index)).compareTo(data.get(index)) < 0) { //父节点比子节点小，交换 (上浮) data.swap(parent(index), index); //然后再向上找 index = parent(index); } }删除元素(取出元素):
这里的取出元素比较特殊，为了保证堆的高效，一般定义只能取出顶部的元素。
拿走堆顶的元素固然简单，但是剩余的两颗子树就要进行融合，过程就复杂了。
直接说结论: 摘顶之后，先上浮末尾元素，然后调整(下沉)合适位置。
(也就是说，末尾元素替换/覆盖顶部元素，然后 sift down 调整)
举个例子:
替换/覆盖后:
然后，此时看到，并没有归为合适的位置。需要下沉。
如何下沉，每次和它的两个孩子中最大的元素进行交换(因为大顶堆一定是根最大)。
什么时候终止: 当前节点 >= 其两个子节点(前提是其存在子节点)。
(叶子节点，没有子节点，不需要调整了)
简单实现:
public E findMax() { if (isEmpty()) { throw new IllegalArgumentException("这是个空堆"); } return data.get(0); } public E extractMax() { E ret = findMax(); data.swap(0, getSize() - 1); //覆盖堆顶元素 data.pop(); //删除末尾的元素 siftDown(0); //只下沉根元素下浮调整 return ret; } private void siftDown(int index) { //1.叶子节点时不用再交换了(数组越界了，说明其就是叶子节点了) //2.当前节点还是小于 `max(其子节点)` //有左孩子，内部再检查有无有孩子 while (leftChild(index) < getSize()) { //找到孩子中的大的一个 (三个元素中找最大，顺便交换) int maxIndex = leftChild(index); //默认先认为左变大 //如果右孩子存在，那就和右边比一下 int rightIndex = rightChild(index); if (rightIndex < getSize() && data.get(rightIndex).compareTo(data.get(maxIndex)) > 0) { //说明确实右边大 maxIndex = rightIndex; } //此时 maxIndex 就代表了孩子中大的一方的索引 if (data.get(index).compareTo(data.get(maxIndex)) >= 0) { break; //不用比了，已经是大顶堆了 } data.swap(index, maxIndex); index = maxIndex; //接着进行下一轮比较 } }测试一下放入 100 个数据，然后不断的拿出大的来，放入数组，最后检查这个数组是否是降序的。有点类似堆排序 (但借助了额外的数组):
public static void main(String[] args) { int n = 1000000; //100万 MaxHeap<Integer> maxHeap = new MaxHeap<>(); Random random = new Random(); //放入堆中 (需要不断的 sift up) for(int i = 0; i < n; i ) { maxHeap.add(random.nextInt(Integer.MAX_VALUE)); } //然后取出来放入 arr 中 int[] arr = new int[n]; for(int i = 0; i< n; i ) { arr[i] = maxHeap.extractMax(); } //检查一下这个 arr 是否是降序的 for(int i = 1; i< n; i ) { if(arr[i-1] < arr[i]) { //说明不是降序的，堆实现有问题 throw new IllegalArgumentException("Error"); } } //全部检查完毕还没有异常，就说明 OK System.out.println("OK"); }主要分析 add 和 extractMax, 其实还是 O(logn)，因为交换的层级是高度 h，即 logn(因为是完全二叉树)。
但是构建或者说存储一棵大顶堆，复杂度是 O(nlogn)。
上面已经说了，构建一个大顶堆，需要 O(nlogn)，如何优化？
heapify优化 (任意数组整理成堆的存储)。
直接说结论，用 sift down 替代 add 构建大顶堆
上面的 add 方法，慢慢构建一个大顶堆，步骤如下:
添加到末尾
慢慢 sift up 调整
这里有一个非常重要的默认思想，那就是，一个元素一个元素的放入数组，慢慢构建大顶堆。
如果，现在假定存储的数组就是一棵完全二叉树(意思是，按照完全二叉树那样子，进行编号)，举个例子，见下图:
(只是完全二叉树，但并不能称为堆)
然后叶子节点先不管(因为叶子节点没有孩子，而后面要进行 sift down 下沉操作，需要孩子节点)，对所有的非叶子节点进行 sift down。从第一个非叶子节点向根节点走(也就是数组末端开始)，图:
数组最大索引处可以定位第一个非叶子节点(getSize()-1)的 parent
最后一层的叶子节点，可以忽略 (这样至少减少了一半的工作量) --- 这是关键
siftDown方法里面就包含了对叶子的过滤，即只对非叶子节点进行siftDown
这么一来其实就很简单了，大概的复杂度也就是 O(n)，比一个个添加(O(n*logN))的好处在于，上来就抛弃了所有的叶子节点，这个将近减少了一半的工作量。(实际减少的数目可以根据最大索引计算)
简单实现如下(对着数组看即可):
public MaxHeap(E[] arr) { data = new AdvanceDynamicArray<>(arr); //把数组折腾成大顶堆 for (int i = parent(getSize() - 1); i >= 0; i--) { siftDown(i); } }其实在大数量级下， n 和 nlongn 近乎一致，相差不了太多。(虽然是不同的数量级)
(再次注意: 这里的 heapify 的时间复杂度是 O(n) 级别。)
构建优先队列不一定要用堆，但是底层用堆实现效率比较高
普通队列: 先进先出，后进后出
出队顺序和入队顺序无关，只和优先级有关(出队的时候要看)
随时根据新入队的元素调整优先级:
优先级的意义可以自己定义，比如每次值最大的元素先出队
优先级，一般都是作用于出队上
因为优先队列也是队列，所以接口还是 Queue，即:
interface Queue<E> { void enqueue(E); E dequeue(); //拿到优先级最高的元素 E getFront(); //拿到优先级最高的元素 int getSize(); boolean isEmpty(); }用线性结构，此时不论是有序线性结构还是无序线性结构，入队和出队总是保持在 O(1),O(n); 如果用 BST 实现的话，它最好的情况保持在 O(logn)，但最坏的情况可能会退化到 O(n)。
堆可以保证，在最差的情况都是 O(logn) 水平。
也就是说，在 PrioryQueue 内部封装一个堆即可。(堆兼容所有的队列接口)
代码试下如下:
package maxheap;import queque.Queue;public class PriorityQueue<E extends Comparable<E>> implements Queue<E> { //内部成员 private MaxHeap<E> maxHeap; //构造函数 public PriorityQueue() { maxHeap = new MaxHeap<>(); } @Override public boolean isEmpty() { return maxHeap.isEmpty(); } @Override public int getSize() { return maxHeap.getSize(); } @Override public E dequeue() { return maxHeap.extractMax(); // 已经对空的情况做了处理 } @Override public E getFront() { //获取优先级最大的元素 return maxHeap.findMax(); //已经对空的情况作了处理 } @Override public void enqueue(E o) { maxHeap.add(o); }}重新整理一下，Java中的优先队列
Java 的 PriorityQueue 是最小堆(顶部始终存储的是优先级最低的)。
但是小顶堆是默认存储优先级最低的元素，但优先级是自己定义的，所以当你反写 compareTo 或者比较器时，那么即便是小顶堆，那么实际上存储还是大顶堆的方式。(堆顶拿到的也就是优先级最大的元素)
这里应用就太多了，什么N个元素中选出前M个，什么出现频率最多的x个等，再就是要求构建堆的时候采用 heapify 的方式(表现在要求复杂度优于O(nlogn)) 等，大多都在此范畴内。
比如 Leetcode 347 就可以用 java.util.PriorityQueue，参考代码:
import java.util.TreeMap;import java.util.PriorityQueue;import java.util.LinkedList;//import java.util.List;class Solution { //放入 PriorityQueue 中的元素 private class Freq implements Comparable<Freq> { public int e, freq; //构造器 public Freq(int key, int freq) { this.e = key; this.freq = freq; } //由于 java.util.PriorityQueue 是小顶堆，正常些比较逻辑 @Override public int compareTo(Freq another) { return this.freq - another.freq; } } public List<Integer> topKFrequent(int[] nums, int k) { //首先把数组放入 map 统计频次 TreeMap<Integer, Integer> map = new TreeMap<>(); for(int num : nums) { if(map.containsKey(num)) { map.put(num, map.get(num) 1); } else { map.put(num, 1); } } PriorityQueue<Freq> queue = new PriorityQueue<>(); //不使用比较器 //遍历 map 放入 PriorityQueue 中 for(int key : map.keySet()) { //前 k - 1 个元素直接放进去 if(queue.size() < k) { queue.add(new Freq(key, map.get(key))); } else if(map.get(key) > queue.peek().freq) { //替换最小的 queue.remove(); queue.add(new Freq(key, map.get(key))); } } //把 queue 中的结果整理出来，放入结果集中 LinkedList<Integer> res = new LinkedList<>(); while(!queue.isEmpty()) { res.addFirst(queue.remove().e); //因为现出来的是频率相对低的 } return res; }}然后，代码优化以下(采用传入比较器，Lambda表达式代替匿名类捕获外部map):
可以捕获外部 map，所以逻辑自然简洁了(但是不容易想到)
不难看出，小顶堆用的还是蛮多的。
想让树的层次变少，那么久使用
K叉堆吧
但是 K 叉堆(K可以取值3以上的值)需要考虑的孩子多余两个，此时 sift up 或者 sift down 需要的比较孩子，交换根与孩子的策略就需要重写一下。
也就是说，调整的时候需要考虑的逻辑会多一些。
其他堆: 比如索引堆(可以操作除堆顶元素之外的元素)，二项堆，斐波那契堆。
(一般相关语言实现的堆，就是最常用最常见，最有用的堆)
对于堆的认识，我也仅停留在最基本的堆。
不多言了，还是把代码仓库贴一下吧 gayhub。
联系客服
