优先队列（堆）

为什么需要优先队列？

队列是一种先进先出的表ADT，正常来说，先入队的元素，会先出队，意味没有那个元素是特殊的，拥有“插队”的优先权。这种平等，并不试用所有场景。有时，我们希望队列中某类元素拥有比其他元素更高的优先级，以便能提前得到处理。因此，我们需要有一种新的队列来满足这样的应用，这样的队列叫做“优先队列（priority queue）”。

优先队列模型

优先队列允许至少两种操作：Insert(插入) ，以及 DeleteMin(删除最小者)。Insert 操作等价于 Enqueue(入队)，而 DeleteMin 则是队列中 Dequeue(出队) 在优先队列中的等价操作。DeleteMin 函数也变更它的输入。

简单实现

单链表

在表头以执行插入操作，并遍历该链表以删除最小元，这又需要时间。另一种做法是，始终让表保持排序状态；这使得插入代价高昂（）而DeleteMin花费低廉（）。基于DeleteMin的操作次数从不多于插入操作次数的事实，前者也许是更好的办法。

二叉查找树

使用二叉查找树，Insert 和 DeleteMin 这两种操作的平均运行时间都是。

二叉堆（binary heap）

实现优先队列更加普遍的方法是二叉堆，以至于当堆(heap)这个词不加修饰地使用时一般都是指该数据结构(优先队列)的这种实现。因此，我们单独说堆时，就是指二叉堆。同二叉查找树一样，堆也有两个性质，即结构性和堆序性。正如AVL树一样，对堆的一次操作可能破坏这两个性质的一个，因此，堆的操作必须要到堆的所有性质都被满足时才能终止。事实上这并不难做到。

结构性质

堆是一棵被完全填满的二叉树，有可能的例外是在底层，底层上的元素从左到右填入。这样的树称为完全二叉树（complete binary tree）。因为完全二叉树很有规律，所以它可以用一个数组表示而不需要指针。对于数组任意位置上的元素，其左儿子在位置上，右儿子在左儿子后的单元上，它的父亲则在位置上。因此，不仅指针这里不需要，而且遍历该树所需要的操作也极简单，在大部分计算机上运行很可能非常快。

一个堆数据结构由一个数组，一个代表最大值的整数以及当前的堆大小组成。

优先队列声明：

#ifndef _BinHeap_H

struct HeapStruct;
typedef struct HeapStruct *PriorityQueue;

PriorityQueue Initialize(int MaxElements);
void Destroy(PriorityQueue H);
void MakeEmpty(PriorityQueue H);
void Insert(ElementType X, PriorityQueue H);
ElementType DeleteMin(PriorityQueue H);
ElementType FindMin(PriorityQueue H);
int IsEmpty(PriorityQueue H);
int IsFull(PriorityQueue H);

#endif

struct HeapStruct
{
    int Capacity;
    int Size;
    ElementType *Elements;
}

堆序性质

使操作被快速执行的性质是堆序(heap order)性。由于我们想要快速地找出最小元，因此，最小元应该在根上。如果我们考虑任意子树也应该是一个堆，那么任意节点就应该小于它的所有后裔。

PriorityQueue
Initialize(int MaxElements)
{
    PriorityQueue H;

    if (MaxElements < MinPQSize)
        Error("Priority queue size is too small");

    H = malloc(sizeof(struct HeapStruct));
    if (H == NULL)
        FatalError("Out of space!!!");

    H->Elements = malloc((MaxElements + 1)
                         * sizeof(ElementType));

    if (H->Elements == NULL)
        FatalError("Out of space!!!");

    H->Capacity =  MaxElements;
    H->Size = 0;
    H->Elements[0] = MinData;

    return H;
}

根据堆序性质，最小元总是可以在根处找到。因此，我们以常数时间完成附加运算FinMin。

基本操作

Insert (插入)

void
Insert(ElementType X, PriorityQueue H)
{
    int i;

    if (IsFull(H))
    {
        Error("Priority queue is full");
        return;
    }
    for (i = ++H->Size; H->Elements[i / 2] > X; i /= 2)
        H->Elements[i] = H->Elements[i / 2];
    H->Elements[i] = X;
}

DeleteMin (删除最小元)

ElementType
DeleteMin(PriorityQueue H)
{
    int i, Child;
    ElementType MinElement, LastElement;

    if (IsEmpty(H))
    {
        Error("Priority queue is empty");
        return H->Elements[0];
    }
    MinElement = H->Elements[1];
    LastElement = H->Elements[H->Size--];

    for(i = 1; i * 2 <= H->Size; i = Child)
    {
        Child = i * 2;
        if (Child != H->size && H->Elements[Child + 1]
                              < H->Elements[Child])
            Child++;

        if (LastElement > H->Elements[ Child ])
            H->Elements[i] = H->Elements[Child];
        else
            break;
    }
    H->Elements[i] = LastElement;
    return MinElement;
}

优先队列的应用

  • 操作系统设计：进程调度
  • 图论算法
  • 选择问题：从N个元素中找出第k个最大的元素
  • 事件模拟