Min-Max Heap（1）

A. First Edition

This is first edition of my min-max-heap and in order to try other approach I need to save this edition first.

B.The problem

How to construct a template-based min-heap and max-heap in a universal format?

The first approach is just like text book---using compare class in template parameter to differ the

min and max heap. But can you pass parameter twice when declare? No, unless you use the "bool" flag.

This is what I want to try later.

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 EEComp
{
public:
	static bool before(Elem e1, Elem e2);
	static bool same(Elem e1, Elem e2);
	static bool after(Elem e1, Elem e2);
};
*/

template<class Key, class Elem,  class KEComp, class EEComp>
class Heap
{
private:
	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;}
public:
	void buildHeap();
	void display();
	Heap(Elem* theArray, int size){ array=theArray; curLength=maxLength=size;}
};


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>
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 (EEComp::before(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 (EEComp::before(array[r], array[l]))//if right is before left
			{
				result = r;
			}
		}
		//
		if (EEComp::before(array[result], array[index]))//compare the "bigger" with parent
		{
			swap(array, result, index);
			siftDown(result);
		}
		//if not, simply end here
	}
}

file name: heap.cpp (main)

#include <iostream>
#include "Heap.h"

using namespace std;


class intMaxComp
{
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;}
};

class intMinComp
{
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, intMaxComp, intMinComp> H(myArray, Length);
	H.buildHeap();
	H.display();
	return 0;
}

Here is the result: The result is a min-heap and by changing the declaration of Heap, say,

replace "intMinComp" with "intMaxComp", you can easily build a max-heap.  

1 6 25 28 20 35 28 59 43 37 70 46 82 79 62 92 96 68 63 42
Press any key to continue