数据结构－二叉堆（C描述）

数据结构－二叉堆（C描述）2010-05-06 “子孑” 博客 1.主要的存储结构

struct HeapStruct
{
  int Capacity;//最大容量
  int Size;//当前容量
  ElementType *Elements;//数组入口地址
};
typedef struct HeapStruct *PriorityQueue;

结构体HeapStruct实际上是一个数组，二叉堆的底层实现是一个完全二叉树，因此可以很方便的使用数组实现。

完全二叉树的一个重要性质是可以明确给出父子之间的位置关系：

设节点v的秩为i（设根节点秩为0），则

若v有左子，左子的秩=2 * i + 1;

若v有右子，右子的秩=2 * i + 2;

若v有父亲，父亲的秩=（i - 1） / 2;

2.主要堆操作

为了维持堆序性，主要涉及的堆操作有两个，即插入与删除节点。

2.1插入节点-O（logN）

插入节点的算法为，

1.新节点插入堆尾。

2.循环比较该节点与它的父节点；

2.1若该节点<父节点，则交换之；

2.2否则，停止与当前位置，即为插入位置。

这个循环过程即为上滤过程。

这里设置一个哑元节点Element[0]，其中放入一个极小值，以便循环过程终止，这样做可以避免在循环体内多加一条判断语句。则现在堆顶为Element[1]，父子之间的位置关系：

设节点v的秩为i（设根节点秩为1），则

若v有左子，左子的秩=2 * i;

若v有右子，右子的秩=2 * i + 1;

若v有父亲，父亲的秩=i / 2;

/* H->Element[ 0 ] is a sentinel */
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;
}