堆的实现方式

堆

PriorityQueue底层用了堆的数据结构，而堆是基于二叉树对元素进行一定的调整所形成的的一种结构。

堆的概念

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

• 堆中某个节点的值总是不大于或不小于其父节点的值。
• 堆总是一棵完全二叉树。
• 

堆的存储方式

由于堆是一棵完全二叉树，因此可以用层序的规则采用顺序存储的方式来达到高效存储。
将元素存放在数组中之后，还可以根据二叉树的性质将树进行还原。
假设i为节点在数组中的下标，则：

• 如果i为0，则i表示的节点为根节点，否则i节点的双亲节点为 (i - 1)/2
• 如果2 * i + 1 小于节点个数，则节点i的左孩子下标为2 * i + 1，否则没有左孩子
• 如果2 * i + 2 小于节点个数，则节点i的右孩子下标为2 * i + 2，否则没有右孩子

堆的创建（小堆为例）

若堆的左右子树已经满足小堆，则只需将根节点向下调整。
调整的过程：

1. 让parent标记需要调整的节点，child标记parent的左孩子（因为堆一定是完全二叉树，如果一个节点有右孩子，则一定有左孩子）
2. 如果parent的左孩子存在，进行以下操作：

• parent的右孩子是否存在，若存在则找到左右孩子中较小的孩子，让child标记
• 让parent与它较小的孩子进行比较，如果parent小于它较小的孩子，调整结束。若不是，将parent与child交换，然后让parent和child向下移动，继续向下调整，重复上述步骤。
  
  代码实现：

private void shiftDown(int parent){
    //使用child标记parent的较小的孩子
    //默认情况下先让其标记其左孩子，因为parent可能只有左孩子而没有右孩子
    int child = parent*2+1;
    while(child < size) {//保证左孩子存在
        //找parent中较小的孩子
        //再用左右孩子进行比较时，必须要保证右孩子存在
       //if (child+1<size && array[child + 1] < array[child]) {
   	   if(child+1<size&&compare.compare(array[child+1],array[child])<0){
           child += 1;
   		}
        //检测较小的孩子是否比parent小
        //if (array[child] < array[parent]) {
        if(compare.compare(array[child],array[parent])<0){
            //说明parent不满足小堆的性质
            swap(parent, child);
            //可能会导致子树不满足小堆的性质
            //继续向下调整
            parent = child;
            child = parent * 2 + 1;
        } else {
            return;
        }
    }
}

任意序列：
循环调整

public static void createHeap(int[] array) {
	// 找倒数第一个非叶子节点，从该节点位置开始往前一直到根节点，遇到一个节点，应用向下调整
	int root = ((array.length-2)>>1);
	for (; root >= 0; root--) {
		shiftDown(array, root);
	}
}