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.
How to find out the median of an array of integer with an algorithm of O(n)?
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.
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