Population

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