My Heap implementation is not working...please have a look frnds..

pavarathyRock

Hi Frnds, I am trying to do the heap implementation. I was following the algorithm explained in cormen....

#include "MyHeap.h"
void MyHeap::Build_Max_Heap(int * array, int length)
{
for (int i= (length/2); i>=0 ; i--)
{
Max_heapify(array, i, length);
}
}

void MyHeap::Max_heapify(int * array, int index, int length)
{
int left = ((2 * index) + 1);
int right = ((2 * index) + 2);
int largest;
if ((left <= length) && (array[left] > array[index]))
{
largest = left;
}
else
{
largest = index;
}

if ((right <= length) && (array\[right\] > array\[largest\]))
{
	largest = right;
}

if (largest != index)
{
	swap(array\[largest\], array\[index\]);
	Max\_heapify(array, largest, length);
}

}

void MyHeap::swap(int & a, int & b)
{
int c = a;
a = b;
b = c;
}

void MyHeap::print(int * array, int length)
{
for (int i = 0; i< length; i++)
{
cout<<array[i]<<"\t";
}
}

int main()
{
int array[] = {14, 10, 1, 8, 7, 9, 3, 2, 4, 16};
MyHeap h;
h.print(array, 10);
h.Build_Max_Heap(array, 10);
h.print(array, 10);

int x;
cin>>x;
return(0);

}

For some input it is working. For some it is not.. for the given input this is the output I am getting.. 16 14 9 8 10 1 3 2 4 7 Thanks in advance...

Iain Clarke Warrior Programmer

pavarathyRock wrote:

I was following the algorithm explained in cormen....

You forgot to explain what you're trying to do in the comments... All we currently know is that you're failing, not what you need to do. Iain.

I have now moved to Sweden for love (awwww). If you're in Scandinavia and want an MVP on the payroll (or happy with a remote worker), or need cotract work done, give me a job! http://cv.imcsoft.co.uk/[^]

Lost User

16 14 9 8 10 1 3 2 4 7 looks like a correct heap to me, now I may have made a mistake, but it looks like:

          16
         /   \\
       14     9
      /  \\   /  \\
     8   10  1  3
    / \\  /
   2  4  7

Which is a correct heap, no?

David Crow

pavarathyRock wrote:

void MyHeap::Max_heapify(int * array, int index, int length) { int left = ((2 * index) + 1); int right = ((2 * index) + 2); ...

The first time Max_heapify() is called, left equals 11 and right equals 12.

pavarathyRock wrote:

if ((left <= length) && (array[left] > array[index]))

left is then used to access array, which is indexed 0-9.

"Old age is like a bank account. You withdraw later in life what you have deposited along the way." - Unknown

"Fireproof doesn't mean the fire will never come. It means when the fire comes that you will be able to withstand it." - Michael Simmons

pavarathyRock

But here 16 / \ 14 9 / \ / \ 8 10 1 3 / \ / 2 4 7 10 is coming after 9 . As per heaps definition the root should contain largest element right..

Lost User

No it doesn't, the layout got messed up here, but that 10 is below the 14 and the 1 and 3 are below the 9.

pavarathyRock

:) :) Thanks herald for the help..... I think my implementation is correct. I have tried to print the heap as follows.

int main()
{
int array[] = {14, 10, 1, 8, 7, 9, 3, 2, 4, 16};
MyHeap h;
h.print(array, 10);
h.Build_Max_Heap(array, 10);
cout<<"Initial Heap\n";
h.print(array, 10);
cout<

It was giving the correct output.

The main cause for this doubt is that I AM A FOOOL. I blindly believed the output given in the book.
I didn't even try to print the output and check.......

Thanks frnd thank you very much.....:thumbsup::thumbsup::thumbsup:

and thanks for all others for your help.

Lost User

Lol you're welcome, but you didn't spell my name right ;)