详解堆排序「优先队列」

215. 数组中的第K个最大元素

排序算法千千万，今天来讲堆排序！！

关于「详解快排及其应用」，可见 详解快排及其应用

关于「详解归并排序及其应用」，可见 详解归并排序及其应用

算法思想

「快排」和「归并」都是一次性将所有元素排好顺序，但有一些场景，我们每次可能只需要获得最小值即可

「堆排序」就是这样的特点，并非一次性全部排好序，而只有堆顶元素是最小值，每次需要获取最小值时，只需要去堆顶取即可

借鉴 Java 中的优先队列，我们的堆只实现几个核心的 API

public MyPQ();                  // 默认构造函数
public MyPQ(int c);             // 带初始容量的构造函数
public void offer(int x);       // 插入一个元素 x
public int poll();              // 弹出堆顶元素
public int peek();              // 获取堆顶元素
public int size();              // 获取堆的大小

注意：本篇文章基于「小根堆」来实现的！！！

定义：当一棵二叉树的每个结点都大于等于它的两个子结点时，它被称为堆有序

根据定义可知，根结点是堆有序的二叉树中的最大结点

定义：二叉堆是一组能够用堆有序的完全二叉树排序的元素，并在数组中按照层级储存 (不使用数组的第一个位置)

根据定义可知，在一个堆中，位置 $k$$k$ 的结点的父结点的位置为 $\lfloor \frac{k}{2}\rfloor$$\left \lfloor \frac{k}{2} \right \rfloor$，而它的两个子结点的位置则分别为 $2k$$2k$ 和 $2k+1$$2k + 1$

我们用长度为N + 1的私有数组pq[]来表示一个大小为N的堆，我们不会使用pq[0]，堆元素放在pq[1]至pq[N]中

插入元素

每次插入一个新的元素时，首先将该元素放在数组的最后一个空位置，然后执行由下至上的堆有序化操作，即「上浮」

假设一个有序堆，如下图所示：

此时，插入一个新的元素4，如下图所示：

然后执行由下至上的堆有序化操作，如下图所示：

由下至上的堆有序化 (上浮) 的实现如下：

x
// k 是需要上浮的元素下标
private void up(int k) {
    // 未到根节点，且当前元素小于其父节点
    while (k > 1 && pq[k] < pq[k / 2]) {
        // 交换
        swap(k, k / 2);
        // k 上浮
        k >>= 1;
    }
}

删除元素

每次删除堆顶元素时，首先将该元素与最后一个元素交换，然后执行由上至下的堆有序化操作，即「下沉」

在上述有序堆的基础上删除堆顶元素，下图所示：

然后执行由上至下的堆有序化操作，如下图所示：

由上至下的堆有序化 (下沉) 的实现如下：

x
// k 是需要下沉的元素下标
private void down(int k) {
    // 未到最后一个元素
    while (2 * k <= size) {
        // 左孩子下标
        int j = 2 * k;
        // 选出左右孩子中最小的一个
        if (j < size && pq[j] > pq[j + 1]) j++;
        // 如果左右孩子中最小的还比当前节点大，则 break
        if (pq[k] < pq[j]) break;
        // 否则交换
        swap(k, j);
        // k 下沉
        k = j;
    }
}

算法模版

核心部分介绍完了，下面给出完整的代码模版：

xxxxxxxxxx
class MyPQ {
    private static final int CAPACITY = 11;
    private int[] pq;
    private int size;
    public MyPQ() {
        pq = new int[CAPACITY];
        size = 0;
    }
    public MyPQ(int c) {
        pq = new int[c + 1];
        size = 0;
    }
    public void offer(int x) {
        // 加到末尾，size + 1
        pq[++size] = x;
        // 上浮最后一个元素
        up(size);
    }
    public int poll() {
        // 记录堆顶元素
        int x = pq[1];
        // 交换
        swap(1, size--);
        // 下沉第一个元素
        down(1);
        return x;
    }
    public int peek() {
        return pq[1];
    }
    public int size() {
        return size;
    }
    private void up(int k) {
        while (k > 1 && pq[k] < pq[k / 2]) {
            swap(k, k / 2);
            k >>= 1;
        }
    }
    private void down(int k) {
        while (2 * k <= size) {
            int j = 2 * k;
            if (j < size && pq[j] > pq[j + 1]) j++;
            if (pq[k] < pq[j]) break;
            swap(k, j);
            k = j;
        }
    }
    private void swap(int i, int j) {
        int t = pq[i];
        pq[i] = pq[j];
        pq[j] = t;
    }
}