一、堆的概念

堆可以看做一个完全二叉树，如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。

二、大小根堆的建立

大根堆：

首先对一个无序的序列进行完全二叉树的建立，然后从下往上，从右往左找到第一个非叶子结点开始比较，与该节点的孩子结点进行比较，必须满足大于所有孩子结点。

小根堆的建立：

与大根堆类似，首先对一个无序的序列进行完全二叉树的建立，然后从下往上，从右往左找到第一个非叶子结点开始比较，与该节点的孩子结点进行比较，必须满足小于所有孩子结点。

三、堆的调整

1. 向下调整

private void shiftDown(int parent,int len){int child = 2*parent + 1;while(child < len){if(child + 1 < len && elem[child] < elem[child + 1]){child++;}if(elem[child] > elem[parent]){int tmp = elem[child];elem[child] = elem[parent];elem[parent] = tmp;parent = child;child = 2 * parent + 1;}else{break;}}}

2. 向上调整

public void shiftUp(int child) {int parent = (child - 1) / 2;while (child > 0) {if (elem[parent] > elem[child]) {break;}else{int t = elem[parent];elem[parent] = elem[child];elem[child] = t;child = parent;parent = (child - 1) / 1;}}}