最大堆和最小堆特性：
（1）都是完全二叉树，最大堆根节点元素大于所有子节点，最小堆根节点元素小于所有子节点；
（2）完全二叉树可以使用数组实现，根节点i（数组索引值），左子节点为 2*i+1，右子节点为 2*(i+1)；节点i的父节点为 (i-1)>>1；（注意，计算父节点时，最好使用位操作，否则可能出错）
（3）完全二叉树节点n个，高度为log2(n+1)，插入和删除操作时间复杂度为O(log n)
最大堆和最小堆的应用：
（1）利用最大堆和最小堆实现堆排序，如按升序排序，采用最小堆，每次从堆顶删除的元素即为最小的元素；同理采用最大堆，可实现降序排序
（2）利用最大堆和最小堆实现Top K问题，
1）计算数组最大的K个数，可使用最小堆，先构建K大小的最小堆，新元素与堆顶元素比较，如果大于堆顶元素，则删除堆顶，加入新元素；否则最小堆不变；
2）计算数组最小的K个数，可使用最大堆，同理，如果新元素比堆顶小，则删除堆顶，加入新元素；否则最大堆不变。
关键思路：
1.构建堆
已最大堆为例，构建最大堆，从下往上执行判断，开始于最后一个非叶子节点；根节点采用下浮操作，与每个子树所有节点比较，找到适合的位置；每个子树都必须是最大堆；
（1）起始为最后一个非叶子节点，位置为（endIdx - 1）>> 1，依次从下往上遍历所有非叶子节点
（2）构建子树为最大堆，子树根节点下浮操作，与所有节点比较，找到子树根节点在子树中适合的位置
（3）构建子树为最大堆时，注意更新原根节点的位置
2.插入操作：节点上浮法。
在尾部添加元素，依次往上找父节点（for(int i = (endidx-1) >> 1; i >= 0 ; i = (i-1) >> 1)，注意此处如果用除2，会出现死循环）比较和替换。因为插入操作时，已是最大堆。
3.删除操作：最大堆最后一个结点的下沉。
删除根节点，将最后一个节点放在根节点位置，然后依次往下比较，找到合适的位置
代码实现
最大堆：构建、新增和删除，其中 属性 int[] n 存储最大堆。
package com.jdk.heap.test; public class Heap { private int[] n; public Heap(int[] n) { this.n = n; } public void createMaxHeap() { int endidx = n.length - 1; //1. 从最后一个非叶子节点开始 for(int i = (endidx-1)/2; i >= 0; i--) { //2.构建子树最大堆，子树根节点必须与所有节点进行比较 int rootidx = i;//在子树中不断更新原root的位置 int left = 2*i + 1; int right = 2*(i+1); //3.非叶子节点包含叶子情况存在3种情况：1.左右子节点都有；2.只有左节点；3.没有子节点 //3.1 包含左右两个子节点的比较 while(left <= endidx && right <= endidx) { //3.1.1根节点大于两个子节点时break，因为左右子树已是最大堆 if(n[rootidx] > Math.max(n[left], n[right])) { break; } //3.1.2 根节点小于左右子节点的最大者，与子节点最大者交换；更新根节点rootidx if(n[left] > n[right]) { swap(n, left, rootidx); rootidx = left; } else { swap(n, right, rootidx); rootidx = right; } //3.1.3 更新左右子节点 left = 2*rootidx + 1; right = 2*(rootidx + 1); } //3.2如果根节点没有左右子节点，存在2种情况：1.只有左节点，该节点为数组最后一位；2.没有子节点 //故只需要判断第1种情况即可 if(left == endidx) { if(n[rootidx] < n[left]) swap(n, left, rootidx); } } } private void swap(int[] n, int n1, int n2) { int tmp = n[n1]; n[n1] = n[n2]; n[n2] = tmp; } /** * 最大堆中插入元素 * 节点上浮操作，将新节点放入尾部，然后依次往上遍历 * @param n * @param k */ public void insert(int k) { int[] copy = new int[n.length+1]; for(int i = 0; i < n.length; i++) { copy[i] = n[i]; } copy[n.length] = k; int endidx = copy.length-1; //因为是在原最大堆中添加元素，故只需要比较上下两级 for(int i = (endidx-1) >> 1; i >= 0 ; i = (i-1) >> 1) { //过程与构建最大堆相同 int left = 2*i + 1; int right = 2*(i+1); if(left <= endidx && right <= endidx) { if(copy[i] > Math.max(copy[left], copy[right])) { continue; } if(copy[left] > copy[right]) { swap(copy, left, i); } else { swap(copy, right, i); } } else if(left == endidx ) { if(copy[i] < copy[left]) swap(copy, left, i); } } n = copy; } /** * 删除，删除根节点 * 然后将尾节点放在根节点，再进行下浮操作 * @param n */ public int delete() { int root = n[0]; if(n.length == 1) return root; int[] copy = new int[n.length-1]; for(int i = 0; i < n.length-1; i++) { copy[i] = n[i]; } copy[0] = n[n.length-1]; //下浮操作 int rootidx = 0; int left = 2*rootidx+1; int right = 2*(rootidx+1); //最后一个非叶子节点包含2个子节点 while(left <= copy.length-1 && right <= copy.length-1) { if(copy[rootidx] > Math.max(copy[left], copy[right])) { break; } if(copy[left] > copy[right]) { swap(copy, left, rootidx); rootidx = left; } else { swap(copy, right, rootidx); rootidx = right; } left = 2*rootidx +1; right = 2*(rootidx + 1); } //最后一个非叶子节点包含1个子节点，只能为左节点 if(left == copy.length-1) { if(copy[rootidx] < copy[left]) swap(copy, left, rootidx); } n = copy; return root; } public int[] getN() { return n; } public void setN(int[] n) { this.n = n; } }
测试：
public static void main(String[] args) { int[] n = new int[] {79,66,43,83,30,87,38,55,91,72,49,9}; Heap heap = new Heap(n); heap.createMaxHeap(); n = heap.getN(); for(int i : n) { System.out.print(heap.delete() + " "); } }
输出（有时间，画图说明）：
91 87 83 79 72 66 55 49 43 38 30 9
最小堆
实现与最大堆类似，也将代码附上
package com.jdk.heap.test; public class MiniHeap { public void createMiniHeap(int[] n) { int endIdx = n.length-1; for(int i = (endIdx-1) >> 1; i >= 0; i--) { int rootIdx = i; int left = 2*rootIdx + 1; int right = 2*(rootIdx + 1); while(left <= endIdx && right <= endIdx) { if(n[rootIdx] < Math.min(n[left], n[right])) { break; } //与子节点的小者交换 if(n[left] < n[right]) { swap(n, left, rootIdx); rootIdx = left; }else { swap(n, right, rootIdx); rootIdx = right; } left = 2*rootIdx +1; right = 2*(rootIdx+1); } if(left == endIdx) { if(n[left] < n[rootIdx]) swap(n, left, rootIdx); } } } private void swap(int[] n, int n1, int n2) { int tmp = n[n1]; n[n1] = n[n2]; n[n2] = tmp; } public int[] insert(int[] n, int k) { int[] copy = new int[n.length+1]; for(int i = 0; i < n.length; i++) { copy[i] = n[i]; } copy[n.length] = k; int endIdx = copy.length-1; for(int i = (endIdx-1)>>1; i >= 0; i = (i-1)>>1) { int left = 2*i+1; int right = 2*(i+1); if(left <= endIdx && right <= endIdx) { if(copy[i] < Math.min(copy[left], copy[right])) { break; } if(copy[left] < copy[right]) { swap(copy, left, i); }else { swap(copy, right, i); } } if(left == endIdx) { if(copy[left] < copy[i]) swap(copy, left, i); } } return copy; } public int[] delete(int[] n) { int[] copy = new int[n.length-1]; for(int i = 0; i < n.length-1; i++) { copy[i] = n[i]; } copy[0] = n[n.length-1]; int rootIdx = 0; int left = 2*rootIdx +1; int right = 2*(rootIdx + 1); int endIdx = copy.length-1; while(left <= endIdx && right <= endIdx) { if(copy[rootIdx] < Math.min(copy[left], copy[right])) { break; } if(copy[left] < copy[right]) { swap(copy, left, rootIdx); rootIdx = left; }else { swap(copy, right, rootIdx); rootIdx = right; } left = 2*rootIdx +1; right = 2*(rootIdx + 1); } if(left == endIdx) { if(copy[left] < copy[rootIdx]) swap(copy, left, rootIdx); } return copy; } }
测试：
public static void main(String[] args) { MiniHeap heap = new MiniHeap(); int[] n = new int[] {79,66,43,83,30,87,38,55,91,72,49,9}; heap.createMiniHeap(n); for(int i : n) { System.out.print(i + " "); } }
输出：
9 30 38 55 49 43 79 83 91 72 66 87