Discussion
Let A be a priority queue for maintaining a set of elements. Suppose A is implemented using a max-heap data structure. The operation Extract-Max(A) extracts and deletes the maximum element from A. The operation Insert(A,key) inserts a new element key in A. The properties of a max-heap are preserved at the end of each of these operations.
When A contains n elements, which one of the following statements about the worst case running time of these two operations is TRUE?
Answer: B
Both Extract-Max(A) and Insert(A,key) run in \(O(\log(n))\).
Extract-Max reads the maximum at the root in constant time, but it must also delete it: the last element is moved to the root and sifted down, swapping with the larger child until the heap property holds again. That can take one swap per level, and a heap of n elements has about \(\log_{2} n\) levels.
Insert places the new key in the next free leaf and sifts it up towards the root, again at most one swap per level, \(O(\log(n))\).
The options with Extract-Max in \(O(1)\) confuse finding the maximum with extracting it while keeping a valid heap. Insert is never \(O(n)\) in a binary heap, and neither operation is \(O(1)\) in the worst case.
Post your comment
Please log in or register to post a comment.
Examination Categories
- SSC Exams
- Banking Exams
- Teaching Exams
- Civil Services Exams
- Railways Exams
- Engineering Recruitment Exams
- Defence Exams
- State Government Exams
- Police Exams
- Insurance Exams
- Nursing Exams
- Other Government Exams
- NRA CET
- PG Entrance Exams
- Campus Placement
- MBA Entrance Exams
- CUET and UG Entrance
- Judiciary Exams
- Regulatory Body Exams
- Software Development