一.概念
二插堆，是一种数据结构。用于解决任务优先级队列的性能问题。比如任务有优先级，我每次处理最高优先级的任务，每次会产生新的任务加入到队列中，并且每次取出最高优先级的任务去处理，并从队列中删除。我可以用一个有序动态数组去解决，插入每次需要 O(n)的时间，查询和删除都是O(1)。那么有没有更好的结构，优于这个效率，BBST是一个，但数据结构实现太复杂。有一个很好的简单的数据结构，就是二插堆，可以实现 插入、删除和获取最大值都是O(logn)。
二插堆在逻辑上是一个完全二叉树。在物理上是用数组来存储。结构的关系见下图：
根据图的观察，节点的序号具有如下规律：(假设当前节点序号为i,数组长度为n)
1.左子节点为 2i + 1，右子节点为 2i+2。
(如果序号超出数组长度n，则不存在相应左右子节点)
2.最后一个子节点(即非叶子节点) 为 n/2
3.父节点为 (i-1)/2
二插堆的特点：任何子节点的值都小于或等于父节点，最大值是根节点。
二.实现
实现涉及到三个关键的方法：
1.初始化，也叫原地建堆，一般有两种方案，从下至上的下滤和从上至下的上滤。一般选取前者。
(从一个任意数组转为满足二插堆性质的数组)
2.插入，要求从最后一个叶子结点下一个节点插入
3.删除，删除根节点
1.插入
插入核心思路是，插入到最后一个叶子节点。然后从此节点开始，找父节点，如果父节点大于子节点，则停止，否则交互父子节点，从父节点位置继续上滤。
想象下：上滤就是把底层的大的值，冒泡到上层，直到合适的位置，保证上一层的子节点严格大于下一层的子节点即可。
public void add(E element) {
elementNotNullCheck(element);
ensureCapacity(size+1);
elements[size++] = element;
siftUp(size-1);
}
// 让index的元素上滤
private void siftUp(int index){
E e = elements[index];
while (index > 0){
int pindex = (index - 1) >> 1;
E p = elements[pindex];
if(compare(e,p) <= 0) return;
E tpm = elements[index];
elements[index] = elements[pindex];
elements[pindex] = tpm;
index = pindex;
}
}
2.删除
删除即是删除堆顶，把最后一个元素放到根节点，然后堆长度-1，之后从根节点开始下滤。
所谓下滤，就是找到当前节点的左右子节点。如果有比当前节点大的，则找到左右子节点中最大的，和当前节点交互，并且从这个交换的子节点继续向下这一过程，直到子节点成为叶子节点为止。如果没有比当前节点大的，则停止，这就是合适的下滤位置了。这个过程保证了二插堆的性质，保证了所有高层的子节点都大于底一层的，且顶部是最大的。可以想想下，下滤就是把顶部新节点流动到合适的位置。
public E remove() {
emptyCheck();
E root = elements[0];
elements[0] = elements[size - 1];
elements[size-1] = null;
size--;
siftDown(0);
return root;
}
private void siftDown(int index){
E element = elements[index];
int half = size >> 1;
while ( index < half){// 第一个叶子节点索引=非叶子节点数量
// 找出左右子树节点中较大的一个，并上移。
int childIndex = 2*index + 1;
E child = elements[childIndex];
int rightIndex = childIndex + 1;
// System.out.printf("比较元素"+childIndex+"和"+rightIndex);
if(rightIndex < size && compare(elements[rightIndex],child) > 0){
childIndex = rightIndex;
child = elements[rightIndex];
}
if(compare(element,child) >= 0) break;
elements[index] = child;
index = childIndex;
}
elements[index] = element;
}
3.原地建堆
原地建堆，就是从最后一个子节点(非叶子几点)向根节点方向，逐渐下滤，下滤可保证每个子树是二叉堆，从而保证树增大的过程中，始终满足二插堆性质。
public BinartHeap(E[] elements,Comparator<E> comparator){
this.comparator = comparator;
if(elements == null || elements.length == 0){
this.elements = (E[])new Object[DEFAULT_CAPACITY];
}else{
size = elements.length;
int capacity = Math.max(elements.length,DEFAULT_CAPACITY);
this.elements = (E[]) new Object[capacity];
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[i];
}
heapify();
}
}
// 批量建堆
private void heapify(){
for (int i = (size >> 1) - 1; i >=0; i--) {
siftDown(i);
}
}
4.替换
一般情况想到，先删除，再增加。
实际可以直接替换堆顶元素，进行下滤。
public E replace(E element) {
// E root = remove();
// add(element);
// return root;
elementNotNullCheck(element);
E root = null;
if(size == 0){
elements[0] = element;
size++;
}else{
root = elements[0];
elements[0] = element;
siftDown(0);
}
return root;
}
三、堆排序
思路：就是原地建堆，之后把队首最大元素放到队尾，队尾元素放到堆首，进行下滤操作，堆长度-1。循环倒数第二个元素重复操作。这样队尾元素从后往前依次形成最大，次大，次次大，这种结构，完成了从小到大的排序。
protected void sort() {
// 原地建堆
heapSize = array.length;
for (int i = (heapSize >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
while (heapSize > 1) {
// 交换堆顶元素和尾部元素
swap(0, --heapSize);
// 对0位置进行siftDown（恢复堆的性质）
siftDown(0);
}
}
四、刷题
leetcode 持续补充
1.215.数组中第k个最大元素
思路：原地建堆，然后删除k-1个元素，堆顶就是最大。
注意：书写过程，按照自己的理解，考虑所有分支。主要是siftdown写法。
堆难在
public static int findKthLargest1(int[] nums, int k) {
// 1、原地建堆,从最后一个非叶子节点(n/2)开始siftdown
for(int i = nums.length/2;i>=0;i--){
siftDown(nums,i,nums.length);
}
// 2、删除堆顶元素k-1次，删除后用最后一个元素siftDown
int heapSize = nums.length;
for (int i = 0; i < k-1; i++) {
remove(nums,heapSize-i);
}
return nums[0];
}
public static void siftDown(int[] nums,int index,int heapSize){
while (index< heapSize/2){
int indexValue = nums[index];
// 是否有左右子节点，以及左右子节点找到最大的，和index比较
int lchildIndex = index * 2 + 1;
if(lchildIndex >= heapSize){
break;
}else{
int lchildValue = nums[lchildIndex];
int rightIndex = index * 2 + 2;
if(rightIndex >= heapSize){
// 比较index和左子节点，如果index较大，则break，否则swap，并且index更新为做子节点的index。
if(lchildValue > indexValue){
swap(nums,lchildIndex,index);
index = lchildIndex;
}else{
break;
}
}else{
// 比较index和左右子节点，逻辑相同
int rchildValue = nums[rightIndex];
int largestindex = index;
int largestValue = indexValue;
if(lchildValue > indexValue){
largestindex = lchildIndex;
largestValue = lchildValue;
}
if(rchildValue > largestValue){
largestindex = rightIndex;
largestValue = rchildValue;
}
if(largestindex == index){
break;
}else{
swap(nums,index,largestindex);
index = largestindex;
}
}
}
}
}
public static void remove(int[]nums,int heapSize){
swap(nums,heapSize-1,0);
siftDown(nums,0,heapSize -1);
}
public static void swap(int[] nums,int i,int j){
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
