Solution

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.