二叉堆（最大堆和最小堆）

programming

/*
Filename: heap.cpp
Function: 简单实现二叉堆结构，可实现最大堆和最小堆。
Details: 调用FindTop()及DeleteTop()函数前请先check
一下IsEmpty()。
*/
#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#define DEFAULT_CAPACITY (10)
template<typename T>
class BinaryHeap
{
public:
    BinaryHeap( );
    BinaryHeap( int nCapacity, int nMode );
    ~BinaryHeap( );
    void Insert( T element );
    void MakeEmpty( );
    T DeleteTop( );
    T FindTop( );
    bool IsEmpty();
    bool IsFull();
    void Destroy();
private:
    T *Elements;
    int Capacity;
    int Size;
    /*
       mode==0:min; mode==1:max
    */
    int mode;
};
template<typename T>
BinaryHeap<T>::BinaryHeap( )
{
    Capacity = DEFAULT_CAPACITY;
    Size = 0;
    mode = 0;
    Elements = (T*) malloc( Capacity*sizeof(T) );
    if( Elements==NULL )
        printf("Out of Spaces!\n");
}
template<typename T>
BinaryHeap<T>::BinaryHeap( int nCapacity, int nMode )
{
    Capacity = nCapacity;
    Size = 0;
    mode = nMode;
    Elements = (T*) malloc( nCapacity*sizeof(T) );
    if( Elements==NULL )
        printf( "Out of Spaces!\n" );
}
template<typename T>
BinaryHeap<T>::~BinaryHeap()
{
    Destroy();
}
/*
*/
template<typename T>
void BinaryHeap<T>::Destroy()
{
    if( Elements!=NULL )
        free( Elements );
}
template<typename T>
bool BinaryHeap<T>::IsEmpty()
{
    return ( Size==0 );
}
template<typename T>
bool BinaryHeap<T>::IsFull()
{
    return ( Size==Capacity );
}
template<typename T>
void BinaryHeap<T>::Insert( T element )
{
    if( IsFull() )
        return;
    int i;
    if( mode==0 )
        for( i=++Size-1; i>0 && Elements[i]>element; i=(i-1)/2 )
            Elements[i] = Elements[(i-1)/2];
    else if( mode==1 )
        for( i=++Size-1; i>0 && Elements[i]<element; i=(i-1)/2 )
            Elements[i] = Elements[(i-1)/2];
    Elements[i] = element;
}
template<typename T>
T BinaryHeap<T>::FindTop()
{
    return Elements[0];
}
template<typename T>
T BinaryHeap<T>::DeleteTop()
{
    T minElement = Elements[0];
    T lastElement = Elements[--Size];
    int i, child;
    if( mode==0 )
    for( i=0; i*2+1<Size; i=child )
    {
        child = i*2+1;
        if( child!=Size-1 && Elements[child]>Elements[child+1] )
            child++;
        if( Elements[child]<lastElement )
            Elements[i] = Elements[child];
        else
            break;
    }
    else if( mode==1 )
    for( i=0; i*2+1<Size; i=child )
    {
        child = i*2+1;
        if( child!=Size-1 && Elements[child]<Elements[child+1] )
            child++;
        if( Elements[child]>lastElement )
            Elements[i] = Elements[child];
        else
            break;
    }
    Elements[i] = lastElement;
    return minElement;
}
template<typename T>
void BinaryHeap<T>::MakeEmpty()
{
    Size = 0;
}