前言
本文主要介绍了堆和比较器：堆包括大根堆和小根堆；比较器的实质就是重载比较运算符，可以用于普通方式的排序和自定义的排序。
1.堆
上面层的节点都是满的，最下层要么是满的，要么左边节点是满的且连续的。
数组也能实现完全二叉树：
有的实现中，0位置不用，从1开始：
这样做的原因是可以直接使用位运算代替算术运算，提高运算速度。
堆结构：
1）堆结构就是用数组实现的完全二叉树结构；
2）完全二叉树中如果每棵子树的最大值都在顶部就是大根堆；
3）完全二叉树中如果每棵子树的最小值都在顶部就是小根堆；
4）堆结构的heapInsert与heapify操作；
5）堆结构的增大和减少；
6）优先级队列结构，就是堆结构。
堆是在完全二叉树的基础上实现的，分为大根堆和小根堆：
大根堆：
每一个子树的最大值都是该子树头节点的值。
举例如下：
小根堆：
每一个子树的最小值都是该子树头节点的值。
将给定的一系列数组成为大根堆。
图示如下：
实现大根堆如下：
package heap04; /** * @author Corley * @date 2021/10/12 20:16 * @description LeetCodeAlgorithmZuo-heap04 */ public class Heap { class MaxHeap { private int[] heap; private final int limit; private int heapSize; MaxHeap(int limit) { heap = new int[limit]; this.limit = limit; heapSize = 0; } /* 加入新元素 */ public void push(int value) { if (heapSize == limit) { throw new RuntimeException("Heap is full!"); } heap[heapSize++] = value; heapInsert(heap, heapSize); } /* 新加进来的数，现在停在了index位置，请依次往上移动 */ private void heapInsert(int[] arr, int index) { while (arr[index] > arr[(index - 1) / 2]) { swap(arr, index, (index - 1) / 2); } } public void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } }
现在分析加入元素时调整堆结构的代价：
堆的深度为LogN级别；
所以加入新元素时调整为二根堆的代价也为LogN。
实现找到大根堆中的最大值，并删除最大值，然后再调整为大根堆。
示意如下：
实现如下：
/* * 实现找到大根堆中的最大值，并删除最大值，然后再调整为大根堆 * */ public int pop() { int ans = heap[0]; swap(heap, 0, --heapSize); heapify(heap, 0, heapSize); return ans; } /* 从index位置，往下看，不断的下沉 停：较大的子节点都不再比index位置的数大；已经没子节点 */ public void heapify(int[] arr, int index, int heapSize) { int left = 2 * index + 1; while (left < heapSize) { int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left; largest = arr[largest] > arr[index] ? largest : index; if (largest == index) { break; } swap(arr, largest, index); index = largest; left = 2 * index + 1; } }
显然，heapify方法的复杂度也是LogN。
