Min-Max Heap£¨2£©

A. Second Edition
This is second edition of my min-max-heap and I reluctantly call it a second edition as there is only a minor
improvement. However, in order to keep the continuation of versions I saved it as a second edition.
B.The problem
How to construct a template-based min-heap and max-heap in a universal format?
C.The idea of program
¡¡

As promised in previous edition, I want to use a bool flag to indicate the "min" or "max" heap.

D.The major functions
E.Further improvement
F.File listing
1. heap.h
2. heap.cpp  (main)
¡¡
file name: heap.h
template<class Elem>
void swap(Elem* array, int i, int j)
{
	Elem temp;
	temp=array[i];
	array[i]=array[j];
	array[j]=temp;
}

template<class Key, class Elem,  class KEComp, class EEComp>
class Heap
{
private:
	bool reversed;
	Elem* array;
	int maxLength;
	int curLength;
	void siftDown(int index);
	void siftUp(int index);
	int parent(int index) { return (index-1)/2;}
	int left(int index) { return index*2+1;}
	int right(int index) { return index*2+2;}
	bool isLeaf(int index) { return left(index)>=curLength;}
	bool EEcompare(Elem e1, Elem e2);
public:
	void buildHeap();
	void display();
	void setDirection(bool direction){reversed=direction;}
	Heap(Elem* theArray, int size){array=theArray; curLength=maxLength=size; reversed=false;}
};


template<class Key, class Elem,  class KEComp, class EEComp>
void Heap<Key, Elem, KEComp, EEComp>::buildHeap()
{
	for (int i=(maxLength-1)/2; i>=0; i--)
	{
		siftDown(i);
	}
}

template<class Key, class Elem,  class KEComp, class EEComp>
bool Heap<Key, Elem, KEComp, EEComp>::EEcompare(Elem e1, Elem e2)
{
	if (!reversed)
	{
		return EEComp::before(e1, e2);
	}
	else
	{
		return EEComp::after(e1, e2);
	}
}



template<class Key, class Elem,  class KEComp, class EEComp>
void Heap<Key, Elem, KEComp, EEComp>::display()
{
	for (int i=0; i<maxLength; i++)
	{
		cout<<array[i]<<" ";
	}
	cout<<endl;
}

template<class Key, class Elem,  class KEComp, class EEComp>
void Heap<Key, Elem, KEComp, EEComp>::siftUp(int index)
{
	int p;
	if (index>0)
	{
		p=parent(index);
		//swap only if son is "before" parent
		if (EEcompare(array[index], array[p]))
		{
			swap(array, index, p);
			siftUp(p);
		}
	}
}


template<class Key, class Elem,  class KEComp, class EEComp>
void Heap<Key, Elem, KEComp, EEComp>::siftDown(int index)
{
	int l, r, result;
	l=left(index);
	r=right(index);

	if (l<=curLength)//index is not a leaf
	{
		result=l;
		if (r<=curLength)//if right is valid
		{
			//swap index only if right is "before" left
			if (EEcompare(array[r], array[l]))//if right is before left
			{
				result = r;
			}
		}
		//
		if (EEcompare(array[result], array[index]))//compare the "bigger" with parent
		{
			swap(array, result, index);
			siftDown(result);
		}
		//if not, simply end here
	}
}




file name: heap.cpp
#include <iostream>
#include "Heap.h"

using namespace std;


class intComp
{
public:
	static bool before(int i, int j) { return i>j;} 
	static bool same(int i, int j) { return i==j;}
	static bool after(int i, int j) { return i<j;}
};

int main()
{
	const int Length=20;
	int myArray[Length];
	for (int i=0; i<Length; i++)
	{
		myArray[i]=rand()%100+1;//1--100
	}
	Heap<int, int, intComp, intComp> H(myArray, Length);
	H.buildHeap();
	H.display();
	cout<<"now it is min-heap by setDir()\n";
	H.setDirection(true);
	H.buildHeap();
	H.display();
	return 0;
}
Here is the result: The result is a min-heap and by changing the direction of Heap.
¡¡
96 92 82 68 70 46 79 59 63 65 6 35 25 28 62 1 42 43 28 37
now it is min-heap by setDir()
1 6 25 28 20 35 28 42 43 37 70 82 46 79 62 59 68 92 63 96
Press any key to continue

	


                                 back.gif (341 bytes)       up.gif (335 bytes)         next.gif (337 bytes)