Heap

A minimum heap is a list of numbers such that the i th i^\text{th} number is smaller than the ( 2 i ) th (2i)^\text{th} and ( 2 i + 1 ) th (2i+1)^\text{th} numbers. For example, L = { 1 , 2 , 3 , 3 , 5 , 4 , 7 } L = \{1, 2, 3, 3, 5, 4, 7\} is a minimum heap because

  • the 1 st 1^\text{st} number is smaller than the 2 nd 2^\text{nd} and 3 rd 3^\text{rd} numbers;
  • the 2 nd 2^\text{nd} number is smaller than the 4 th 4^\text{th} and 5 th 5^\text{th} numbers;
  • the 3 rd 3^\text{rd} number is smaller than the 6 th 6^\text{th} and 7 th 7^\text{th} numbers.

Conversely, a maximum heap is a list of numbers such that the i th i^\text{th} number is larger than the ( 2 i ) th (2i)^\text{th} and ( 2 i + 1 ) th (2i+1)^\text{th} numbers.


True or False?

If I reverse a minimum heap , I always get a maximum heap .

False True

This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try refreshing the page, (b) enabling javascript if it is disabled on your browser and, finally, (c) loading the non-javascript version of this page . We're sorry about the hassle.

1 solution

Ayush Kumar
May 2, 2017

You can make a minimum heap that is not in ascending order because the 5th (although 4th, 6th, and 7th work as well) can be made very big. This will give us a heap that when reversed has a very large number in the 3rd slot. We can make this number bigger than the one in the first. One example is {1, 4, 2, 5, 7, 3, 3} if the logic is still not clear.​ Reversing it, we obtain {3, 3, 7, 5, 2, 4, 1}. If we look at the first and compare to the second and third, it should be greater than both. However, you can see that three isn't greater than either, and therefore, the heap is not a maximum heap. We have proved the statement false.

I have changed the example so that it is not too obvious!

Christopher Boo - 4 years, 1 month ago

I will change the wording of the solution to account for that. Thanks!

Ayush Kumar - 4 years, 1 month ago

0 pending reports

×

Problem Loading...

Note Loading...

Set Loading...