二叉堆（binary heap）—— 优先队列的实现

二叉堆因为对应着一棵完全二叉树，因而可以通过线性数组的方式实现。

注意，数组第 0 个位置上的元素，作为根，还是第 1 个位置上的元素作为根？
- 本文给出的实现，以数组第 1 个位置上的元素作为根，则其两个孩子 ⇒ 2*i, 2*i+1
- 而第 0 个位置上的元素，则用来作为标志变量（Size 不包括此变量）；
在元素逐个插入的过程中（插入在合适的位置），实现二叉堆的构建；自然删除也需按着指定的规则；

1. 声明

struct HeapStruct;

typedef struct HeapStruct* PriorityQueue;

PriorityQueue Init(int MaxElements);

...

void Insert(ElementType X, PriorityQueue PQ);

ElementType DeleteMin(PriorityQueue PQ);

2. 实现

struct HeapStruct {

    int Capacity;

    int Size;

    ElementType* Elements;

};

PriorityQueue Init(int MaxElements){

    PriorityQueue PQ;

    PQ = (PriorityQueue)malloc(sizeof(struct HeapStruct));

    if (!PQ) ....

    PQ->Elements = (ElementType)malloc(MaxElements*sizeof(ElementType));

    if (!PQ) ...

    PQ->Capacity = MaxElements;

    PQ-Size = 0;

    PQ->Elements[0] = INT_MIN;

}

void Insert(ElementType X, PriorityQueue PQ) {

    if (IsFull(PQ)) ...

    for (int i = ++PQ->Size; PQ->Elements[i/2] > X; i /= 2) {

        PQ->Elements[i] = PQ->Elements[i/2];

    }

    PQ->Elements[i] = X;

}

比较困难的是删除时，二叉堆结构在线性数组上的维持：

ElementType DeleteMin(PriorityQueue PQ) {

    if (IsEmpty(PQ)) ...

    ElementType MinElement, LastElement;

    MinElement = PQ->Elements[1];

    LastElement = PQ->Elements[PQ->Size--];

    int Child;

    for (int i = 1; i*2 <= PQ->Size; ++i) {

        Child = 2*i;

        if (Child != PQ->Size && PQ->Elements[Child+1] < PQ->Elements[Child])

            Child = Child + 1;

        if (PQ->Elements[Child] < LastElement)

            PQ->Element[i] = PQ->Elements[Child];

        else

            break;

    }

    PQ->Elements[i] = LastElement;

    return MinElement;

}

巴特西

二叉堆（binary heap）—— 优先队列的实现

1. 声明

2. 实现

最新文章

热门文章