一、基本概念

堆在逻辑上就是一棵完全二叉树。
堆在物理上是储存在数组中。
满足任意根节点值>=子树节点值，叫做大根堆、最大堆。
满足任意根节点值<=子树节点值，叫做小根堆、最小堆。
堆的基本作用是快速找集合中的最值。

回到目录…

二、上浮操作(siftUp)

	/** 元素上浮操作 **/private void siftUp(int k) {//确认终止条件，当到达顶部时不需要继续上浮//并且只有该节点值>父节点时，才进行上浮while(k > 0 && list.get(k) > list.get((k - 1) / 2)){//交换该节点和父节点的val值swap(k, (k - 1) / 2);//更新索引为父节点的索引k = (k - 1) / 2;}}

回到目录…

三、下沉操作(siftDown)

原理：
该节点和它的左右孩子比较，如果该节点值<孩子的值，则swap(cur.val, max(left.val,right.val));
并且继续向下比较，再让刚刚交换过的孩子节点和它的孩子作比较，直到叶子节点

	/** 元素下沉操作 **/private void siftDown(int k) {// 在确保有孩子的情况下，下沉while(2 * k + 1 < list.size()) {// 先认为左孩子是比较大的孩子int maxChild = 2 * k + 1;// 如果存在右孩子，且右孩子 > 左孩子，则 maxChild 记录右孩子的位置if(2 * k + 2 < list.size() && list.get(maxChild) < list.get(maxChild + 1)){maxChild += 1;}// 比较自己和大孩子的值if(list.get(k) < list.get(maxChild)){swap(k, maxChild);k = maxChild;}else{// 如果此时符合堆性质，则不需要再向下比较了，结束循环break;}}}

回到目录…

四、数组堆化

	//数组堆化,O(N)public MaxHeap(int[] arr) {this.list = new ArrayList<>(arr.length);//将元素放入list中for(int i : arr){list.add(i);}//从最后一个非叶子节点开始倒着下沉每一个节点，直到堆顶for (int i = (arr.length - 2) / 2; i >= 0; i --) {siftDown(i);}}

回到目录…

五、实现大根堆

/*** 自己实现大根堆*/
public class MaxHeap {private List<Integer> list;public MaxHeap() {this(10);}public MaxHeap(int size) {list = new ArrayList<>(size);}// 数组堆化public MaxHeap(int[] arr) {list = new ArrayList<>(arr.length);for(int i : arr) {list.add(i);}// 从最后一个非叶子节点的位置往上做下沉操作for (int i = (arr.length - 2) / 2; i >= 0; i --) {siftDown(i);}}// 上浮操作private void siftUp(int k) {// 和父节点比较大小做交换while(k > 0 && list.get(k) > list.get((k - 1) / 2)){swap(k, (k - 1) / 2);k = (k - 1) / 2;}}// 下沉操作private void siftDown(int k) {// 在确保有孩子的情况下，下沉while(k <= (list.size() - 2) / 2) {// 先认为左孩子是比较大的孩子int maxChild = 2 * k + 1;// 如果存在右孩子，且右孩子 > 左孩子，则 maxChild 记录右孩子的位置if(2 * k + 2 < list.size() && list.get(maxChild) < list.get(maxChild + 1)){maxChild += 1;}// 比较自己和大孩子的值if(list.get(k) < list.get(maxChild)){swap(k, maxChild);k = maxChild;}else{// 如果此时符合堆性质，则不需要再向下比较了，结束循环break;}}}// 添加元素public void add(int val) {// 先插到最后面list.add(val);// 从最后一节点开始上浮siftUp(list.size() - 1);}// 弹出最大堆的最大值public int extractMax() {int max = list.get(0);// 交换首尾元素的值swap(0, list.size() - 1);// 删掉最后一个元素的值(最大值)list.remove(list.size() - 1);// 第一个元素做下沉操作siftDown(0);return max;}// 交换private void swap(int i, int j) {int tmp = list.get(i);list.set(i, list.get(j));list.set(j, tmp);}@Overridepublic String toString() {return list.toString();}
}