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 from the options given below:

Question

Question

This question was previously asked in

UGC NET Computer Science (Paper 2) 17 June 2023 Official Paper

Answer 1

The correct answer is A, C only

Key Points

A. The MAX-HEAPIFY procedure which runs in O(lg n) time, is the key to maintaining the max heap property.
- This statement is true. The MAX-HEAPIFY procedure is responsible for maintaining the max-heap property, and it indeed runs in O(log n) time.
B. The BUILD-MAX-HEAP procedure, which runs in O(lg n) time, produces a max-heap from an unordered input array.
- This statement is incorrect. The BUILD-MAX-HEAP procedure has a time complexity of O(n), not O(log n). It builds a max-heap from an unordered input array in linear time.
C. The MAX-HEAP-INSERT, which runs in O(lg n) time, implements the insertion operation.
- This statement is true. The MAX-HEAP-INSERT operation involves inserting a new element into the max-heap and then maintaining the max-heap property. Its time complexity is O(log n).
D. The HEAP-INCREASE-KEY procedure runs in O(n lg n) time to set the key of a new node to its correct value.
- This statement is incorrect. The time complexity of HEAP-INCREASE-KEY is O(log n), not O(n log n). It is used to increase the key of a node in a max-heap to its correct value.

Therefore, the correct answer is option 2) A, C only.