堆是一种特殊的基于树的数据结构，其中树是一个完整的二叉树。一般来说，堆可以有两种类型:
- Max-Heap 大顶堆: 在Max-Heap中，根节点上的键必须是所有子节点上的键中最大的。同样的属性必须递归地适用于该二叉树中的所有子树。
- Min-Heap 小顶堆: 在Min-Heap中，根节点上的键必须是它所有子节点上的键中最小的。同样的属性必须递归地适用于该二叉树中的所有子树
堆满足如下性质：参见heap-data-structure
- 堆是一棵完全二叉树, 也被称为二叉堆(binary heap)，一般说的堆就是指二叉堆，实际上还有左倾堆、右倾堆等，它们不要求是完全二叉树。
- 堆中任意节点的值总是不大于/不小于其子节点的值；
- 堆常被用于实现“优先队列”（PriorityQueue）。优先队列可以自由添加数据
- 在guava包中有 双向优先级队列(MinMaxPriorityQueue)，它提供了一种常数时间复杂度的方式访问其最小和最大元素的数据结构。作为一个queue，它在功能上和PriorityQueue一样
- PriorityQueue（优先队列）本质上是一个最小堆，不同于先进先出（FIFO）队列，每次从队列中取出的是具有最高优先权的元素（指定比较器）。
- 实现堆排序
因为堆作为一颗完全二叉树
根据二叉树的性质，完全二叉树能够完美的映射到数组结构中去：如果节点从0开始编号，并把节点映射到数组中之后，则节点之间满足如下关系：
- 大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]（0<=i<=n/2 -1）如 9,8,7,6,5,4,3,2,1
- 小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]（0<=i<=n/2 -1）如 1,2,3,4,5,6,7,8,9
n为数组长度，n/2 -1实际上表示数组从头到尾最后一个非叶子结点的索引位置。
因此常常使用数组来实现堆结构，比如Java中的PriorityQueue，就是采用数组实现的二叉堆。
由于堆算作一个偏序（只有父节点和子节点的大小关系，没有两个子节点之间的大小关系），因此同一批元素采用不同算法构建成的堆在数组中的实际存储顺序是不一定相同的，并且堆排序也是一种不稳定的排序算法。
- 在二叉排序树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大
- 二叉排序树一般使用链表实现，占用的内存空间比它们存储的数据要多。必须为节点对象以及左/右子节点指针分配额外的内存。堆可以使用数组来存放数据，节点对象以及左/右子节点存在天然的关系，使用索引即可到达，节省内存。
- 由于二叉排序树中节点大小的性质，在二叉排序树中查找会很快，查找过程类似与有序数组的二分查找，并且查找次数不会超过树的深度，但是在堆中查找会比较慢。使用二叉排序树的目的是为了方便查找节点，使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关排序、插入、删除操作。
import java.util.Arrays; import java.util.Collection; import java.util.Comparator; public class MaxBinaryTreeHeap小顶堆实现{ private Object[] heap; private int size; private static int capacity = 16; private final Comparator cmp; private int compare(E e1, E e2) { if (cmp != null) { return cmp.compare(e1, e2); } else { return ((Comparable ) e1).compareTo(e2); } } public MaxBinaryTreeHeap() { this(capacity, null); } public MaxBinaryTreeHeap(int initCapacity) { this(initCapacity, null); } public MaxBinaryTreeHeap(Comparator comparator) { this(capacity, comparator); } public MaxBinaryTreeHeap(int initCapacity, Comparator comparator) { if (initCapacity < 1) { throw new IllegalArgumentException(); } capacity = initCapacity; this.heap = new Object[initCapacity]; cmp = comparator; } public MaxBinaryTreeHeap(Collection heap) { this(heap, null); } public MaxBinaryTreeHeap(Collection heap, Comparator comparator) { Object[] array = heap.toArray(); this.cmp = comparator; if (array.getClass() != Object[].class) { array = Arrays.copyOf(array, array.length, Object[].class); } for (Object o : array) { if (o == null) { throw new NullPointerException(); } } this.heap = array; this.size = array.length; buildHeap(this.heap); } private void buildHeap(Object[] heap) { for (int i = heap.length / 2 - 1; i >= 0; i--) { buildHeap(heap, i, heap.length); } } private void buildHeap(Object[] arr, int i, int length) { //先把当前非叶子节点元素取出来，因为当前元素可能要一直移动 Object temp; //节点的子节点的索引 int childIndex; for (temp = arr[i]; (childIndex = 2 * i + 1) < length; i = childIndex) { //childIndex + 1 < length 说明该节点具有右子节点,并且如果右子节点的值大于左子节点，那么childIndex自增1，即childIndex指向右子节点索引 if (childIndex + 1 < length && compare((E) arr[childIndex], (E) arr[childIndex + 1]) < 0) { childIndex++; } //如果发现最大子节点(左、右子节点)大于根节点，为了满足大顶堆根节点的值大于子节点，需要进行值的交换 //如果子节点更换了，那么，以子节点为根的子树会受到影响,所以，交换之后继续循环对子节点所在的树进行判断 if (compare((E) arr[childIndex], (E) temp) > 0) { swap(arr, i, childIndex); } else { //走到这里,说明父节点大于最大的子节点，满足大顶堆的条件，直接终止循环 break; } } } public Object[] heapSort() { //使用大顶堆的副本进行排序输出 Object[] arr = Arrays.copyOf(heap, size); for (int i = size - 1; i > 0; i--) { //交换堆顶与堆尾元素顺序 swap(arr, 0, i); //重新构建大顶堆 buildHeap(arr, 0, i); } return arr; } public void add(E e) { if (e == null) { throw new NullPointerException(); } if (heap.length == size) { resize(); } addNode(e, size++); } private void addNode(E e, int start) { //获取size处节点的父节点索引 int parent = (start - 1) / 2; while (start > 0) { //判断父节点和新子节点的大小,如果父节点小于等于新子节点,那么符合小顶堆的要求,重构结束,该start就是子节点插入的位置 if (compare((E) heap[parent], e) >= 0) { break; } else { //否则,将父节点的值移动到子节点的位置处 heap[start] = heap[parent]; //将start的索引值变成父节点的索引值 start = parent; //重新计算父节点的索引,不断循环,直到找到父节点值小于等于新子节点值的索引 parent = (start - 1) / 2; } } //在合适的位置插入新节点值 heap[start] = e; } private void resize() { heap = Arrays.copyOf(heap, heap.length * 2, Object[].class); } private static void swap(Object[] arr, int a, int b) { Object temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } public boolean remove(E e) { int eIndex = -1; for (int i = 0; i < size; i++) { //这里是通过compare来查找元素是否相同的 if (compare((E) heap[i], e) == 0) { eIndex = i; } } if (eIndex == -1) { return false; } //原尾部元素x E x = (E) heap[size - 1]; //交换查找到的元素与堆尾元素的位置 swap(heap, eIndex, size - 1); //移除堆尾元素 heap[size--] = null; //从eIndex开始向下重新构建大顶堆 buildHeap(heap, eIndex, size); //构建之后如果eIndex位置的元素就是x，说明没有调整堆结构，那么将该位置的元素看成新插入的元素，需要向上构建大顶堆 if (heap[eIndex] == x) { //调用addNode从eIndex开始向上重构大顶堆 addNode(x, eIndex); } return true; } public int size() { return size; } @Override public String toString() { StringBuilder stringBuilder = new StringBuilder(); stringBuilder.append("["); for (int i = 0; i < size; i++) { stringBuilder.append(heap[i]); if (i != size - 1) { stringBuilder.append(","); } } stringBuilder.append("]"); return stringBuilder.toString(); } }
请参考：PriorityQueue类的实现
测试代码public static void main(String[] args) {
Integer[] arr = new Integer[]{9, 8, 5, 4, 5, 2, 1, 3, 7};
//构建大顶堆
MaxBinaryTreeHeap maxBinaryHeap = new MaxBinaryTreeHeap<>(Arrays.asList(arr));
//输出大顶堆
System.out.println(maxBinaryHeap);
//添加节点,并且重构大顶堆
maxBinaryHeap.add(11);
maxBinaryHeap.add(77);
//输出大顶堆
System.out.println(maxBinaryHeap);
//删除节点,并且重构大顶堆
//删除失败
System.out.println(maxBinaryHeap.remove(79));
//删除成功
System.out.println(maxBinaryHeap.remove(7));
//输出大顶堆
System.out.println(maxBinaryHeap);
//大顶堆排序(顺序排序)
System.out.println(Arrays.toString(maxBinaryHeap.heapSort()));
//输出大顶堆
System.out.println(maxBinaryHeap);
}
输出结果如下：
[9,8,5,7,5,2,1,3,4]
[77,11,5,7,9,2,1,3,4,5,8]
false
true
[77,11,5,8,9,2,1,3,4,5]
[1, 2, 3, 4, 5, 5, 8, 9, 11, 77]
[77,11,5,8,9,2,1,3,4,5]
10种常见排序算法原理详解以及Java代码的完全实现
heap-data-structure
