数据结构－二叉堆(C描述)

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;
}