Min-Heap

The order of elements in the min-heap is different to the order of elements in the max-heap. In the max-heap, the element of the root should be greater than or equal to the elements of its children. In the min-heap, the element of the root should be less than or equal to the elements of its children.

The procedure of MIN-HEAPIFY is similar to the procedure of MAX-HEAPIFY, except in some conditions. The procedure of MIN-HEAPIFY is as follows:

1

2

3 if and

4

5 else

6 if and

7

8 if

9 exchange with

10

The following steps are changed in the MIN-HEAPIFY procedure, when compared to the MAX-HEAPIFY procedure.

The heading is changed to

The variable largest is changed to least.

In line 3, the condition is changed to

In line 6, the condition is changed to

In line 9, the value is changed to

In line 10, the call is changed to

There are no other changes in the loops or procedure. So, the running time of MIN-HEAPIFY procedure is the same as the running time of MAX-HEAPIFY procedure. Therefore, the running time of MIN-HEAPIFY procedure is .

MAX–HEAPIFY does not cause any changes to the heap tree for.

When, the node is a leaf node. It does not have any left or right children.

Hence, there will not be any change in the heap tree.

Example: Consider the following heap tree.

In this max–heap, . Then

For, i will be 4, 5, 6. The nodes at 4, 5 ,6 do not contain any left or right sub trees or children.

Hence, MAX – HEAPIFY does not cause any effect.

Following is the modified MAX-HEAPIFY procedure using iterative control structure:

Iterative-MAX-HEAPIFY (A, i)

// Execute the loop while true

1. while (true)

// Assign the node LEFT(i) to left

2. left = LEFT(i)

// Assign the node RIGHT(i)to right

3. right = RIGHT(i)

// Check whether left A.heap-size and A[left] > A[i].

// If true then assign left to largest.

//If false then assign index i to largest.

4. if left A.heap-size and A[left] > A[i]

5. largest = left

6. else

7. largest = i

// Check whether rA.heap-size and A[r]>A[largest]

// If true then assign r to largest.

8. if r A.heap-size and A[r] > A[largest]

9. largest = r

// Check whether i is equal to largest.

// If false then swap A[i] and A[largest].

10. if largest i

11. Exchange A[i] with A[Largest]

12. if largest = i

13. break

// Assign largest to i

14. i = largest