UGC NET CSE | June 2023 | Part 2: 21

Question

Consider the following statements about heap sort algorithm:

• A. The MAX-HEAPIFY procedure which runs in $\mathrm{O} \lg (n)$ time, is the key to maintaining the max heap property
• B. The BUILD-MAX-HEAP procedure, which runs in $\mathrm{O} \lg (n)$ time, produces max-heap from an unordered input array
• C. The MAX-HEAP-INSERT, which runs in $\text{O}$ $(\lg n)$ time, implements the insertion operation
• D. 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{A, B}$ only
• B. $\text{A, C}$ only
• C. $\text{B, D}$ only
• D. $\text{A, B, C, D}$

 

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)