堆、堆排序及Top K问题

堆（Heap）是一种特殊的二叉树，有以下两个特点：
1.堆是一个完全二叉树；
2.堆中每个节点的值都必须大于等于其子树中每个节点的值（大顶堆）或小于等于其子树中每个节点的值。（小顶堆）。

1、堆的实现

1.1、堆的储存方式

对于完全二叉树而言，采用数组进行储存是一个非常不错的选择，例如上图中的两个堆采用数组进行储存则结构为：

此处有点特殊的是，数组下标为0的位置闲置没有储存数据。在这种情况下，对于下标为i的元素，其左右子树的下标分别为2i和2i+1,父节点则为i/2。

1.2、堆的核心操作

插入元素

插入元素的过程可以分为两步：将插入元素放入数组末尾的空位、堆化使插入新数据后的堆满足开头所谈到的两点要求，核心步骤是对插入后的堆进行堆化。
堆化的过程有两种思路进行实现，自上往下和自下往上，这两种思路的核心都是沿着节点所在的路径进行比较并操作，以下以大顶堆为例，给出插入操作的代码：

public class MyHeap {
    private int[] arr;//用于储存元素的数组
    private int n;//堆最多可以储存的元素个数
    private int count;//堆中已经储存的元素个数

    public MyHeap(int capaccity) {
        this.arr = new int[capaccity + 1];
        this.n = capaccity;
        this.count = 0;
    }

    public boolean insert(int data) {
        if (count == n)
            return false;
        arr[++count] = data;
        //将插入到最后的元素找到应该的位置，实现堆化
        //此处从下至上进行堆化
        int i = count;
        while (i / 2 > 0 && arr[i / 2] < arr[i]) {
            swap(arr , i , i/2);
            i = i/2;
        }
        return true;
    }
    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

删除堆顶元素

由堆的性质可知堆顶元素即为整组数据中的最大值（大顶堆）或最小值（小顶堆），以大顶堆为例，删除堆顶元素以后需要找到第二大元素之后将其放置在堆顶，并保证堆的性质不被破坏。此时如果从上向下以此遍历，会出现“数组空洞”的现象，即数组中间部分某个位置没有元素。此处可以将数组末尾的元素放到堆顶，并进行一次上向下的堆化。

  public boolean removeMax() {
        if (count == 0)
            return false;
        arr[1] = arr[count--];
        heapify(arr, count, 1);
        return true;
    }
     /**
     * 从上往下进行堆化
     *
     * @param arr   储存堆的数组
     * @param count 堆中元素个数
     * @param i     待堆化元素所处位置
     */
     private void heapify(int[] arr, int count, int i) {
        while (true) {
            int minpos = i;
            if (i * 2 <= count && arr[i * 2] > arr[i]) {
                minpos = i * 2;
            } 
            if (i * 2 + 1 <= count && arr[i * 2 + 1] > arr[i]) {
                minpos = i * 2 + 1;
            }
            //如果子节点没有比父节点大的值，则返回，堆化完成
            if (minpos == i) break;
            swap(arr, i,minpos);
            i = minpos;
        }
    }

堆化的时间复杂度为O(nlogn)。

2、堆的应用

2.1、堆排序

因为堆顶元素始终是最大或最小元素，利用该性质可以实现排序操作。由建堆和排序两步完成，对于建堆操作可以采用前面提到的插入和删除堆顶元素两种操作中的堆化方式。
对于自下向上进行堆化的方式，我们可以认为最初原数组中只有第1个元素，依次将第2-第n个元素插入堆中；对于自上向下进行堆化的方式，我们可以从n/2个元素开始，逐渐向前进行堆化操作，n/2-n个元素都是叶子节点，不用堆化。
第一种思路的代码：

public void buidHeap(int[] arr , int n){
    if(n == 1) return;
    for(int i = 2 ; i <= n ; i++){
        int j = i;
        while (j / 2 > 0 && arr[j / 2] < arr[j]) {
            swap(arr , j , j/2);
            j = j/2;
        }
    }
}

第二种思路的代码

public void buidHeap(int[] arr , int n){
    for(int i = n/2 ; i >= 1 ; i--){
        heapify(arr , n, i)
    }
}

建堆的时间复杂度为O(n)，具体分析可参考：https://www.zhihu.com/question/20729324
建堆完成后，数组中的数据已按照堆的性质进行了排序，此时可以将对顶元素出堆，然后将下标为n的元素放到堆顶，并将剩下的n-1个元素进行堆化，将刚出堆的元素放在下标为n的位置。重复进行上述操作，直至堆中只剩下标为1的元素。

public void sort(int[] arr, int n){
    buiidHeap(arr , n);
    int k = n;
    while (k > 1){
        swap(arr , 1 , k);
        k--;
        heapify(arr,k,1);
    }
}

2.2、Top K问题

Top K即为确定无序数组中前K大的数据。此处可以构建一个容量为K的小顶堆，堆满以后继续对剩下的数据进行遍历，如果数据大于堆顶元素则将原堆顶出栈，并将数据入栈。遍历数组的时间复杂度为O(n),一次堆化的时间复杂度为O(logK),n个数据入堆的时间复杂度为O(nlogk)。

public topK(int[] arr , int n , int k){
    Heap heap = new Heap(k);
    int min = 0;//用以储存堆顶元素
    for(int i = 1 ; i < n; i++){
        if(i <= k){
            min = heap.insert(arr[i]);
        } else {
            if(arr[i] > min){
                heap.pop();
                min = heap.insert(arr[i]);
            }
        }
    }
}

此处需要重写insert函数，使返回新堆的堆顶。
如果求bottom K问题则构建大顶堆，当元素大于小于堆顶元素时，删除堆顶元素并将新元素入堆。