I am writing a max heap in java. Here is my code: I am having a little trouble w

Question

I am writing a max heap in java. Here is my code:

I am having a little trouble with the extract max funciton. After running the function, the last item in the array is moved to the top of the array. I can extract the max value, but I'm not sure what to do with the array after.. Do I move all values up one in the array, or do I just assume the removed value isn't there. I'm a little confused.

Thanks

Explanation / Answer

In extractMax function what we essentially do is that, we first, take to the value from root, which will be maximum value and save it in our max variable. Then we replace the value on top or at index 0 with the last value of the heap array.

For this we are maintaining a variable sortCount here. It will contain present number of elements in the heap array. So after taking out the max value, we need to get the last element in the array with help of sortCount, and save it in first position.

Then we need to decrease the value of sortCount, because we have removed one element from the array.

So essentially, we are not considering what values are there in the whole array. We are just considering the values equivalent to sortCount.

eg.

consider array...

5,4,3,2,1

here sortcount is 5,

So we store arr[0] in max. So max = 5.

arr[0] = arr[sortCount - 1]

So arr[0] = 1, So array becomes 1,4,3,2,1.

Now we decrease the sortCount to 1.

So 1,4,3,2 is the array,

Now we will run maxHeapify on this .

There are few errors in your extraxtMax function. : -

1. Your if condition

if(sortCount < 0) return null;

is wrong . sortCount starts from 0 . If there are no values in heap , then sortCount will be 0 . So we need to check that condition also.So correct version will be

if(sortCount <= 0) return null;

2. Other issue is this line

heaoList[0] = heapList[sortCount]

sortCount starts from 0 . As array indexes start from 0 to n-1,So here it should be

heapList[0] = heapList[sortCount -1];

Rest code of your extractMax is fine ..

Note that because question was for extractMax function. I have not checked and explained errors in your heapify. There are few errors in that also. First complete the program . If there is any error, post the question with complete code. We'll love to explain and correct errors in your code.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.