Question

You are given a list of numbers for which you need to construct a **min**-heap. (A **min**-heap is a complete binary tree in which every key is less than or equal to the keys in its children.) How would you use an algorithm for constructing a **max**-heap (a heap as defined in Section 6.4) to construct a **min**-heap? You need to describe your algorithm in **pseudo code**.

Answer 1

The sort used in this is called Heap Sort. Here, the numbers are sorted in the order according to the heap used. In the case of min-heap, the root will have to lesser than the children which have to be lesser than the subsequent children. In the case of the max heap, the binary tree will be ordered from the highest (root) to lowest (children).

For the following pseudocode, we have to make following assumptions:

1. a[i] – I

2. left(i) – 2I

3. right(i) – 2I+1

4. parent(i)- I/2

Max heap pseudocode:

Max_Heap(a,I)

1. l=left(I)

2. r=right(I)

3. if l<=a.heapsize and a[l]>a[I]

a. Largest = l

4. else

a. Largest = I

5. If r<= a.heapsize and a[r]>a[I]

a. Largest = r

6. else

a. Largest = I

7. if Largest != I

a. exchange a[I] with a[Largest]

b. Max_Heap(a,Largest)

8. Stop

This is how to max heap is generated.