Heap

堆的实现就是一棵近似的完全二叉树，然后操作就是上浮和下沉，是相对比较简洁的数据结构

堆¶

堆是一个数组 (A)，可以被看作一个近似的完全二叉树，除了最底层外，树是完全充满的，而且是从左向右填充

A.length 数组元素的个数

A.heap-size 堆的有效元素

数组元素从1开始计数

即虽然A[1...length]可能都存有元素，但只有A[1..A.heap-size]存放的是堆的有效元素，树的根节点是A[0]

Parent(i) return i / 2;
Left(i) return 2 * i;
Right(i) return 2 * i + 1;

最大堆: 除了根以外的所有结点i都满足 $A[Parent(i)] \ge A[i]$
最小堆: 除了根以外的所有结点i都满足 $A[Parent(i)] \le A[i]$

堆有以下操作

MAX_HEAPIFY(vector<int>& A, int i); // A[i]的左右孩子都是最大堆，逐级下沉A[i]，保持堆的性质
BUILD_MAX_HEAP(); // 从无序的输入数组中构造出一个最大堆
HEAPSORT(); // 对一个数组进行原址排序
// 以下为利用堆实现一个优先级队列
MAX_HEAP_INSERT();
HEAP_EXTRACE_MAX();
HEAP_INCREASE_KEY();
HEAP_MAMIMUN();

6.2 维护堆的性质¶

MAX_HEAPIFY实现如下，从根上开始，每次和左右孩子中较大者比较，如果孩子大于它，就和孩子交换，然后递归进行，直到两个孩子都不大于大或不存在为止

void MAX_HEAPIFY(heap<T>& A, int i) {
    int l = Left(i), r = Right(i), largest = 0;
    if (l <= A.heap_size && A[l] > A[i]) largest = l;
    else largest = i;
    if (r <= A.heap_size && A[r] > A[largest]) largest = r;
    if (i != largest) {
        swap(A[i], A[largest]);
        MAX_HEAPIFY(A, largest);
    }
}

复杂度

每次迭代，在树底层半满的时候，子树最大，即由 $n$ 变成 $2/3n$

$T(n)\le T(2/3n)+O(1)$

由主方法， $log_b1=0$ ，即 $n^{log_ba}=\Theta(O(1))$ ，所以应用主方法第二种情况，复杂度为 $O(lgn)$

6.3 建堆¶

对于一个大小为 $n=A.length$ 的数组A[1..n]，从 $\lfloor n/2\rfloor+1$ 到 $n$ 都是叶子结点下标，因此要将一个数组建成堆，从 $\lfloor n/2\rfloor$ 一直到1都执行一下MAX_HEAPIFY即可

void Build_Max_Heap(heap<T>& A) {
    for (int i = A.length / 2; i >= 1; i --)
        MAX_HEAPIFY(A, i);
}

复杂度为 $O(n)$

如下图，从A[5]=16开始，逐个执行下沉，最后所得即最大堆

6.4 堆排序算法¶

利用堆对一个数组进行排序，即每次将最大元素A[1]换到末尾，然后将heap_size减一，重新执行MAX_HEAPIFY，重复n次后即得排序结果

复杂度为 $O(nlgn)$

void HEAPSORT(heap<T>& A) {
    for (int i = A.length; i >= 2; i --) {
        swap(A[0], A[i]);
        A.heap_size -= 1;
        MAX_HEAPIFY(A, 1);
    }
}

优先级队列¶

优先级队列是由一组元素构成的集合S，其中每个元素都有一个相关的值，叫关键字

一个最大优先级队列需要以下操作

Insert(S, x); // 把元素x插入到集合S中
Maximum(S); // 返回集合S中的最大元素
Extract_Max(S); // 去掉并返回S中具有最大关键字的元素
Increase_Key(S, x, k); // 将元素x的关键字增加到k，这里k要不小于x的关键字值

利用最大堆可以这样实现这些接口

T Maximum(const heap<T>& A) {
    return A[1];
}

要弹出最大值，把末尾元素放到堆顶，然后堆大小减一，执行下沉即可

void Extract_Max(heap<T>& A) {
    if (A.heap_size < 1) error("heap underflow");
    T max = A[1];
    A[1] = A[A.heap_size];
    A.heap_size --;
    Max_Heapify(A, 1);
    return max;
}

Increase_Key这里增加一个元素的值后，一定比其孩子的值更大，所以就检查是否需要和Parent交换即可

void Increase_Key(Heap<T>& A, int i, T key) {
    if (key < A[i]) error("new key is smaller than current key");
    A[i] = key;
    while (i > 1 && A[Parent(i)] < A[i]) {
        swap(A[i], A[Parent(i)]);
        i = Parent(i);
    }
}

在此基础上，就可以实现Insert，即把要插入的元素放在最后，然后上浮该元素即可

void Insert(Heap<T>& A, T key) {
    A.heap_size ++;
    A[A.heap_size] = std::numeric_limits<T>::min();
    Increase_Key(A, A.heap_size, key);
}

STL里的heap (algorithm库)¶

make_heap(v.begin(), v.end());
push_heap(v.begin(), v.end());
pop_heap(v.begin(), v.end());
sort_heap(v.begin(), v.end());

std::priority_queue¶

小顶堆

小顶堆用的是greater比较，push时对加入容器末尾的元素进行上溯，每次cmp(father, son)，如果成立则将son上溯，因此greater对应

std::priority_queue<int, std::vector<int>, std::greater<int>> pq;

大顶堆

std::priority_queue<int, std::vector<int>, std::less<int>> pq;

主要有以下函数

p.push(T value);
p.pop();
p.top();
p.empty();
p.size();