二叉堆和堆排序

1. 简介

堆是优先队列最高效的一种数据结构，堆又分为最大堆最小堆。最大堆的孩子节点的key小于或者等于父亲节点的key，而最小堆则是孩子节点key大于或者等于父亲节点key。堆通常的实现是二叉堆。

2. ADT

insert：插入一个元素。
delete：删除一个元素。
replace：替换一个元素。
findMax（findMin）：查找最大或者最小元素。
deleteMax（deleteMin）：删除最大或者最小元素。
heapify：将非二叉堆转化为二叉堆。
size：二叉堆的大小。
isEmpty：堆是否为空。
siftDown：查看当前节点是否需要和当前节点的子节点互换，如需要则互换位置。
siftUp：查看当前节点是否需要和当前节点的父节点互换，如需要则互换位置。
heapSort：堆排序

其中核心的操作为heapify、siftDown、siftUp。

3. 实现思路（以最大二叉堆为例）

Ex：数组A = {20,30,10,50,30,40};
将次数组绘制为二叉树为：

二叉树

很明显这个数组不符合最大二叉堆的定义也即是孩子节点的key小于或者等于父亲节点的key。
我们将每个节点从左到右，从上到下，以此标上1,2,3,4,5,6的序号。
我们可以很明显的看出来两个二叉树的性质：

1. 最后一个有孩子节点的序号为n / 2。
2. 若其中n/2 ≥ i ≥ 0，那么A[i]的左右孩子节点分别为A[2 * i + 1]和A[2 * i + 2]。
3. 如n > i > 0，那么A[i]的父亲节点为A[（i + 1） >> 1 - 1]

siftDown：利用性质2从当前元素的位置找到两个子节点的位置，然后依次两个子节点依次与父节点比较大小来判断是否需要互换位置。
siftUp：利用性质2和性质3获取三个节点的位置，然后依次两个子节点依次与父节点比较大小来判断是否需要互换位置。
heapify：根据堆的定义我们可知道，父亲节点的key大于或等于孩子节点的key。因此我们可以从最后一个含有孩子节点的位置开始从右到左，从下到上依次进行siftDown操作。则可以将数组转化为最大二叉堆。
heapSoft：heapSoft只能使用在已经为最大二叉堆或者最小二叉堆上。1#我们将A[0]和A[n]的元素互换，A[n]则为数组中最大的元素，随后将A[0]到A[n-1]的元素进行heapify运算后那么A[0]到a[n-1]则为最大二叉堆。然后重复1的步骤将第一位和最后一位互换直到互换到根节点，之后就会得到排好序的数组。

4. 伪代码

siftUp伪代码描述：

siftUp(A, index) //A为数组,index为当前元素的下标
     parentNodeIndex = ((index + 1) >> 1) - 1;
     leftNodeIndex = 2 * parentNodeIndex + 1;
     rightNodeIndex = leftNodeIndex + 1;
     if (A[parentNodeIndex] < A[leftNodeIndex])
            swap(A,parentNodeIndex, leftNodeIndex);//互换位置
     if (A[parentNodeIndex] < A[rightNodeIndex])
            swap(A,parentNodeIndex, rightNodeIndex);//互换位置

heapify伪代码描述：

heapify(A, index) //A为数组,index为当前元素的下标
     for a = A.length >> 1 to 1
            siftDown(a - 1);

sort伪代码描述：

sort(A)
     for i = A.length - 1 to 1 {
            swap(0, i);
            heapify(i); //将i之前的元素构建最大二叉堆
      }

5. Java实现

public class BinaryHeap{

        private Integer[] array;

        public void heapify(Integer[] target) {
            if (target == null)
               return;

            array = new Integer[target.length];
            System.arraycopy(target, 0, array, 0, target.length); //拷贝数组
            heapifyRecursion(0); //递归版本
    //        if (target.length != 0)  //非递归版本
    //            for (int a = array.length >> 1; a > 0; a--) 
    //                siftDown(a - 1);
        }

        private void heapifyRecursion(int parent) {
            if (parent < array.length >> 1) {
                heapify(2 * parent + 1); //left
                heapify(2 * parent + 2); //right
                siftDown(parent);
            }
        }

        private void siftUp(int index) {
            int parentNodeIndex = ((index + 1) >> 1) - 1;
            int leftNodeIndex = 2 * parentNodeIndex + 1;
            int rightNodeIndex = leftNodeIndex + 1;
            if (array[parentNodeIndex] < array[leftNodeIndex])
                swap(parentNodeIndex, leftNodeIndex);

            if (rightNodeIndex < array.length && array[parentNodeIndex] < array[rightNodeIndex])
                swap(parentNodeIndex, rightNodeIndex);
        }

        private void siftDown(int index) {
            int leftNodeIndex = 2 * index + 1;
            int rightNodeIndex = leftNodeIndex + 1;
            if (array[index] < array[leftNodeIndex])
                swap(index, leftNodeIndex);

            if (rightNodeIndex < array.length && array[index] < array[rightNodeIndex])
                swap(index, rightNodeIndex);
        }

       private void siftDown(int index, int sort) {  //sort为已经排好序的位置
            int leftNodeIndex = 2 * index + 1;
            int rightNodeIndex = leftNodeIndex + 1;
            if (array[index] < array[leftNodeIndex])
                swap(index, leftNodeIndex);

            if (rightNodeIndex < sort && array[index] < array[rightNodeIndex])
                swap(index, rightNodeIndex);
        }

        private void swap(int index, int index2) {
            int a = array[index];
            array[index] = array[index2];
            array[index2] = a;
        }

        private void heapify(int sort) {
            for (int a = sort >> 1; a > 0; a--)
                siftDown(a - 1, sort);
        }

        public void sort() {
            if (array == null || array.length == 0)
                return;

            for (int i = array.length - 1; i > 0; i--) {
                swap(0, i);
                heapify(i);
            }
        }
}