Population

Min-Max Heap£¨3£©

    A. Third Edition

    This is third edition of my min-max-heap and this edition is really a practical one which means it indeed solves

    some problems.

    B.The problem

    How to find out the median of an array of integer with an algorithm of O(n)?

C.The idea of program
¡¡

It is said that if you want to do a good job, you need first have a good tool. It is the case as I

plan this ahead for the tool in two editions. I created two heaps, one is max-heap and the other is

min-heap with such a property that the median is not less than the max of max-heap and is not bigger

than the min of min-heap. Then indeed the median is not less than all elements in max-heap and not

bigger than all elements in min-heap. Now the problem is how to keep this median to be median which

means that the two heaps must be in a balanced mode. Here "balance" is very similar to that of a

AVL Tree with two sides of maximum difference in number of elements not bigger than 1. If not

balanced, we need to shift. For example, the max-heap has 4 elements, and min-heap has 6 elements.

It means that the min-heap needs to remove the min one and makes it median and the original median

should be inserted into max-heap.

    D.The major functions

    E.Further improvement

    I found out a serious bug  in previous edition of "siftdown" which exceeds the boundary of array.

    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);
    	void insert(bool fromHead=false);//two choices:from head or from end
    public:
    	bool insert(const Elem& e);
    	void buildHeap();
    	void display();
    	bool removeHead(Elem& e);
    	void setDirection(bool direction){reversed=direction;}
    	Heap(Elem* theArray, int size, int maxSize=20)
    	{array=theArray; curLength=size; maxLength=maxSize; reversed=false;}
    };

    template<class Key, class Elem, class KEComp, class EEComp>
    bool Heap<Key, Elem, KEComp, EEComp>::removeHead(Elem& e)
    {
    	if (curLength==0)
    	{
    		cout<<"heap is empty\n";
    		return false;
    	}
    	curLength--;
    	swap(array, 0, curLength);
    	e=array[curLength];
    	siftDown(0);
    	return true;
    }

    template<class Key, class Elem, class KEComp, class EEComp>
    bool Heap<Key, Elem, KEComp, EEComp>::insert(const Elem& e)
    {
    	if (curLength==maxLength)
    	{
    		cout<<"the heap is full\n";
    		return false;
    	}
    	//else
    	curLength++;
    	array[curLength-1]=e;
    	siftUp(curLength-1);
    	return true;
    }

    template<class Key, class Elem, class KEComp, class EEComp>
    void Heap<Key, Elem, KEComp, EEComp>::insert(bool fromHead)
    {
    	curLength++;
    	if (fromHead)
    	{
    		array--;
    		siftDown(0);
    	}
    	else
    	{
    		siftUp(curLength-1);
    	}
    }

    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<curLength; 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 (main)

    #include <iostream>
    #include <time.h>
    #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 current, mid=0, leftSize=0, rightSize=0, hold;
    	int myArray[Length];
    	int leftArray[Length];//try to waste some memory
    	int rightArray[Length];

    	Heap<int, int, intComp, intComp> H(myArray, Length);

    	srand(time(0));

    	for (int i=0; i<Length; i++)
    	{
    		myArray[i]=rand()%100+1;//1--100
    		cout<<myArray[i]<<"  ";
    	}

    	cout<<endl;
    	H.buildHeap();
    	H.display();
    	cout<<endl;

    	Heap<int, int, intComp, intComp> left(leftArray, 0);

    	Heap<int, int, intComp, intComp> right(rightArray, 0);
    	//left is by default the max heap
    	left.setDirection(false);
    	//right is min heap
    	right.setDirection(true);

    	mid=myArray[0];

    	for (i=1; i<Length; i++)
    	{
    		current=myArray[i];
    		if (current<mid)
    		{
    			left.insert(current);
    			leftSize++;
    		}
    		else
    		{
    			right.insert(current);
    			rightSize++;
    		}
    		if (leftSize-rightSize>1)
    		{
    			left.removeHead(hold);
    			right.insert(mid);
    			mid=hold;
    			leftSize--;
    			rightSize++;
    		}
    		else
    		{
    			if (leftSize-rightSize<-1)
    			{
    				right.removeHead(hold);
    				left.insert(mid);
    				mid=hold;
    				leftSize++;
    				rightSize--;
    			}
    		}
    	}

    	cout<<"the mid is:"<<mid<<endl;
    	cout<<"the left is:"<<endl;
    	left.display();
    	cout<<"the right is:"<<endl;
    	right.display();
    	cout<<endl;

    	return 0;
    }

    Here is the result: In order for a better view, I "sorted" the heap a bit and increased the chance of "shifting".

    65 21 79 82 68 10 83 40 51 25 54 73 16 99 13 93 91 43 96 75
    99 96 83 93 75 73 79 91 82 68 54 10 16 65 13 40 21 43 51 25

    the mid is:68
    the left is:
    65 54 16 43 51 10 13 21 40 25
    the right is:
    73 75 82 79 93 96 83 99 91

    Press any key to continue