堆（heap）
什么是堆？ 堆是满足下面两个条件的一种二叉树
- 它是一棵完全二叉树；
- 堆中每个节点的值都必须大于等于（大根堆）或者小于等于（小根堆）其子树中每个节点的值。
完全二叉树是指除了最后一层，其他层的节点个数都是满的，最后一层的节点都靠左排列
我们看几个例图
image.png
其中1,2是大根堆，3,4是小根堆。从图中我们也可以看出来，同一组数据排成的堆可能有多种形式。
存储
因为堆是一棵完全二叉树，所以我们通常使用数组来存储它。节约空间也好定位父节点或者子节点。为了计算子节点方便，通常从下标为1的位置开始存储，如果i是父节点那么2i， 2i + 1就是子节点。
如下图所示
image.png
添加元素
添加元素通常是在数组的最末尾添加，这样添加之后数组仍然满足堆的特性1，但是不满足特性2了，所以必须进行调整，我们将这个调整过程称为heapify.
方法很简单： 就是顺着节点所在的路径，往上对比，需要换位置的就交换
image.png
下面是java代码实现：
public void insert(int value){
if(count >= capacity) return ;
data[++count] = value;
int current = count;
int parentIndex = count/2;
while(parentIndex > 0 && data[parentIndex] < value){
data[current] = data[parentIndex];
data[parentIndex] = value;
current = parentIndex;
parentIndex = current/2;
}
}
删除堆顶元素
删除堆顶元素的方法是，将堆顶元素删除，然后将最后一个元素放到堆顶，这样就保证了特性1，然后再按住从上往下的顺序比较交换元素，以满足特性2
image.png
java代码实现
public void removeMax(){
if(count <= 0) return;
data[1] = data[count--];
int current = 1;
while(true){
int maxIndex = current;
if(current *2 <= count && data[current *2] > data[maxIndex]) {
maxIndex = current * 2;
}
if(current *2 + 1 <= count && data[current * 2 + 1] > data[maxIndex]) {
maxIndex = current * 2 + 1;
}
if(maxIndex == current) break;
int temp = data[current];
data[current] = data[maxIndex];
data[maxIndex] = temp;
current = maxIndex;
}
}
有了上述了解之后，接下来我们看看堆最重要的一个应用，堆排序
堆排序可以分成两步：
1. 建堆
我们先来分析一下原始数据，刚开始数据是无序的，但其中叶子节点其实已经是“有序”的了，即其满足堆的定义，大于它所有的子节点，因为它们没有子节点；所有我们只需要对非叶子节点进行排序即可，这里可以宣传从上往下heapify的方法来建堆
image.png
java代码实现如下：
public static void buildHeap(int[] array, int n){
if(array == null || array.length < 2) return;
for(int i = n/2; i >= 1; i--){
heapify(array, n, i);
}
}
private static void heapify(int[] array, int n, int i) {
while(true){
int maxIndex = i;
if(i * 2 <= n && array[i*2] > array[maxIndex]) {
maxIndex = i * 2;
}
if(i*2 + 1 <= n && array[i*2+1] > array[maxIndex]){
maxIndex = i * 2 + 1;
}
if(maxIndex == i) break;
swap(array, i, maxIndex);
i = maxIndex;
}
}
private static void swap(int[] array, int i, int maxIndex) {
int temp = array[i];
array[i] = array[maxIndex];
array[maxIndex] = temp;
}
2. 排序
堆建成之后，我们能确定的是第一个元素就是最大元素了（或者最小元素），其他元素的顺序无法确定，所以我们此时将第一个元素和最好一个个元素互换，堆大小减一，此时给我没删除操作类似了，只需要再次堆话就可以得到第二大数据，依次类推可以对整个数组排序
image.png
java 代码实现
public static void sort(int[] array, int n){
buildHeap(array, n);
if(array == null || array.length < 2) return;
while(n > 1){
swap(array, 1, n--);
heapify(array, n, 1);
}
}
堆的应用场景
- 优先级队列
java 中的PriorityQueue 就是用堆实现的 - 取数组中TopK的数据
假如我们要取一组数据中的top 5,那么我们只需要维护一个5个元素大小的小根堆，当有数据加进来时只需要和堆顶元素做比较，如果比堆顶元素小直接忽略，如果比堆顶元素大，则置换调堆顶元素，然后做heapify.这样每次加数据都只需要和堆顶元素做比较 -
利用堆求中位数
对应静态数据我们可以直接用快排找；对于动态变化的数据，用堆就比较合适了，这里需要维护两个堆，一个大根堆，一个小根堆；大根堆里面存储前一半小数据，小根堆里面存储后一半大数据。每次插入数据的时候和大根堆堆顶元素比较，小于则放入大根堆，大于则放入小根堆，放完之后为了保证大根堆的堆顶就是中位数，我们可能需要在两个堆之间移动一下数据；
image.png
