Discussion
Which of the following operations on a priority queue implemented using a binary heap requires Theta of (log n) time ?
Answer: C
The operation that takes Θ(log n) is deleting the minimum element.
In a binary min-heap the minimum is at the root. To delete it, the last element is moved to the root and then sifted down, swapping with its smaller child at each level until the heap property holds. The heap is a complete binary tree of height about log2 n, so this takes Θ(log n) time.
Checking the size reads a counter, Θ(1). Accessing the minimum reads the root, also Θ(1). Building a heap of n elements with bottom-up heapify takes Θ(n), because most nodes sit near the bottom and sift down only a little; inserting them one at a time would take O(n log n), but neither is Θ(log n).
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