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.
How to construct a template-based min-heap and max-heap in a universal format?
As promised in previous edition, I want to use a bool flag to indicate the "min" or "max" heap.
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