Min-Max Heap£¨4£©
A. Fourth Edition
This is fourth edition of my min-max-heap and this edition is only trying to prove it is indeed a O(n) algorithms
by counting the movements and comparisons.
How to find out the median of an array of integer with an algorithm of O(n)?
This is actually a kind of copy from my data structure assignment in which we are required to
count the movements and comparisons of different sorting algorithms so that we can analysis and
compare them. The movements of data is defined to be the copy and swap of elements: copy=1 and
swap=3. Comparisons of elements is restricted to elements comparison and index comparison is not
ignored. So, there is really little change than previous edition, but I need to keep the versions.
E.Further improvement
When using the heap, don't forget that the default max array size is 20. And it is programmer's duty
to specify it when declared. Otherwise there maybe some strange things happening.
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:
int moveCount;//swap is considered to be 3 times of movements
int compCount;
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:
int getMove(){ return moveCount;}
int getComp(){ return compCount;}
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; compCount=moveCount=0;}
};
//insert movement count
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--;
//insert counting
//swap is 3 movements
moveCount+=4;
swap(array, 0, curLength);
e=array[curLength];
siftDown(0);
return true;
}
//insert movement counts
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++;
//insert movement counts
moveCount+=1;
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);
}
}
//insert movement count
template<class Key, class Elem, class KEComp, class EEComp>
bool Heap<Key, Elem, KEComp, EEComp>::EEcompare(Elem e1, Elem e2)
{
if (!reversed)
{
compCount+=1;
return EEComp::before(e1, e2);
}
else
{
compCount+=1;
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]))
{
moveCount+=3;
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
{
moveCount+=3;
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=80;
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, 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, Length);
Heap<int, int, intComp, intComp> right(rightArray, 0, Length);
//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;
cout<<"the total movements/Length are "
<<(left.getMove()+right.getMove())/Length<<endl;
cout<<"the total compares/Length are "
<<(left.getComp()+right.getComp())/Length<<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".
And I changed the Length then run, you can observe that the times of number of movements and comparison than
Length nearly doesn't increase while the Length doubles. This proves the algorithms is indeed linear.
1. This is for Length=20:
37 61 14 80 97 13 91 47 65 55 42 15 73 77 24 12 90 39 67 75 97 90 91 80 75 73 77 47 67 61 42 15 13 14 24 12 37 39 65 55 the mid is:61 the left is: 55 47 42 37 39 15 14 12 24 13 the right is: 65 67 75 73 90 91 77 97 80 the total movements/Length are 8 the total compares/Length are 3 Press any key to continue
2. This is for Length=40:
68 13 85 73 64 42 17 28 69 9 26 77 92 70 74 7 66 52 91 58 100 74 87 41 95 8
1 68 20 34 98 3 58 58 18 36 62 74 55 70 24
100 91 98 74 87 95 85 66 73 64 74 77 92 70 74 58 36 68 70 58 9 13 26 41 42 81 68 20 34 17 3 7 58 18
28 62 52 55 69 24
the mid is:64
the left is:
62 58 42 58 58 36 41 34 55 24 13 26 3 20 17 7 18 28 52 9
the right is:
66 68 70 68 74 81 73 74 69 95 77 98 87 92 74 100 85 91 70
the total movements/Length are 9
the total compares/Length are 4
Press any key to continue
3. This is for Length=80:
48 51 74 35 41 4 61 68 2 13 59 99 14 14 59 30 95 31 77 95 60 58 35 96 27 22 90 79 91 97 15 99 1 76 50 55 68 58 71 90 6 75 52 41 77 34 59 81 50 20 95 60 16 62 4 45 64 85 58 62 96 89 70 34 70 32 93 11 19 63 33 29 36 49 18 63 3 9 35 76 82 99 95 99 93 95 96 97 76 77 90 77 95 90 91 96 70 63 68 76 82 75 59 59 81 74 60 62 79 85 62 89 51 68 3 5 50 55 49 63 71 41 6 60 52 41 58 34 35 4 50 20 27 22 16 14 4 45 64 14 58 61 59 15 70 34 30 32 1 11 19 48 33 29 36 31 18 58 39 35 2 13 the mid is:58 the left is: 58 55 58 51 49 50 52 48 50 41 41 30 27 45 19 34 35 36 39 33 16 1 34 4 20 22 14 18 14 4 15 6 32 11 2 29 31 35 35 13 the right is: 59 59 63 59 76 70 64 62 60 77 76 85 71 68 68 79 63 62 60 97 93 95 77 99 90 95 74 96 89 90 70 99 91 9 5 75 96 81 82 61 the total movements/Length are 11 the total compares/Length are 5 Press any key to continue
4. This is for Length=160:
91 29 66 45 99 72 37 40 16 42 51 37 84 56 42 42 39 41 93 73 55 59 27 58 98 56 94 13 97 4 85 44 74 5 10 17 17 7 40 64 83 49 72 15 29 76 86 87 19 62 67 59 78 62 69 19 70 70 54 62 28 53 4 14 29 50 96 68 7 9 58 7 24 64 8 82 83 24 59 82 58 14 10 72 77 16 29 51 36 28 33 88 21 75 28 35 22 18 96 17 98 17 74 50 93 16 41 65 28 58 12 22 24 91 4 36 37 89 24 98 100 51 68 39 92 10 93 12 19 76 93 61 28 33 6 29 8 79 97 97 20 33 3 64 77 35 12 46 89 49 41 58 88 37 52 34 5 99 43 48 100 99 98 97 99 98 98 97 93 83 88 96 94 97 93 96 79 89 88 82 77 59 86 91 74 93 84 91 89 68 92 93 74 68 58 77 64 83 59 64 73 72 72 51 33 76 75 87 58 62 72 59 78 65 69 24 70 70 56 62 51 66 85 19 76 61 4 2 29 39 20 40 64 35 46 49 82 52 34 43 48 58 14 10 55 49 16 29 15 36 28 29 27 21 51 28 35 22 18 19 17 37 17 67 50 56 16 41 62 28 58 12 22 19 13 4 36 37 54 24 4 42 37 28 39 53 10 4 12 14 44 29 50 28 33 6 29 8 5 7 9 10 33 3 17 7 24 12 41 17 8 41 58 7 37 45 24 5 40 16 42 the mid is:49 the left is: 48 46 42 45 43 41 37 44 41 42 39 37 29 29 37 39 33 40 41 42 36 28 35 35 19 19 28 24 21 36 28 19 33 2 9 33 24 28 37 40 17 14 12 16 15 3 27 7 22 18 17 17 4 16 7 14 22 13 8 5 4 4 28 10 12 10 29 6 29 5 9 2 0 10 17 24 8 7 34 24 12 16 the right is: 49 50 59 50 70 64 59 56 51 74 72 68 65 62 59 58 56 53 51 89 74 73 72 86 69 68 66 83 64 62 61 78 70 5 8 58 76 54 58 51 99 91 97 75 97 89 91 72 99 93 96 82 98 87 88 67 98 84 93 64 94 83 85 62 100 92 96 7 6 97 79 88 58 98 77 93 55 93 77 82 52 the total movements/Length are 15 the total compares/Length are 7 Press any key to continue