优先队列 - 堆

1. 一些简单的实现
    a.  可以用链表，在头以O(1)执行插入操作，并遍历该链表删除最小的元素，这需要O(n)的时间。或者是链表始终保持排序状态，插入的时间花费O(N)，而删除最小元素需要的时间为O(1)。删除的操作次数不多于插入操作次数，应此前一种结构更好。
    b. 二叉查找树， 删除和插入操作的时间都为O(logN)。但是会破坏树的平衡性。
2. 二叉堆
   a.  堆是一棵完全二叉树(complete binary tree)， 有可能的例外在底层，底层上的元素从左到右填入。
   b. 一棵高为h的完全二叉树有2^h到2^h+1 - 1节点。这意味着完全二叉树的高是log(N)。
   c. 可以用一个数组把二叉堆映射到数组里面，i任意位置， 其左儿子是2i，右儿子是2i + 1。数组的0空着，放入最小的数据，例如MIN_INT。

// binheap.h

        typedef int ElementType;

/* START: fig6_4.txt */
        #ifndef _BinHeap_H
        #define _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

/* END */

// fatal.h

#include <stdio.h>
#include <stdlib.h>

#define Error( Str ) FatalError( Str )
#define FatalError( Str ) fprintf( stderr, "%s\n", Str ), exit( 1 )

// binheap.cpp

        #include "binheap.h"
        #include "fatal.h"
        #include <stdlib.h>

        #define MinPQSize (10)
        #define MinData (-32767)

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

/* START: fig6_0.txt */
        PriorityQueue
        Initialize( int MaxElements )
        {
            PriorityQueue H;

/* 1*/ if( MaxElements < MinPQSize )
/* 2*/ Error( "Priority queue size is too small" );

/* 3*/ H = malloc( sizeof( struct HeapStruct ) );
/* 4*/ if( H ==NULL )
/* 5*/ FatalError( "Out of space!!!" );

            /* Allocate the array plus one extra for sentinel */
/* 6*/ H->Elements = malloc( ( MaxElements + 1 )
                                    * sizeof( ElementType ) );
/* 7*/ if( H->Elements == NULL )
/* 8*/ FatalError( "Out of space!!!" );

/* 9*/ H->Capacity = MaxElements;
/*10*/ H->Size = 0;
/*11*/ H->Elements[ 0 ] = MinData;

/*12*/ return H;
        }
/* END */

        void
        MakeEmpty( PriorityQueue H )
        {
            H->Size = 0;
        }

/* START: fig6_8.txt */
        /* 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;
        }
/* END */

/* START: fig6_12.txt */
        ElementType
        DeleteMin( PriorityQueue H )
        {
            int i, Child;
            ElementType MinElement, LastElement;

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

/* 6*/ for( i = 1; i * 2 <= H->Size; i = Child )
            {
                /* Find smaller child */
/* 7*/ Child = i * 2;
/* 8*/ if( Child != H->Size && H->Elements[ Child + 1 ]
/* 9*/ < H->Elements[ Child ] )
/*10*/ Child++;

                /* Percolate one level */
/*11*/ if( LastElement > H->Elements[ Child ] )
/*12*/ H->Elements[ i ] = H->Elements[ Child ];
                else
/*13*/ break;
            }
/*14*/ H->Elements[ i ] = LastElement;
/*15*/ return MinElement;
        }
/* END */

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

        #if 0
/* START: fig6_14.txt */
        for( i = N / 2; i > 0; i-- )
            PercolateDown( i );
/* END */
        #endif