第6章 优先队列（堆）

具有特殊优先级的队列叫做优先队列。像操作系统中，调度算法往往会使用优先队列结构。优先队列至少允许下列两种操作：insert，deleteMin（找出、返回和删除优先队列中的最小项）。

---

二叉堆

二叉堆又叫做堆。下面将讨论其结构性质和堆序性质。

（1）结构性质

二叉堆是一棵被完全填满的二叉树（即完全二叉树），可能的例外是在底层，底层元素从左到右填入。如下：

因为完全二叉树很有规律，所以可以用一个数组表示而不需要使用链。因为对于数组中任意位置 i 上的元素，其左儿子在位置 2i 上，右儿子在左儿子后的单元（2i + 1）中，它的父亲则在位置  上。

上图的数组存储如***意是从下标为 1 的位置存储第一个元素）：

如下是优先队列（堆）的整体接口：

template<typename Comparable>
class BinaryHeap
{
public:
    explicit BinaryHeap(int capacity = 100);
    explicit BinaryHeap(const vector<Comparable> & items);

    bool isEmpty() const;
    const Comparable & findMin() const;

    void insert(const Comparable & x);
    void deleteMin();
    void deleteMin(Comparable & minItem);
    void makeEmpty();

private:
    int currentSize;    //堆中元素的个数
    vector<Comparable> array;   //存放堆的数组

    void buildHeap();
    void percolateDown(int hole);
};

（2）堆序性质

使操作可以快速执行的性质即是堆序性质。由于要快速的找到最小元，因此最小元应该在根上。如果任意子树也是堆，那么任意结点就应该小于它的所有后裔。

• 插入操作：insert

插入操作使用一种叫做上滤的策略，新元素在堆中上滤直到找出正确的位置。如将一个元素 X 插入到堆中，我们在下一个空闲的位置创建一个空穴，因为否则该堆将不是完全树。如果 X 可以放在空穴中而并不破坏堆序，那么插入完成。否则把空穴的父结点上的元素移入空穴中，这样空穴就朝着根的方向上行一步。继续该过程直到 X 能被放入空穴中为止。所以最好的时间 O(1)，最坏为 O(logN)。

    void insert(const Comparable & x)
    {
        if(currentSize == array.size()-1)
            array.resize(array.size()*2);
        
        //上滤
        int hole = ++currentSize;
        for( ; hole>1 && x<array[hole/2]; hole/=2)
            array[hole] = array[hole/2];
        
        array[hole] = x;
    }

如下是一个插入过程：

• deleteMin操作

该操作使用一种叫做下滤的策略。当删除一个最小元时，要在根结点建立一个空穴。由于现在堆少了一个元素，因此堆中最后一个元素 X 必须移动到该堆的某个地方。如果 X 可以被放到空穴中，那么 deleteMin 完成。否则我们将空穴的两个儿子中的较小者移入空穴，这样就把空穴向下推了一层。重复该步骤直到 X 可以被放入空穴。所以最坏为 O(logN)。

    //删除最小元素
    void deleteMin()
    {
        if(isEmpty())
            throw UnderflowException();

        //下标为 1 的位置是堆的起始位置
        array[1] = array[currentSize--];
        percolateDown(1);
    }
    //删除最小元素，放入 minItem 中
    void deleteMin(Comparable & minItem)
    {
        if(isEmpty())
            throw UnderflowException();

        minItem = array[1];
        array[1] = array[currentSize--];
        percolateDown(1);
    }

    //下滤， hole 是下滤的起始位置
    void percolateDown(int hole)
    {
        int child;
        Comparable tmp = array[hole];
        
        for( ; hole*2 <= currentSize; hole = child)
        {
            child = hole * 2;
            if(child != currentSize && array[child + 1] < array[child])
                child++;    //换成右子树
            
            if(array[child] < tmp)
                array[hole] = array[child];
            else
                break;
        }
        
        array[hole] = tmp;
    }

如下是一个删除最小值过程：

• 初始操作：buildHeap

这种操作有两种方法，一种是对每个元素进行 insert 操作，因为插入最好的时间 O(1)，最坏为 O(logN)，所以这种最好时间为 O(N)，最坏 O(NlogN)。一种是将 N 个元素以任意顺序放入树中，然后下滤非叶结点。由于非叶结点一般为  ，所以最坏的情况下下滤总次数为：，h 为高度。可以知道这个值为 ，而 N 的最大值：，所以这种构造的时间为 O(N)。

    explicit BinaryHeap(const vector<Comparable> & items)
        : array(items.size()+10), currentSize(items.size())
    {
        for(int i=0; i<items.size(); i++)
            array[i+1] = items[i];
        buildHeap();
    }

    void buildHeap()
    {
        for(int i=currentSize/2; i>0; i--)
            percolateDown(i);
    }

---

d堆

d 堆与二叉堆很像，但其所有的结点都有 d 个儿子，因此二叉堆记为 2 堆。

因为有很多情形是插入比删除操作多得多，这种树就派上用场了。d 堆将 insert 操作运行时间改为 O()，然而对于 deleteMin 操作，因为要进行 d-1 次比较，所以时间为 O()。而且找到儿子和父亲的乘法和除法都有个因子 d ，除非 d 是 2 的幂，不然不能通过二进制的移位来实现除法而导致运行时间急剧增加。

如下是一个 3 堆：

---

左式堆

由于二叉堆的合并操作是比较困难的操作，所以这是一种方便合并操作的堆。我们把任意一个结点 X 的零路径长（null path length）npl(X) 规定为从 X 到一个不具有两个儿子的结点的最短路径的长。具有 0 个或 1 个儿子结点的 npl 为 0，而 npl(NULL) = -1 ，如下为两棵树的 npl 情况。

   

可以发现，任意结点的零路径长比它的诸儿子结点的零路径长的最小值多 1。这也适用于少于两个儿子的结点，因为 null 的零路径长是 -1。

左式堆：对于堆中的每一个结点 X，左儿子的零路径长至少与右儿子的零路径长一样大。对于左式堆，X 结点的零路径长度等于右儿子的零路径长度加 1。

因为左式堆趋向于加深左路径，所以右路径应该短，事实上沿左式堆右侧的右路径确实是该堆中最短路径。否则，就会存在一条路径通过某个结点 X ，取得左儿子（可能为空）的零路径长度小于右儿子的零路径长度。

定理：在右路径上有 r 个结点的左式树必然至少有 个结点。

该定理说明，N 个结点的左式树有一条右路径最多含有 个结点。

下面是是实现：

方法一：合并操作（merge）采用递归操作

#ifndef LeftistHeap_H
#define LeftistHeap_H

#include <queue>
using namespace std;

template<typename Comparable>
class LeftistHeap
{
public:
    explicit LeftistHeap()
    {
        root = NULL;
    }
    explicit LeftistHeap(const vector<Comparable> & items)
    {
        for(int i=0; i<items.size(); i++)
        {
            LeftistHeap *heap = new LeftistHeap();
            heap->insert(items[i]);
            que.push(heap);
        }
        buildHeap();
    }

    bool isEmpty() const
    {
        if(root == NULL)
            return true;
        else
            return false;
    }

    //C++中千万不能返回局部对象的引用，因为返回引用之前已被析构
    const Comparable & findMin() const
    {
        if(isEmpty())
            throw UnderflowException();
        return root->element;
    }

    void insert(const Comparable & x)
    {
        //插入操作变为一个结点和该堆的合并
        root = merge(new LeftNode(x), root);
    }

    //删除最小元素
    void deleteMin()
    {
        if(isEmpty())
            throw UnderflowException();

        LeftNode *oldRoot = root;
        root = merge(root->left, root->right);
        delete oldRoot;
    }
    //删除最小元素，放入 minItem 中
    void deleteMin(Comparable & minItem)
    {
        if(isEmpty())
            throw UnderflowException();

        minItem = findMin();
        deleteMin();
    }
    void makeEmpty();

    //合并 rhs堆 到本堆
    void merge(LeftistHeap & rhs)
    {
        if(this == &rhs)
            return;

        root = merge(root, rhs.root);
        rhs.root = NULL;
    }

    const LeftistHeap & operator=( const LeftistHeap & rhs);

private:
    struct LeftNode
    {
        Comparable  element;
        LeftNode *  left;
        LeftNode *  right;
        int         npl;
        LeftNode( const Comparable &theElement, LeftNode *lt = NULL,
                  LeftNode *rt = NULL, int np = 0)
            :element(theElement), left(lt), right(rt), npl(np){}
    };

    LeftNode *root;
    queue<LeftistHeap *> que;   //存放堆的队列

    LeftNode * merge(LeftNode *h1, LeftNode *h2)
    {
        if(h1 == NULL) return h2;
        if(h2 == NULL) return h1;
        if(h1->element < h2->element)
            return merge1(h1, h2);
        else
            return merge1(h2, h1);
    }

    //内部合并函数，h1->element < h2->element
    LeftNode * merge1(LeftNode *h1, LeftNode *h2)
    {
        if(h1->left == NULL)    //一个结点的堆的合并
            h1->left = h2;
        else
        {
            h1->right = merge(h1->right, h2);   //h1 左结点非空就合并右结点和 h2
            if(h1->left->npl < h1->right->npl)  //每层递归操作完成后检查该层根结点孩子的零路径长度
                swapChildren(h1);   //不符合左式堆的时候就交换左右孩子
            h1->npl = h1->right->npl + 1; //根结点 npl = min_npl(h1->left, h1->right) + 1,
                                          //但是左式堆的左结点的npl一定大于或等于右结点
        }
    }

    void swapChildren(LeftNode *t)
    {
        LeftNode *tmp = t->left;
        t->left = t->right;
        t->right = tmp;
    }
    void reclaimMemory(LeftNode *t)
    {
        if(t)
            delete t;
    }
    LeftNode * clone(LeftNode *t) const
    {
        LeftNode *node = new LeftNode(t->element,
                                      t->left, t->right, t->npl);
        return node;
    }

    void buildHeap()
    {
        while (que.size() > 1) {
            LeftistHeap *h1 = que.front();
            que.pop();
            LeftistHeap *h2 = que.front();
            que.pop();
            h1->merge(h2);
            que.push(h1);
        }
        LeftistHeap *heap = que.front();
        que.pop();
        this->merge(heap);
    }
};

#endif // LeftistHeap_H

步骤如下：

方法二：合并操作（merge）非递归

先通过合并两个堆的右路径建立一棵新的树，如下

我们可以看到右路径以排序的方式安排，且保持它们各自的左儿子不变。然后交换该路径上左式堆性质被破坏的结点的两个儿子。这就是非递归实现的方法。因为可能由于结点很多，而导致递归实现缺乏栈空间，所以该方法适合于大型数据堆合并。

递归的方法的合并操作的时间与右路径的长成正比，合并两个左式堆的时间界为 O(logN)。同理插入，删除都是 O(logN)。

---

斜堆

首先，斜堆是具有堆序性质的二叉树，但是没有树的结构限制。而左式堆也是具有堆序性质的二叉树，但是要求 npl(leftChild) >= npl(rightChild)。所以不用保留结点的 npl 信息。除此之外，和左式堆没有区别。斜堆的右路径可以任意长。斜堆的基本操作也是合并（merge），只不过交换孩子结点是每次递归操作后都有的。看下面的代码

    //内部合并函数，h1->element < h2->element
    LeftNode * merge1(LeftNode *h1, LeftNode *h2)
    {
        if(h1->left == NULL)    //一个结点的堆的合并
            h1->left = h2;
        else
        {
            h1->right = merge(h1->right, h2);   //h1 左结点非空就合并右结点和 h2
            swapChildren(h1);  //每层递归操作完成后就交换左右孩子
        }
    }

我们会发现，每个子树的右路径的所有结点的最大者不交换左右儿子，这是因为它的右儿子必定为空。这也是由这段代码决定的，因为我们的合并操作，总是先考虑到左孩子是否为空，为空就放在左边，所以不存在这样的结点它只有右孩子。所以右路径的最大结点要么没有孩子，要么只有左孩子。没有孩子时最后执行 “h1->left = h2” 跳出递归，有左孩子时，交换后，那么右路径最大结点变为其原来的左孩子，它是没有孩子结点的，当然也符合上面的结论。

 

斜堆的插入、删除、合并也是 O(logN)。

---

二项队列