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**.

Question

Thunder Thighs

Computers & Technology

1 June, 12:17

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**.

+2

Answers (1)

Know the Answer?

Emmanuel Powers · 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 la[I]

a. Largest = l

4. else

a. Largest = I

5. If ra[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.