堆

MinHeap(int size):m_nMaxSize(size defaultsize ? size : defaultsize) ,m_pheap(new Type[m_nMaxSize]),m_ncurrentsize(0){} MinHeap(Type heap[],int n); //initialize heap by a array ~MinHeap(){ delete[] m_pheap; public: bool Insert(const Type item); //insert element bool Delete(const Type item); //delete element bool IsEmpty() const{ return m_ncurrentsize == 0; bool IsFull() const{ reutrn m_ncurrentsize == m_nMaxSize; void Print(const int start=0, int n=0); private: //adjust the elements of the child tree with the root of start from top to bottom void Adjust(const int start, const int end); private: static const int defaultsize = 100; const int m_nMaxSize; Type *m_pheap; int m_ncurrentsize; template typename Type void MinHeap Type ::Adjust(const int start, const int end){ int i = start,j = i*2+1; //get the position of the child of i Type temp=m_pheap[i]; while(j = end){ if(j end m_pheap[j] m_pheap[j+1]){ //left right j++; if(temp = m_pheap[j]){ //adjust over break; else{ //change the parent and the child, then adjust the child m_pheap[i] = m_pheap[j]; i = j; j = 2*i+1; m_pheap[i] = temp; template typename Type MinHeap Type ::MinHeap(Type heap[], int n):m_nMaxSize( n defaultsize ? n : defaultsize){ m_pheap = new Type[m_nMaxSize]; for(int i=0; i i++){ m_pheap[i] = heap[i]; m_ncurrentsize = n; int pos=(n-2)/2; //Find the last child tree which has more than one element; while(pos =0){ Adjust(pos, n-1); pos--; template typename Type bool MinHeap Type ::Insert(const Type item){ if(m_ncurrentsize == m_nMaxSize){ cerr "Heap Full!" endl; return 0; m_pheap[m_ncurrentsize] = item; int j = m_ncurrentsize, i = (j-1)/2; //get the position of the parent of j Type temp = m_pheap[j]; while(j 0){ //adjust from bottom to top if(m_pheap[i] = temp){ break; else{ m_pheap[j] = m_pheap[i]; j = i; i = (j-1)/2; m_pheap[j] = temp; m_ncurrentsize++; return 1; template typename Type bool MinHeap Type ::Delete(const Type item){ if(0 == m_ncurrentsize){ cerr "Heap Empty!" endl; return 0; for(int i=0; i m_ncurrentsize; i++){ if(m_pheap[i] == item){ m_pheap[i] = m_pheap[m_ncurrentsize-1]; //filled with the last element Adjust(i,m_ncurrentsize-2); //adjust the tree with start of i m_ncurrentsize--; i=0; return 1; template typename Type void MinHeap Type ::Print(const int start, int n){ if(start = m_ncurrentsize){ return; Print(start*2+2, n+1); //print the right child tree for(int i=0; i i++){ cout " "; cout m_pheap[start] "--- " endl; Print(start*2+1, n+1); //print the left child tree

test.cpp

#include iostream 

using namespace std;

#include "MinHeap.h"

int main(){

 int init[30]={17,6,22,29,14,0,21,13,27,18,2,28,8

 ,26,3,12,20,4,9,23,15,1,11,5,19,24,16,7,10,25};

 MinHeap int heap(init,30);

 heap.Print();

 cout endl endl endl;

 heap.Insert(20);

 heap.Print();

 cout endl endl endl;

 heap.Delete(20);

 heap.Print();

 cout endl endl endl;

 return 0;

}