Finding median from arbitrary array of integers using only heap(s)

user_466056 0
Viewed 113

I need to find the median for a given array, having a restriction to use only heaps.

I am aware of the linear selection algorithms for finding the median. Is the following approach (based on heaps only) correct?

  1. build a max-heap (h) from the given array
  2. build a max-heap (h1) from the leaves (ceil(n/2)) of heap h
  3. build a min-heap (h2) from the internal nodes (floor(n/2)) of heap h
  4. if n is odd return max(h1[0],h2[0])
    else return (h1[0] + h2[0])/2
median heap algorithm
1 Answers

No, the algorithm you propose will not work generally. It wrongly assumes that the leaves of the max heap cannot have a value that is greater than the median. This is not true. Here is a counter example:

input: [7, 6, 3, 5, 4, 2, 1]

  1. build max-heap (h) from given array

The input happens to already be structured as a max-heap. It is:

                     7
                   /   \  
                 6       3
                / \     / \
               5   4   2   1
  1. build max-heap (h1) from the leaves (ceil(n/2)) elements of heap h
                 5     
                / \
               4   2
              /
             1
  1. build min-heap (h2) from the internal nodes (floor(n/2)) elements of heap h
                 3
                / \
               7   6

Note that the creation of these smaller heaps, in this and the previous step, is not really necessary for your purpose, as you really are only interested to get the maximum value from the leaves and the minimum value from the internal nodes. For that a simple scan would be enough, without the need to actually create two more heaps.

  1. if n is odd return max(h1[0],h2[0])
 max(h1[0],h2[0]) = 5

Yet the correct answer is not 5, but 4.

Algorithm

You only need one heap.

Put the first half (rounded upwards) of the values in a min-heap. Then for the remaining values, check for each whether they are smaller than the root of the heap. If so, ignore the value. If not, then replace the root's value with the greater value, and heapify the heap so the new value sifts down to a good position in the heap.

After doing this, you know that all values greater than the median are in the tree, and it also includes the one or two values representing the median. If the input had an odd number of values, the root is the median. If it was even, then pull the root value from the heap, and average it with the value that becomes the root after this extraction.

user_54598390
Related