堆
什么是堆？
堆结构就是用数组实现的完全二叉树结构。
什么是最大堆
完全二叉树中，如果所有的节点都大于等于它的子节点（即每颗子树的最大值都在顶部），那么这就是最大堆。
比如[6,5,3,4,2,1]表示的最大堆是：
什么是最小堆
完全二叉树中，如果所有的节点都小于等于它的字节点（即每颗子树的最小值都在顶部），那么这就是最小堆。
比如[1,3,2,4,6,5]表示的最小堆是：
节点的位置
- 左侧子节点的位置是2∗index+12*index+12∗index+1
- 右侧子节点的位置是2∗index+22*index+22∗index+2
- 父节点位置是(index−1)/2(index-1)/2(index−1)/2
堆的基本操作-HeapInsert 插入
思路（以最小堆为例）
- 将值插入堆的底部，即数组的尾部
- 然后将这个值与它的父节点进行比较，如果比父节点的值小，则进行交换，交换之后再继续跟上一级的父节点比较，直到父节点小于等于这个插入值。
复杂度
大小为k的堆中插入元素的时间复杂度为O(logk)O(log{k})O(logk)。因为对于一个长度为n的数组，也就是节点数为n的二叉树，那么这个二叉树的层级是lognlog{n}logn，插入元素时，是逐层进行比较，因此时间复杂度就是lognlog{n}logn。
Javascript版（以最小堆为例）
class MinHeap{ constructor(){ this.heap=[] } swap(i1,i2){ const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = this.heap[i1]; } getParentIndex(i){ // return Math.floor((i-1)/2); return (i-1)>>1; } shiftUp(index){ if(index === 0) return; const parentIndex = this.getParentIndex(index); if(this.heap[parentIndex] > this.heap[index]){ this.swap(parentIndex, index); this.shiftUp(parentIndex); } } insert(value){ this.heap.push(value); this.shiftUp(this.heap.length - 1); } } const h = new MinHeap(); h.insert(3); 复制代码
Java版（以最大堆为例）
public static void heapInsert(int[] arr, int index){ while(arr[index] > arr[(index - 1)/2]){ swap(arr, index, (index - 1)/2); index = (index - 1)/2; } } 复制代码
堆的基本操作-删除堆顶（Heapify 堆化）
思路（以最小堆为例）
- 用数组尾部元素替换堆顶，数组长度-1（直接删除堆顶会破坏堆结构）
- 然后下移进行heapify 堆化
复杂度
大小为k的堆中删除堆顶的时间复杂度为O(logk)O(log{k})O(logk)
Javascript版（以最小堆为例）
class MinHeap{ constructor() { this.heap = []; } swap(i1, i2) { const temp = this.heap[i1]; this.heap[i1] = this.heap[i2]; this.heap[i2] = temp; } getParentIndex(i) { // return Math.floor((i-1)/2)] // 取商 return (i - 1) >> 1; } getLeftIndex(i) { return i * 2 + 1 } getRightIndex(i) { return i * 2 + 2 } // 上移 shiftUp(index) { if (index == 0) return; const parentIndex = this.getParentIndex(index); if (this.heap[parentIndex] > this.heap[index]) { this.swap(parentIndex, index); this.shiftUp(parentIndex) } } shiftDown(index) { const leftIndex = getLeftIndex(index); const rightIndex = getRightIndex(index); if (this.heap[leftIndex] < this.heap[index]) { this.swap(leftIndex, index); this.shiftDown(leftIndex) } if (this.heap[rightIndex] < this.heap[index]) { this.swap(rightIndex, index); this.shiftDown(rightIndex) } } insert(value) { this.heap.push(value); this.shiftUp(this.heap.length - 1) } pop() { this.heap[0] = this.heap.pop(); this.shiftDown(0) } } const h = new MinHeap(); h.insert(3); h.insert(2); h.insert(1); h.pop() 复制代码
Java版（以最大堆为例）
// 某个数在index位置，能否向下移动 public static void heapify(int[] arr, int index, int heapSize){ int left = index * 2 + 1; while(left < heapSize){ // 下方还有孩子的时候 // 两个孩子中，谁的值大，把下标给largest int largest = left + 1 < heapSize && arr[left+1] > arr[left] ? left + 1 : left; if(largest == index){ break; } swap(arr, largest, index); index = largest; left = index * 2 +1; } } 复制代码
堆的基本操作-获取堆顶和堆的大小
- 获取堆顶：直接返回数组的头部
- 获取堆的大小：直接返回数组的长度
class MinHeap{ ... peek() { return this.heap[0] } size() { return this.heap.length } } 复制代码
堆排序
思路
- 先将数组进行堆化，成为一个最大堆
- 然后将数组首尾元素交换，尾元素移出堆（heapSize-1），首元素继续进行堆化
- 堆化之后重复上一个步骤
- heapSize=0时，就排好序了（移出堆的元素是越来越小的） 时间复杂度：O(nlogn)O(nlog{n})O(nlogn)，空间复杂度：O(1)O(1)O(1)，比快排更优
public static heapSort(int[] arr){ if(arr==null || arr.length < 2){ return; } for(int i=0; i<arr.length; i++){ // O(N) heapInsert(arr, i); // O(logN ) } int heapSize = arr.length; swap(arr, 0, --heapSize); while(heapSize > 0){ // O(N) heapify(arr, 0, heapSize); // O(logN ) swap(arr, 0, --heapSize); // O(1) } } 复制代码
优化堆化过程
上面这个堆化实现过程，是将元素一个一个插入逐个进行堆化的。而现实情况往往是直接就拿到一个元素已经确定的数组，此时，我们就可以不用上面的方式进行逐个堆化。
比如[1,3,2,4,6,5,8,10,9,7,11,18,17,13,12 ]表示的最小堆是：
那么我们可以先从数组最后一个元素开始进行堆化。先堆化一个小子树然后往左往上进行扩展：
代码优化
public static heapSort(int[] arr){ if(arr==null || arr.length < 2){ return; } // for(int i=0; i<arr.length; i++){ // O(N) // heapInsert(arr, i); // O(logN ) // } for(int i=arr.length-1;i>=0;i--){ heapify(arr,i,arr.length); } int heapSize = arr.length; swap(arr, 0, --heapSize); while(heapSize > 0){ // O(N) heapify(arr, 0, heapSize); // O(logN ) swap(arr, 0, --heapSize); // O(1) } } 复制代码
数学论证
一个长度为N的数组，那么形成的二叉树中的最底层有N/2个节点(假设有子节点，看了一眼，但不移动)，倒数第二层有N/4个节点（最多移动1步），倒数第三层有N/8个节点（最多移动1 2步），...，整体复杂度就是：T(N)=N/2+N/4∗2+N/8∗3+...T(N)=N/2+N/4*2+N/8*3+...T(N)=N/2+N/4∗2+N/8∗3+...
T(N)=N/2+N/4∗2+N/8∗3+...T(N)=N/2+N/4*2+N/8*3+...T(N)=N/2+N/4∗2+N/8∗3+...
2T(N)=N+N/2∗2+N/4∗3+...2T(N)=N+N/2*2+N/4*3+...2T(N)=N+N/2∗2+N/4∗3+...
2T(N)−T(N)=T(N)=N+N/2+N/4+...2T(N)-T(N)=T(N)=N+N/2+N/4+...2T(N)−T(N)=T(N)=N+N/2+N/4+...
根据等比数列求和公式：
就可以得出复杂度是：O(N)O(N)O(N)
堆的应用
- 堆能高效、快速地找出最大值和最小值，时间复杂度为O(1)O(1)O(1)
- 找出第K个最大（小）元素，这一类也可以用堆来找出
举个例子：找出第K个最大元素 思路如下：
- 首先构建一个最小堆，并将元素依次插入堆中
- 当堆的容量超过k，就删除堆顶
- 插入结束后，堆顶就是第k个最大元素
扩展
已知有一个几乎有序的数组，几乎有序是指，如果把数组排好顺序的话，每个元素移动的距离可以不超过k，并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序。
思路：维护一个大小为k的小根堆，从头到尾扫描n个数，如果当前数比堆顶大，替换堆顶，每个元素的移动距离不超过K，表示前K个数中一定有最小值， 所以堆顶为最小值，堆顶放到a0处，a[k]放到最小堆的堆顶，继续建堆，知道剩下最后k个元素，此时随着每次堆顶的弹出，堆的大小k--. 因为每个元素移动都在k以内，所以时间复杂度为O(N∗logK)O(N*logK)O(N∗logK)，空间复杂度O（k）。
1.21
假设k=6，遍历前7个数，扔到最小堆里，最小数一定在0位置，
Leetcode
相关链接：
