數據結構－二叉堆(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;
}

2.2 刪除節點-O(logN)

刪除節點的算法為，

1.刪除堆頂元素，將堆中最末的一個節點置於堆頂。

2.置當前節點為堆頂，循環比較當前節點與它的兩個孩子節點；

2.1 若當前節點>它較小的那個孩子，則交換之，繼續比較該節點與它下一層的孩子；

2.2否則，退出循環，比較結束。

這個循環過程即為下濾過程。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 )
　　　　{
　　　　　　　　/* Find smaller child */
　　　　　　　　Child = i * 2;
　　　　　　　　if( Child != H->Size && H->Elements[ Child + 1 ] < H->Elements[ Child ] )
　　　　　　　　　　　　Child++;
　　　　　　　　/* Percolate one level */
　　　　　　　　if( LastElement > H->Elements[ Child ] )
　　　　　　　　　　　　H->Elements[ i ] = H->Elements[ Child ];
　　　　　　　　else
　　　　　　　　　　　　break;
　　　　}
　　　　H->Elements[ i ] = LastElement;
　　　　return MinElement;
}

3.完整的ADT與實現

binheap.h

typedef int ElementType;
#ifndef BINHEAP_H_INCLUDED
#define BINHEAP_H_INCLUDED
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 // BINHEAP_H_INCLUDED
　　
binheap.c
#include "binheap.h"
#include "../lib/fatal.h"
#include <stdlib.h>
#define MinPQSize 10
#define MinData -32767
struct HeapStruct
{
　　　　int Capacity;
　　　　int Size;
　　　　ElementType *Elements;
};
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!!!" );
　　　　/* Allocate the array plus one extra for sentinel */
　　　　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;
}
void MakeEmpty( PriorityQueue H )
{
　　　　H->Size = 0;
}
/* 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;
}
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 )
　　　　{
　　　　　　　　/* Find smaller child */
　　　　　　　　Child = i * 2;
　　　　　　　　if( Child != H->Size && H->Elements[ Child + 1 ] < H->Elements[ Child ] )
　　　　　　　　　　　　Child++;
　　　　　　　　/* Percolate one level */
　　　　　　　　if( LastElement > H->Elements[ Child ] )
　　　　　　　　　　　　H->Elements[ i ] = H->Elements[ Child ];
　　　　　　　　else
　　　　　　　　　　　　break;
　　　　}
　　　　H->Elements[ i ] = LastElement;
　　　　return MinElement;
}
ElementType FindMin( PriorityQueue H )
{
　　　　if( !IsEmpty( H ) )
　　　　　　　　return H->Elements[ 1 ];
　　　　Error( "Priority Queue is Empty" );
　　　　return H->Elements[ 0 ];
}
int IsEmpty( PriorityQueue H )
{
　　　　return H->Size == 0;
}
int IsFull( PriorityQueue H )
{
　　　　return H->Size == H->Capacity;
}
void Destroy( PriorityQueue H )
{
　　　　free( H->Elements );
　　　　free( H );
}

本文出自 “子 孑” 博客，請務必保留此出處http://zhangjunhd.blog.51cto.com/113473/102384