堆和堆排序

一、什么是优先队列？

　　普通队列：先进先出，后进后出

　　优先队列：出队顺序和入队顺序无关，和优先级相关。

　　优先队列的实现：

	入队	出队
普通数组	O(1)	O(n)
顺序数组	O(N)	O(1)
堆	O(logN)	O(logN)

二、堆的基本实现

　　二叉堆的特点：这很重要！！！是核心

　　　　任意节点小于其父节点

　　　　除了最后一层叶子节点外，其他层的元素个数必须是最大值，叶子节点虽然可以不是最大值，但必须靠左排列(最大堆)

　　　　堆是一棵完全二叉树

　　用数组存储二叉堆

　　这样用数组存储的堆中元素和数组下标有以下规律：这很重要！！！是核心

父节点下标：parent (i) = ( i - 1) / 2

左子节点： left child (i) = (i + 1) * 2

右子节点：right child (i) = (i + 1) * 2 + 1

　　最大堆代码实现 (逐步的实现，下面只是简单的定义，各种操作的方法后续依次加入) ：

 1 public class MaxHeap {
 2 
 3     // 存储元素
 4     private int[] data;
 5     // 记录堆中节点个数
 6     private int size;
 7     // 堆的容量
 8     private int capacity;
 9 
10     public MaxHeap(int capacity) {
11 
12         this.capacity = capacity;
13         data = new int[capacity]; // 堆的第一个元素索引为 0;
14         this.size = 0;
15     }
16 
17     public int size() {
18         return size;
19     }
20 
21     public boolean isEmpty() {
22         return size == 0;
23     }
24 
25 }

　　往最大堆中添加元素(shiftUp)

　　根据前面对最大堆的定义(任意子节点小于其父节点) 以及元素下标之间的关系，我们不断交换父子节点的位置，知道满足最大堆的原则，就完成了元素插入。下面是代码实现：

    /**
     * 往最大堆中加入一个元素
     * @param e 
     */
    public void insert(int e) {

        if (size - 1 < capacity) {
            data[size] = e;
            shiftUp(size);
            size++;
        }
    }

    /**
     * 根据堆的定义，交换父子节点的位置，直到满足最大堆的原则
     * @param k
     */
    private void shiftUp(int k) {

        while (k > 0 && data[k] > data[(k - 1) / 2]) {
            SortedHandler.swap(data, k, (k - 1) / 2);
            k = (k - 1) / 2;
        }
    }

　　删除最大堆中的元素(shiftDown)

　　根据优先队列的定义，元素的出顺序按照优先级，而在最大堆中，根节点的优先级就是最大的，因此我们删除的时候，总是从根节点开始。

　　具体的思路是，首先交换根节点和最后一个节点的位置，然后删除掉交换后的根节点，也就是最大值，然后根据堆的定义交换节点位置维护最大堆的原则，最后返回删除了的最大值即可。代码实现如下：

    /**
     * 交换根节点和最后一个节点的位置，再将移除的根节点的值返回，并维护最大堆的原则
     * @return 原堆中的最大值
     */
    public int extractMax() {

        if (size > 0) {
            int res = data[0];

            // 交换第一个和最后一个的位置
            SortedHandler.swap(data, 0, size - 1);
            size--;
            shiftDown(0);
            return res;
        }

        return -1;
    }

    /**
     * 交换节点的位置  维护最大堆的定义
     * @param k 开始的节点位置
     */
    private void shiftDown(int k) {

        while (2 * k + 1 < size) {
            int j = 2 * k + 1; // 左子点的下标
            if (j + 1  data[j]) {
                j += 1;
            }
            if (data[k] < data[j]) {
                SortedHandler.swap(data, k, j);
                k = j;
            } else {
                break;
            }
        }

    }

基本的堆排序

　　通过上面的努力，我们实现了一个基本操作的最大堆。如果前面的明白了的话，那么实现一个堆排序就是小问题了，因为我们的最大堆的输出顺序就是由大到小的，那么排序的问题不过是将数组的顺序反过来 .

    public static void heapSorted1(int arr[]) {

        int n = arr.length;
        MaxHeap heap = new MaxHeap(n);

        for (int i = 0; i ) {
            heap.insert(arr[i]);
        }
        for (int i = n - 1; i >= 0; i--) {
            arr[i] = heap.extractMax();
        }
    }

最大堆的另外一种构造方法 —— Heapify

　　在前面构造最大堆的实现中，我们都是首先构造一个初始化容量的数组，然后依次加入数组的每个元素。现在我们考虑一个情况，因为最大堆的存储本身就是数组实现的，那么当我们对数组需要排序的时候，是否可以直接将这个数组构造成为最大堆呢，而无需逐个的复制元素并shiftUp？答案是肯定的。

　　具体的思路是：将待排序的数组本身看成是一棵二叉树，在这课二叉树中，所有不同的非叶子节点就是不用的最大堆。那么我们就从这棵二叉树的第一个非叶子节点开始执行shiftDown操作，直到整棵二叉树满足最大堆的原则。那么问题又来了？第一个非叶子是多少呢，这里又有一个规律：完全二叉树的排列中，第一个非叶子节点 i 等于数组的长度 (n - 1) / 2.代码实现如下：

    // heapify 的过程
    public MaxHeap(int arr[]) {

        int n = arr.length;
        data = new int[n];
        capacity = n;
        for (int i = 0; i ) {
            data[i] = arr[i];
        }
        size = n;
        // 第一个非叶子节点的下标 (n-1) / 2
        for (int i = (n - 1) / 2; i >= 0; i--) {
            shiftDown(i);
        }

    }

    public static void heapSorted2(int arr[]) {

        int n = arr.length;
        MaxHeap heap = new MaxHeap(arr);

        for (int i = n - 1; i >= 0; i--) {
            arr[i] = heap.extractMax();
        }

    }

堆排序的优化——原地堆排序

    public static void heapSorted3(int arr[]) {

        int n = arr.length;
        
        // heapify ,将数组转换为堆
        for (int i = (n - 1) / 2; i >= 0; i--) {
            __shiftDown(arr, n, i);
        }

        // 
        for (int i = n - 1; i > 0; i--) {
            int tmp = arr[i];
            arr[i] = arr[0];
            arr[0] = tmp;

            __shiftDown(arr, i, 0);
        }

    }

    /**
     *  原地堆排序的shiftDown操作
     * @param arr
     * @param n
     * @param i
     */
    private static void __shiftDown(int[] arr, int n, int i) {

        while (2 * i + 1 < n) {
            int j = 2 * i + 1;
            if (j + 1 ]) {
                j += 1;
            }
            if (arr[j] > arr[i]) {
                int tmp = arr[j];
                arr[j] = arr[i];
                arr[i] = tmp;

                i = j;
            } else
                break;
        }

    }