Consider the following statements about heap sort algorithm A. The MAX-HEAPIFY…
2023
Consider the following statements about heap sort algorithm
A. The MAX-HEAPIFY procedure which runs in O(lg n) time, is the key to maintaining the max heap property
B. The BUILD-MAX-HEAP procedure, which runs in O(lg n) time, produces max-heap from an unordered input array
C. The MAX-HEAP-INSERT, which runs in O(lg n) time, implements the insertion operation
D. The HEAP-INCREASE-KEY procedure runs in O(n lg n) time, to set the key of new node of its correct value
Choose the correct answer
- A.
A, B only
- B.
A, C only
- C.
B, D only
- D.
A, B, C, D
Attempted by 184 students.
Show answer & explanation
Correct answer: B
Statement A is correct because MAX-HEAPIFY maintains the heap property in O(lg n) time. Statement B is incorrect as BUILD-MAX-HEAP runs in linear O(n) time. Statement C is correct since MAX-HEAP-INSERT operates in O(lg n). Statement D is incorrect because HEAP-INCREASE-KEY also runs in O(lg n), not O(n lg n). Thus, only A and C are true.
A video solution is available for this question — log in and enroll to watch it.