堆排序与优先队列

【注】参考自教材「算法导论」。

1. 堆

1.1 定义

（二叉）堆物理上是一个数组，逻辑上是一棵完全二叉树，树上的每一个结点对应数组中的一个元素。
设表示堆的数组 $A$，其包含两个属性：

1. $A.length$ 给出数组元素的个数。
2. $A.heapsize$ 给出有多少个堆元素存储在该数组中。

1.2 性质

从根结点编号为 1 开始，同一深度的结点自左往右、不同深度的结点自上往下，对堆上的结点编号（即逐层从左往右进行编号），结点编号对应数组 $A$ 中元素的下标。

• $n$ 个元素的堆的高度为 $\lfloor \lg n \rfloor$ 。

证明
  因为堆是一棵完全二叉树，设堆高为 $h$，则

$$\begin{array}{c} 2^h \leq n \leq 2^{h+1} - 1 \Rightarrow \lg (n+1) - 1 \leq h \leq \lg n \\ \Rightarrow \lg n - 1 \lt \lg (n+1) - 1 \leq h \leq \lg n \end{array}$$

因为 $h$ 为整数，故 $h = \lfloor \lg n \rfloor$ 。

• 非根结点 $i$ 的双亲结点的编号为

$$\begin{array}{c} parent[i] = \lfloor i/2 \rfloor \end{array}$$

• 非叶结点 $i$ 的左右孩子结点编号分别为

$$\begin{array}{c} left[i] = 2i \\ right[i] = 2i + 1 \end{array}$$

• 当用数组表示存储 $n$ 个元素的堆时，叶结点编号分别是 $\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots, n$ 。

证明
  因为 $n$ 是编号最大的结点，故 $n$ 肯定是叶结点，且是编号最大的叶结点。故 $n$ 的双亲 $parent[n] = \lfloor n/2 \rfloor$ 也是编号最大的非叶结点。故区间 $(parent[n], n]$ 范围内的结点编号都是叶结点。即 $\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots, n$ 。

• 对于包含 $n$ 个元素的堆最多包含 $\lceil n/2^{h+1} \rceil$ 个高度为 $h$ 的结点。

证明
归纳法证明如下：

• 对于高度为 0 的结点（即叶结点），因为堆是一棵完全二叉树，故叶结点个数 $l$ 满足 $l_0 = \lfloor (n+1)/2 \rfloor = \lceil n/2^{0 + 1} \rceil$ 。
• 假设对于高度为 $h$ 的结点，满足结点数 $l_h = \lceil n/2^{h+1} \rceil$，由于堆是一棵完全二叉树，故对于高度为 $h+1$ 的结点，有

$$\begin{array}{c} l_{h+1} = \lceil l_h / 2 \rceil = \lceil n / 2^{(h+1)+1} \rceil \end{array}$$

堆可分为最大堆和最小堆，二者分别满足最大堆性质和最小堆性质。

• 最大堆性质：除了根结点以外的所有结点 $i$ 满足

$$\begin{array}{c} A[parent(i)] \geq A[i] \end{array}$$

• 最小堆性质：除了根结点以外的所有结点 $i$ 满足

$$\begin{array}{c} A[parent(i)] \leq A[i] \end{array}$$

2. 堆排序

堆排序是原址的、不稳定的。以下仅以最大堆为例。

2.1 maxHeapify

该过程用于维护最大堆性质。即根据输入的结点 $i$ 维护以 $i$ 为根的堆的最大堆性质。

// 伪代码
maxHeapify(A, i) {
    l = left(i)     // 左孩子结点
    r = right(i)    // 右孩子结点
    largest = i     // 记录左孩子、右孩子、根三者中值最大的一者
    if l ≤ A.heapsize and A[l] > A[largest]
        largest = l
    if r ≤ A.heapsize and A[r] > A[largest]
        largest = r
    if largest != i
        swap(A[i], A[largest])
        maxHeapify(A, largest)
}

由于堆高为 $\lfloor \lg n \rfloor$，故 maxHeapify 复杂度为 $O(\lg n)$ 。

2.2 buildMaxHeap

采用自底向上的方法，利用 maxHeapify 过程，将数组 A 构建为一棵最大堆。即从最小的非空子树（内部结点）开始，由于最小非空子树最少两个元素、最多三个元素，故 maxHeapify 后一定是一棵最大堆，然后逐步向上对更大的子树递归利用 maxHeapify 构建最大堆。
根据上文堆的性质可知，堆的叶结点编号分别是 $\lfloor n/2 \rfloor + 1, \lfloor n/2 \rfloor + 2, \cdots, n$ ，故非叶结点的编号为 $1,2, \cdots, \lfloor n/2 \rfloor$ 。

// 伪代码
buildMaxHeap(A) {
    A.heapsize = A.length
    for i = ⌊A.heapsize/2⌋ downto 1 
        maxHeapify(A, i)
}

因为在高度为 $h$ 的树上执行 maxHeapify 过程的复杂度为 $O(h)$，而由上文堆的性质可知，堆中高度为 $h$ 的结点数为 $\lceil n/2^{h+1} \rceil$，堆的高度为 $\lg n$，故 buildMaxHeap 的复杂度为

$$\begin{array}{c} \sum^{\lfloor \lg n \rfloor}_{h = 0}\lceil n/2^{h+1} \rceil O(h) = O(n) \end{array}$$

2.3 heapSort

构建好最大堆后，值最大的元素在 A[1]，通过将 A[1] 与 A[A.heapsize] 交换后，然后缩小 A.heapsize，并使用 maxHeapify 过程维护最大堆性质。如此往复，直到 A.heapsize = 2 时，数组 A 变为有序。

// 伪代码
heapSort(A) {
    buildMaxHeap(A)
    for i = A.length downto 2
        swap(A[1], A[i])
        A.heapsize = A.heapsize - 1
        maxHeapify(A, 1)
}

heapSort 的复杂度为 $O(n + \lfloor \lg n \rfloor + \lfloor \lg (n-1) \rfloor + \cdots + \lfloor \lg 1 \rfloor) = O(n + \lg n!) = O(n\lg n)$ 。

2.4 模板

#include <bits/stdc++.h>
using namespace std;

// 比较函数
template <typename T>
bool compare(const T & t1, const T & t2) {
    return t1 < t2;
}
// 最大堆
template <typename T>
struct MaxHeap {
    #ifndef _MAXHEAP_ 
    #define _MAXHEAP_
    #define ll long long
    #endif
    ll length;
    ll heapsize;
    MaxHeap() {}
    // 维护最大堆性质
    void maxHeapify(T *A, ll i, bool (*cmp)(const T &, const T &)) {
        ll l = 2*i, r = 2*i + 1;
        ll largest = i;
        if(l <= heapsize && cmp(A[largest], A[l])) {
            largest = l;
        }
        if(r <= heapsize && cmp(A[largest], A[r])) {
            largest = r;
        }
        if(largest != i) {
            swap(A[i], A[largest]);
            maxHeapify(A, largest, cmp);
        }
    }
    // 构建最大堆
    void buildMaxHeap(T *A, bool(*cmp)(const T &, const T &)) {
        heapsize = length;
        for(ll i = heapsize/2; i; --i) {
            maxHeapify(A, i, cmp);
        }
    }
    // 堆排序
    void heapSort(T *bA, T *eA, bool(*cmp)(const T &, const T &) = compare) {
        T *A = bA - 1;
        length = eA - bA;
        buildMaxHeap(A, cmp);
        for(ll i = length; i; --i) {
            swap(A[1], A[i]);
            heapsize--;
            maxHeapify(A, 1, cmp);
        }
    }
};

3. 优先队列

以下优先队列以最大堆为底层实现。

3.1 maxHeapifyUp

该过程用于从当前结点向根结点的路径上维护最大堆性质。

// 伪代码
maxHeapifyUp(A, i) {
    p = parent(i)   // 双亲结点
    if p > 0 and A[p] < A[i]
        swap(A[i], A[p])
        maxHeapifyUp(A, p)
}

由于堆高为 $\lfloor \lg n \rfloor$，故 maxHeapifyUp 复杂度为 $O(\lg n)$ 。

3.2 maxHeapifyDown

该过程用于从当前结点向叶结点的路径上维护最大堆性质。

// 伪代码
maxHeapifyDown(A, i) {
    l = left(i)     // 左孩子结点
    r = right(i)    // 右孩子结点
    largest = i     // 记录左孩子、右孩子、根三者中值最大的一者
    if l ≤ A.heapsize and A[l] > A[largest]
        largest = l
    if r ≤ A.heapsize and A[r] > A[largest]
        largest = r
    if largest != i
        swap(A[i], A[largest])
        maxHeapifyDown(A, largest)
}

由于堆高为 $\lfloor \lg n \rfloor$，故 maxHeapifyDown 复杂度为 $O(\lg n)$ 。

3.3 模板

#include <bits/stdc++.h>
using namespace std;

#ifndef _PRIORITYQUEUE_
#define _PRIORITYQUEUE_
#define ll long long
#define MAXN 1000005

// 比较元素
template < typename T >
struct Compare {
    bool operator () (const T & a, const T & b) {
        return a < b;
    }
};
// 优先队列
template < typename T, typename F = struct Compare <T> >
struct PriorityQueue {
    ll heapsize;
    T A[MAXN];
    F compare;
    typedef T* iterator;
    // 构造函数
    PriorityQueue(): heapsize(0) {}
    // 向上维护最大堆性质
    void maxHeapifyUp(ll i) {
        ll p = i/2;
        if(p && compare(A[p], A[i])) {
            swap(A[p], A[i]);
            maxHeapifyUp(p);
        }
    }
    // 向下维护最大堆性质
    void maxHeapifyDown(ll i) {
        ll l = 2*i, r = 2*i + 1;
        ll largest = i;
        if(l <= heapsize && compare(A[largest], A[l])) {
            largest = l;
        }
        if(r <= heapsize && compare(A[largest], A[r])) {
            largest = r;
        }
        if(largest != i) {
            swap(A[i], A[largest]);
            maxHeapifyDown(largest);
        }
    }
    // 将元素压入优先队列中
    void push(T a) {
        A[++heapsize] = a;
        maxHeapifyUp(heapsize);
    }
    // 将元素弹出优先队列外
    T pop() {
        swap(A[1], A[heapsize]);
        --heapsize;
        maxHeapifyDown(1);
        return A[heapsize+1];
    }
    // 获取优先队列顶部元素
    T top() {
        return A[1];
    }
    // 获取优先队列大小
    ll size() {
        return heapsize;
    }
    // 判断优先队列是否为空
    bool empty() {
        return !heapsize;
    }
    // 清空优先队列
    void clear() {
        heapsize = 0;
    }
    // 获取优先队列首元素
    T* begin() {
        return &A[1];
    }
    // 获取优先队列尾元素
    T* end() {
        return &A[heapsize] + 1;
    }
};
#endif