UGC NET CSE | June 2023 | Part 2: 21

Question

Consider the following statements about heap sort algorithm:

1. The MAX-HEAPIFY procedure which runs in $\mathrm{O} \lg (n)$ time, is the key to maintaining the max heap property
2. The BUILD-MAX-HEAP procedure, which runs in $\mathrm{O} \lg (n)$ time, produces max-heap from an unordered input array
3. The MAX-HEAP-INSERT, which runs in $\text{O}$ $(\lg n)$ time, implements the insertion operation
4. The HEAP-INCREASE-KEY procedure runs in $\text{O}$ $(\mathrm{n} \lg n)$ time , to set the key of new node of its correct value

Choose the correct answer from the options given below:

• A. $\text{I, II}$ only
• B. $\text{I, III}$ only
• C. $\text{II, IV}$ only
• D. $\text{I, II, III, IV}$

Answer 1

Ans : B. A and C are correct.

This is taken as it is from CLRS book (Heap chapter).

BUILD-MAX-HEAP runs in O(n) time.

 HEAP-INCREASE-KEY runs in runs in O(lg n)