ch11 优先队列

1. 完全二叉堆

【需求】若只需查找极值元，则不必维护所有元素之间的全序关系，偏序足矣。\(\tt BBST\) 的功能远远超出了需求，因此需要寻求一种更为简单、维护成本更低的实现方式，使得各功能接口的时间复杂度依然为 \(\cal{O}(\log n)\)，而且实际效率更高。

【结构性】逻辑上等同于完全二叉树，物理上直接借助向量实现。

【堆序性】处处满足 \(H[i] \le H[Parent(i)]\)，故 \(H[0]\) 即是全局最大者。

2. 左式堆

【NPL】引入所有的外部节点，消除一度节点，转为真二叉树。\(npl(\)\(\tt NULL\)\() = 0\)，\(npl(x) = 1 + \min\{npl(lc(x)), npl(rc(x))\}\)。\(npl(x)\) 等于 \(x\) 到外部节点的最近距离，也等于以 \(x\) 为根的最大满子树的高度。

【左倾性】对任何内节点 \(x\)，都有 \(npl(lc(x)) \ge npl(rc(x))\)，不难推出 \(npl(x) = 1 + npl(rc(x))\)。左倾性与堆序性，相容而不矛盾，左式堆的子堆，必是左式堆。左式堆倾向于更多节点分布于左侧分支。

【右侧链】\(rChain(x)\) 表示从节点 \(x\) 出发，一直沿右分支前进。特别地，\(rChain(r)\) 的重点，即全堆中最浅的外部节点，\(npl(r) = |rChain(r)| = d\)，存在一棵以 \(r\) 为根、高度为 \(d\) 的满子树。右侧链长为 \(d\) 的左式堆，至少包含 \(2^d -1\) 个内部节点，\(2^{d+1} -1\) 个节点。反之，包含 \(n\) 个节点的左式堆，右侧链长度 \(d\le \lfloor\log_2(n+1)\rfloor - 1 =\cal{O}(\log n)\)。

C++

template <typename T> 
class PQ_LeftHeap: public PQ<T>, public BinTree<T> {
public:
    T & getMax() { return _root->data; }
    void insert(T); T delMax(); //均基于统一的合并操作实现...

    PQ_LeftHeap( PQ_LeftHeap& A, PQ_LeftHeap& B ) {
        _root = merge( A._root, B._root ); 
        _size = A._size + B._size;A._root = B._root = NULL; 
        A._size = B._size = 0;
    }
};

// 合并算法
template <typename T> 
BinNodePosi<T> merge(BinNodePosi<T> a, BinNodePosi<T> b) {
    if (!a) return b;
    if (!b) return a;

    if (*a < *b) swap(a, b);    // 确保 a >= b

    for ( ; a->rc; a = a->rc)
        if (*(a->rc) < *b) {
            b->parent = a;
            swap(a->rc, b);
        }

    (a->rc = b))->parent = a;   // 将 a 的右子堆与 b 合并

    for ( ; a; b = a, a = a->parent) {
        if (!a->lc || (a->lc-npl < a->rc->npl)) // 若有必要
            swap(a->lc, a->rc);     // 交换 a 的左、右子堆，以确保左子堆的 npl 不小
        a->npl = a->rc ? 1 + a->rc->npl : 1;    // 更新 a 的 npl
    }

    return b;   // 合并后的堆顶
}

// 插入算法
template <typename T> 
void PQ_LeftHeap<T>::insert(T e) { //O(logn)
    _root = merge(_root, new BinNode<T>(e, NULL));
    _size++;
}

// 删除算法
template <typename T> 
T PQ_LeftHeap<T>::delMax() { //O(logn)
    BinNodePosi<T> lHeap = _root->lc; 
    if (lHeap) lHeap->parent = NULL; 

    BinNodePosi<T> rHeap = _root->rc; 
    if (rHeap) rHeap->parent = NULL;

    T e = _root->data;
    delete _root; 
    _size--;
    _root = merge( lHeap, rHeap);
    return e;
}