CODEWITHSUNDEEP
data-structuresheap
Frank
Frank

Reputation: 4417

Finding the smallest element of a binary max heap stored as Ahnentafel array

I have a binary max heap (largest element at the top), and I need to keep it of constant size (say 20 elements) by getting rid of the smallest element each time I get to 20 elements. The binary heap is stored in an array, with children of node i at 2*i and 2*i+1 (i is zero based). At any point, the heap has 'n_elements' elements, between 0 and 20. For example, the array [16,14,10,8,7,9,3,2,4] would be a valid max binary heap, with 16 having children 14 and 10, 14 having children 8 and 7 ...

To find the smallest element, it seems that in general I have to traverse the array from n_elements/2 to n_elements: the smallest element is not necessarily the last one in the array.

So, with only that array, it seems any attempt at finding/removing the smallest elt is at least O(n). Is that correct?

Upvotes: 2

Views: 10689

Answers (3)

Dungeon Hunter
Dungeon Hunter

Reputation: 20623

For any given valid Max Heap the minimum will be at the leaf nodes only. The next question is how to find the leaf nodes of the heap in the array ?. If we carefully observe the last node of the array it will be the last leaf node. Get the parent of the leaf node by the formula 

parent node index = (leaf Node Index)/2

Start linear search from the index (parent node index +1) to last leaf node index get the minimum value in that range.

FindMinInMaxHeap(Heap heap)
   startIndex = heap->Array[heap->lastIndex/2]
   if startIndex == 0
          return heap->Array[startIndex]
   Minimum = heap->Array[startIndex + 1]
   for count from startIndex+2 to heap->lastIndex
            if(heap->Array[count] < Minimum)
                Minimum := heap->Array[count]
   print Minimum

Upvotes: 5

MBo
MBo

Reputation: 80327

There is minmax heap data structure: http://en.wikipedia.org/wiki/Min-max_heap . Of course, it's code is rather complex, but with two separate heaps we have to use a lot of additional space (for the second heap, for maintaining one-to-one mapping) and to do the job twice.

Upvotes: 0

Hari Menon
Hari Menon

Reputation: 35475

There isn't any way I can think of by which you can get better that O(n) performance for finding and removing the smallest element from a max heap by using the heap alone. One approach that you can take is:

If you are creating this heap data structure yourself, you can keep a separate pointer to the location of the smallest element in the array. So whenever a new element is added to the heap, check if the new element is smaller. If yes, update the pointer etc. Then finding the smallest element would be O(1).

MBo raises a good point in the comment about how to get the next smallest element after each removal. You'll still need to do the O(n) thing to find the next smallest element after each removal. So removal would still be O(n). But finding the smallest element would be O(1)

If you need faster removal as well, you'll need to also maintain a min-heap of all the elements. In that case, removal would be O(log(n)). Insertion will take 2x time because you have to insert into two heaps and it will also take 2x space.

By the way, if you have only 20 elements at any point of time, this is not really going to matter much (unless it is a homework problem or you are just doing it for fun). It would really matter only if you plan to scale it to thousands of values.

Upvotes: 3

Related Questions