堆(heap)又被为优先队列(priority queue)。尽管名为优先队列，但堆并不是队列。

　　因为队列中允许的操作是先进先出（FIFO），在队尾插入元素，在队头取出元素。

　　而堆虽然在堆底插入元素，在堆顶取出元素，但是堆中元素的排列不是按照到来的先后顺序，而是按照一定的优先顺序排列的。

　　本文通过堆的实现、最小堆（最大堆）、堆的时间复杂度、优先队列的实现、堆排序来介绍「 堆 」。

　　堆的实现

　　堆的一个经典的实现是完全二叉树(complete binary tree)，这样实现的堆称为二叉堆(binary heap)。

　　这里来说明一下满二叉树的概念与完全二叉树的概念。

　　满二叉树：除了叶子节点，所有的节点的左右孩子都不为空，就是一棵满二叉树，如下图。

　　可以看出：满二叉树所有的节点都拥有左孩子，又拥有右孩子。

　　完全二叉树：不一定是一个满二叉树，但它不满的那部分一定在右下侧，如下图

　　堆的特性：

　　必须是完全二叉树任一结点的值是其子树所有结点的最大值或最小值最大值时，称为“最大堆”，也称大顶堆；最小值时，称为“最小堆”，也称小顶堆。

　　堆的基础实现

　　只要谨记堆的定义特性，实现起来其实是很容易的。

　　特性1. 维持完全二叉树 特性2. 子类数字总是大于父类数字 1public class MinHeap <E exts Comparable<E>> { 2 private Array<E> data; 3 4 public MinHeap(int capacity){ 5 data = new Array<>(capacity); 6 } 7 8 public MinHeap(){ 9 data = new Array<>();10 }1112 // 返回堆中的元素个数13 public int size(){14 return data.getSize();15 }1617 // 返回一个布尔值, 表示堆中是否为空18 public boolean isEmpty(){19 return data.isEmpty();20 }2122 // 返回完全二叉树的数组表示中，一个索引所表示的元素的父亲节点的索引23 private int parent(int index){24 return (index - 1) / 2;25 }2627 // 返回完全二叉树的数组表示中，一个索引所表示的元素的左孩子节点的索引28 private int leftChild(int index){29 return index * 2 + 1;30 }3132 // 返回完全二叉树的数组表示中，一个索引所表示的元素的右孩子节点的索引33 private int rightChild(int index){34 return index * 2 + 2;35 }36}最小堆的插入（ADD）

　　假设现有元素 5 需要插入，为了维持完全二叉树的特性，新插入的元素一定是放在结点 6 的右子树；同时为了满足任一结点的值要小于左右子树的值这一特性，新插入的元素要和其父结点作比较，如果比父结点小，就要把父结点拉下来顶替当前结点的位置，自己则依次不断向上寻找，找到比自己大的父结点就拉下来，直到没有符合条件的值为止。

　　动画讲解：

　　在这里先将元素 5 插入到末尾，即放在结点 6 的右子树。然后与父类比较， 6 > 5 ，父类数字大于子类数字，子类与父类交换。重复此操作，直到不发生替换。Show me the code：

　　添加一个辅助函数，用来交换传入的索引两个位置的元素值

　　 1/** 2 * 交换传入的索引两个位置的元素值 3 * 4 * @param i 5 * @param j 6 */ 7 public void swap(int i, int j) { 8 if (i < 0

　　 i >= size

　　 j < 0

　　 j >= size) 9 throw new IllegalArgumentException("Index is illegal.");1011 E temp = data[i];12 data[i] = data[j];13 data[j] = temp;14 }数组中添加交换两元素位置的方法，注意下面代码中注释的描述特性位置。

　　 1 /** 2 * 堆中添加元素方法。 3 * 4 * @param e 5 */ 6 public void add(E e) { 7 //特性1：新插入的元素首先放在数组最后，保持完全二叉树的特性 8 data.addLast(e); 9 siftUp(data.getSize() - 1);10 }1112 /**13 * index 为i位置元素上浮。14 *15 * @param i16 */17 private void siftUp(int i) {18 //特性2：比较插入值和其父结点的大小关系，小于父结点则用父结点替换当前值，index位置上升为父结点19 // 当上浮元素大于父亲，继续上浮。并且不能上浮到0之上20 // 直到i 等于 0 或 比 父亲节点小了。21 while (i > 0 && data.get(i).compareTo(data.get(parent(i))) > 0) {22 // 数组Array中添加方法swap23 data.swap(i, parent(i));24 i = parent(i); // 这句话让i来到新的位置，使得循环可以查看新的位置是否还要大。25 }26 }最小堆的删除（DELETE）

　　核心点：将最后一个元素填充到堆顶，然后不断的下沉这个元素。

　　假设要从节点 1 ，也可以称为取出节点 1 ，为了维持完全二叉树的特性 ，我们将最后一个元素 6 去替代这个 1 ；然后比较 1 和其子树的大小关系，如果比左右子树大（如果存在的话），就要从左右子树中找一个较小的值替换它，而它能自己就要跑到对应子树的位置，再次循环这种操作，直到没有子树比它小。

　　通过这样的操作，堆依然是堆，总结一下：

　　找到要删除的节点（取出的节点）在数组中的位置用数组中最后一个元素替代这个位置的元素当前位置和其左右子树比较，保证符合最小堆的节点间规则删除最后一个元素Show me the code：

　　 1 public E findMin() { 2 return data.get(0); 3 } 4 5 public E extractMin() { 6 7 E ret = findMin(); 8 9 data.swap(0, data.getSize() - 1); // 0位置元素和最后一个元素互换。10 data.removeLast(); // 删除此时的最后一个元素(最小值)11 siftDown(0); // 对于0处进行siftDown操作1213 return ret;14 }1516 /**17 * k位置元素下移18 *19 * @param k20 */21 private void siftDown(int k) {2223 while(leftChild(k) < data.getSize()){24 int j = leftChild(k); // 在此轮循环中,data[k]和data[j]交换位置25 if( j + 1 < data.getSize() &&26 data.get(j + 1).compareTo(data.get(j)) < 0 )27 j ++;28 // data[j] 是 leftChild 和 rightChild 中的最小值2930 if(data.get(k).compareTo(data.get(j)) >= 0 )31 break;3233 data.swap(k, j);34 k = j;35 }36 }时间复杂度

　　对于有 n 个节点的堆来说，其高度 d = log2n + 1。 根为第 0 层，则第 i 层结点个数为 2i，

　　考虑一个元素在堆中向下移动的距离。

　　大约一半的结点深度为 d-1 ，不移动(叶)。四分之一的结点深度为 d-2 ，而它们至多能向下移动一层。树中每向上一层，结点的数目为前一层的一半，而子树高度加一堆有logn层深，所以插入删除的平均时间和最差时间都是O(logN)

　　优先队列（priority_queue）

　　普通队列是一种先进先出的数据结构，先放进队列的元素取值时优先被取出来。而优先队列是一种具有最高优先级元素先出的数据结构，比如每次取值都取最大的元素。

　　优先队列下面的操作：

　　a. 找出优先级最高的元素(最大或最小元素)；b. 删除一个具有最高优先级的元素；c. 添加一个元素到集合中。代码实现

　　 1public class PriorityQueue<E exts Comparable<E>> implements Queue<E> { 2 3 private MaxHeap<E> maxHeap; 4 5 public PriorityQueue(){ 6 maxHeap = new MaxHeap<>(); 7 } 8 9 @Override10 public int getSize(){11 return maxHeap.size();12 }1314 @Override15 public boolean isEmpty(){16 return maxHeap.isEmpty();17 }1819 @Override20 public E getFront(){21 return maxHeap.findMax();22 }2324 @Override25 public void enqueue(E e){26 maxHeap.add(e);27 }2829 @Override30 public E dequeue(){31 return maxHeap.extractMax();32 }33}堆排序

　　理解了优先队列，堆排序的逻辑十分简单。

　　第一步：让数组形成堆有序状态；

　　第二步：把堆顶的元素放到数组最末尾，末尾的放到堆顶，在剩下的元素中下沉到正确位置，重复操作即可。

　　堆排序动画

　　End

　　关于本号

　　作者程序员小吴，哈工大学渣，目前正在学算法，开源项目 「 LeetCodeAnimation 」5100star，GitHub Tring 榜 连续半个月登顶。欢迎大家我的微信：五分钟学算法，一起学习，一起进步！