CS29003 Algorithms Laboratory Autumn 2013, L-T-P: 0-0-3 

Assignment No 5

Implementation of Median Heaps

A max-heap (or a max-priority queue, to be more precise) supports constant-time max finding, and logarithmic-time insertion and deleteMax. A min-heap, on the other hand, supports constant-time min finding, and logarithmic-time insertion and deleteMin. In this exercise, you build a heap (let us call it a med-heap) that should support the following three operations:

Using a med-heap, you are supposed to write a sorting function analogous to heap sort.

Let N be the current number of elements in a collection (a med-heap). We make the following convention. If N = 2k + 1 (that is, odd), then the median is the (k + 1)-st smallest element in the collection. If N = 2k (even), then we call the k-th smallest element the median of the collection.

A med-heap is realized by maintaining two heaps: a max-heap consisting of the smaller half of the values, and a min-heap consisting of the larger half of the values. The following figure demonstrates how a single array can be used for the contiguous representation of both the heaps back to back.

Max-heap of smaller values    Empty space    Min-heap of larger values
Direction of growth → (for future insertions) ← Direction of growth

Let N1 be the number of elements stored in the max-heap, and N2 the number of elements stored in the min-heap. We have N1 + N2 = N. We maintain the convention N1 = ⌊N / 2⌋ and N2 = ⌈N / 2⌉. Notice that the max-heap grows from the left, that is, the maximum in this heap can be found at the zeroth index of the array. On the other hand, the min-heap grows from the right end, that is, the minimum in this heap can be found at the (n − 1)-st index of the array, where n is the total capacity of the array (including the empty space).

Now, write the following functions.

Sample Output

n = 20

+++ MedHeap initialized

+++ Going to insert elements one by one in MedHeap
    Insert(3064) done. Current median = 3064.
    Insert( 545) done. Current median =  545.
    Insert(2978) done. Current median = 2978.
    Insert(5176) done. Current median = 2978.
    Insert(7432) done. Current median = 3064.
    Insert(2687) done. Current median = 2978.
    Insert(9903) done. Current median = 3064.
    Insert(7991) done. Current median = 3064.
    Insert(7963) done. Current median = 5176.
    Insert(6184) done. Current median = 5176.
    Insert(5426) done. Current median = 5426.
    Insert(9981) done. Current median = 5426.
    Insert(8838) done. Current median = 6184.
    Insert(8053) done. Current median = 6184.
    Insert(1069) done. Current median = 6184.
    Insert(2950) done. Current median = 5426.
    Insert(3625) done. Current median = 5426.
    Insert(9130) done. Current median = 5426.
    Insert(8458) done. Current median = 6184.
    Insert(9070) done. Current median = 6184.

+++ Median Heap Sort done
      545 1069 2687 2950 2978 3064 3625 5176 5426 6184 7432 7963 7991 8053 8458
     8838 9070 9130 9903 9981

Remark: If our ultimate goal is the medHeapSort function, then we could have done better than inserting n elements one by one in the med-heap, which takes O(n log n) time. What we instead do is just starting with an array fully populated with elements. We then convert the array to a med-heap using a linear-time makeMedHeap function. Such a function can, for example, be implemented if we can quickly locate the median in the initial array. A linear-time median-finding algorithm does exist, and will be covered later in the theory course. We then partition the array using the median as pivot as in the quick sort algorithm. Finally, we call makeMaxHeap to convert the smaller half to a max-heap, and makeMinHeap to convert the larger half to a min-heap. The subsequent sequence of n deletions would anyway take O(n log n) time. But it is interesting to know that a linear-time makeHeap algorithm can be designed for med-heaps too.

Submission site | Miscellaneous information | Home