Population

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.

    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
¡¡

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.

    D.The major functions

    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