二叉堆和堆排序

（二叉）堆是一个数组，它可以近似看作完全二叉树。树上的每一个节点对应数组中的一个元素。除了最底层，该树是完全充满的，而且是从左向右填充。
根据节点下标可以求出对应的子树和双亲

 PARENT(i)
    return [i/2]   //i表示数组中的第几个元素，[i/2]表示取整数
 LEFT(i)
    return 2*i
 RIGHT(i)
     return 2*i+1

二叉堆可分为最大堆和最小堆。堆顶元素（根节点元素）比其它节点元素都大的堆并且任何双亲节点都不小于子节点是最大堆，反之堆顶元素比其它节点元素都小，并且任何双亲节点都不大于子节点的堆是最小堆。
A是数组
最大堆 A[PARENT(i)]>=A[i] （常用用于堆排序）
最小堆A[PARENT(i)]<=A[i] （常用于优先队列）
堆的一些基本操作，比如建堆，调整堆，堆排序的时间复杂度是O(lg n)。堆的高度是lgn。
下面给出维护堆的伪代码

MAX-HEAPIFY(A, i)
1 l=LEFT(i) //获取左子树位置
2 r=RIGHT(i) //获取右子树位置
3 if l<=A.heap-size and A[l]>A[i]
4  largest=l;
5 else largest=I
6 if r<=A.heap-size and A[r]>A[i]
7  largest=r
8 if largest 不等于 i
9   exchange  A[I] with A[largest]
    MAX-HEAPIFY(A, largest) //递归调用，因为交换可能会破坏堆性质

我们从完全二叉树的性质上来分析，字数组A(|n/2|+1…n)中的元素都是树的叶节点，豆哥叶节点都可以看成只包含一个元素的堆。那么建堆我们只需要从非A(|n/2|+1…n)的数组元素开始调用建堆过程就可以了。下面给出伪代码

BUILD-MAX-HEAP（A）
1 A.heap-size=A.length
2 for I=A[A.length/2] down to 1
3  MAX-HEAPIFY(A,i)

堆的用途之一是用于排序的堆排序。在建立完成最大堆（按升序排序数组，最小堆就是按降序排序数组）之后，注意到整个数组的 最大元素 总是在最大堆的第一个，即a[0]。这时，如果我们拿走第一个元素，放到数组的最后一个位置，然后对第一个元素进行维护最大堆maxHeapify，如此循环进行，便可完成整个数组的排序。下面给出伪代码

HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i=A.length down to 2
3  exchange A[1] with A[i]
4  A.heap-size--
5  MAX-HEAPIFY(A,1)

完整示例代码

import org.junit.Test;

/**
 * Created by WuNanliang on 2017/5/3.
 * 堆数据结构
 */
public class HeapDemo {


    @Test
    public void testDemo() {
        int[] arr = {10, 8, 11, 8, 14, 9, 4, 1, 17};
        heapSort(arr);
        for (int num : arr)
            System.out.print(num + " ");
    }

    /**
     * 左子树的位置
     *
     * @param parentIndex 双亲节点位置
     * @return
     */
    private int leftChildIndex(int parentIndex) {
        return 2 * parentIndex + 1;//因为根节点index=0
    }

    /**
     * 右子树的位置
     *
     * @param parentIndex 双亲节点位置
     * @return
     */
    private int rightChildIndex(int parentIndex) {
        return 2 * parentIndex + 2;//因为根节点index=0
    }

    private void swap(int[] arr, int i, int j) {
        arr[j] = arr[i] + arr[j];
        arr[i] = arr[j] - arr[i];
        arr[j] = arr[j] - arr[i];
    }

    /**
     * 维护最大堆
     *
     * @param arr          数组
     * @param currentIndex 当前位置
     * @param length       数组的长度
     */
    private void maxHeapify(int[] arr, int currentIndex, int length) {
        int leftIndex = leftChildIndex(currentIndex);
        int rightIndex = rightChildIndex(currentIndex);
        //largestIndex  记录leftIndex/rightIndex/currentIndex最大值
        int largestIndex;
        if (leftIndex < length && arr[leftIndex] > arr[currentIndex])
            largestIndex = leftIndex;
        else largestIndex = currentIndex;
        if (rightIndex < length && arr[rightIndex] > arr[largestIndex])
            largestIndex = rightIndex;
        if (largestIndex != currentIndex) {
            swap(arr, currentIndex, largestIndex);
            //递归维护堆性质
            maxHeapify(arr, largestIndex, length);
        }
        System.out.println("index:" + currentIndex + "->" + arr[currentIndex]);
    }


    /**
     * 建立最大堆
     *
     * @param arr
     */

    private void buildMaxHeap(int[] arr) {
        int len = arr.length;
        int middleIndex = len / 2;

        for (int i = middleIndex + 1; i >= 0; i--)
            maxHeapify(arr, i, len);
    }

    private void heapSort(int[] arr) {
        buildMaxHeap(arr);
        int len = arr.length;
        for (int i = len - 1; i >= 1; i--) {
            swap(arr, i, 0);
            len--;
            maxHeapify(arr, 0, len);
        }
    }


}

参考资料

1《算法导论 原书第3版》
2 堆排序以及最大优先队列