Correct : b

Explanation:
To understand the worst-case running times of operations on a priority queue implemented via a max-heap, we look at how the tree structure is modified during insertion and deletion.
1. Worst-Case Analysis of INSERT(A, key):
• To insert a new element, it is initially placed at the next available leaf position at the bottom of the complete binary tree to maintain the structural property.
• To restore the max-heap property (where a parent must be greater than or equal to its children), the newly added element is swapped upward with its parent iteratively. This process is called heapify-up or percolate-up.
• In the worst-case scenario, the new key is larger than all existing elements and travels from the leaf all the way up to the root node.
• Since a complete binary tree with n elements has a height of ⌊log₂(n)⌋, the maximum number of levels it can traverse is proportional to the height. Thus, the worst-case time complexity is O(log(n)).
2. Worst-Case Analysis of EXTRACT-MAX(A):
• The maximum element in a max-heap is always located at the root node, which can be accessed in O(1) time.
• However, removing the root leaves a hole at the top. To fix this, the last element at the deepest leaf position is moved to the root.
• To restore the max-heap property, this element is then swapped downward with its largest child iteratively until it finds its correct position. This process is called heapify-down or percolate-down.
• In the worst-case scenario, the swapped element is smaller than most elements and travels from the root down to the bottom-most leaf level.
• Just like insertion, this traversal path is bounded by the height of the tree. Therefore, the worst-case time complexity is O(log(n)).
3. Conclusion:
Both maintenance operations require a tree traversal up or down the height of the tree in the worst case, making O(log(n)) the correct runtime bound for both, matching option (b).