minheap.cpp

普里母算法和克卢氏卡儿的关于求最短路径的无向图算法

#include<iostream>
template <class Type> class MinPQ 
{
  public:
    virtual int Insert ( const Type & ) = 0;
    virtual int RemoveMin ( Type & ) = 0;
};


template <class Type> class MinHeap : public MinPQ<Type> 
{
  private:
    enum { DefaultSize =10};
    Type *heap;
    int CurrentSize;
    int MaxHeapSize;
    void FilterDown ( int i, int m );
    void FilterUp ( int i );
  public:
    MinHeap ( int maxSize );
    MinHeap ( Type arr[ ], int n );
    ~MinHeap ( ) { delete [ ] heap; }
    const MinHeap<Type> & operator = ( const MinHeap<Type> &R );
    int Insert ( const Type &x );
    int RemoveMin ( Type &x );
    int IsEmpty ( ) const { return CurrentSize == 0; }
    int IsFull ( ) const { return CurrentSize == MaxHeapSize; }
    void MakeEmpty ( ) { CurrentSize = 0; }
    void PrintHeap();
};

  template <class Type> MinHeap<Type>::MinHeap ( int maxSize ) 
  {
    MaxHeapSize = DefaultSize < maxSize ? maxSize : DefaultSize;
    heap = new Type [MaxHeapSize];
    CurrentSize = 0;
  }

  template <class Type> MinHeap<Type>::MinHeap ( Type arr[ ], int n ) 
  {
    MaxHeapSize = DefaultSize < n ? n : DefaultSize;
    heap = new Type [MaxHeapSize];
    for(int i=0;i<=n;i++) heap[i].key=arr[i].key;
    CurrentSize = n+1;               //n is arr's maximum index.
    int currentPos = (CurrentSize-2)/2;
    while ( currentPos >= 0 ) {
      FilterDown ( currentPos, CurrentSize-1 );
      currentPos--;
      }
   }


  template <class Type> void MinHeap<Type>::FilterDown ( int start, int EndOfHeap ) 
  {
    int i = start,   j = 2*i+1;	Type temp = heap[i];
    while ( j <= EndOfHeap ) 
    {
      if ( j < EndOfHeap && heap[j].key > heap[j+1].key ) j++;
      if ( temp.key <= heap[j].key ) break;
   	  else 
      {
        	heap[i] = heap[j];
        	i = j;
        	j = 2*j+1; 
      }
    }
    heap[i] = temp;
  }

  template <class Type> void MinHeap<Type>::FilterUp ( int start ) 
  {
    int j = start,  i = (j-1)/2;   Type temp = heap[j];
    while ( j > 0 ) 
    {
      if ( heap[i].key <= temp.key ) break;
	  else { heap[j] = heap[i];  j = i;  i = (i -1)/2; }
    }
    heap[j] = temp;
  }


  template <class Type> int MinHeap<Type>::Insert ( const Type &x ) {
    if ( CurrentSize == MaxHeapSize ) 
    {
        cerr << "Heap Full" << endl;
        return 0;
    }
    heap[CurrentSize] = x;
    FilterUp (CurrentSize);
    CurrentSize++;
    return 1;
  }


  template <class Type> int MinHeap<Type>::RemoveMin ( Type &x ) 
  {    
    //return the minimum through the reference of x.
    if ( !CurrentSize ) { cout << "Heap empty" << endl;  return 0; }
    x = heap[0];
    heap[0] = heap[CurrentSize-1];
    CurrentSize--;
    FilterDown ( 0, CurrentSize-1 );
    return 1;
   }

  template<class Type> void MinHeap<Type>::PrintHeap()
  {
    for(int i=0;i<CurrentSize;i++)
        cout<<heap[i].key<<endl;
  }