Consider an ordinary binary min-heap data structure with n elements. supporting the instructions INSERT and EXTRACT-MIN in O(lgn) worst- case time. Give a potential function such that the amortized cost of INSERT is O(lgn) and the amortized cost of EXTRACT-MIN is O(1), and show that it works.

icon
Related questions
Question

Plz  solve  correctly  it is already  solved  but wrong  plz give correct solution. 

Consider an ordinary binary min-heap data structure with n elements.
supporting the instructions INSERT and EXTRACT-MIN in O(lgn) worst-
case time. Give a potential function such that the amortized cost of
INSERT is O(lgn) and the amortized cost of EXTRACT-MIN is 0(1), and
show that it works.
Transcribed Image Text:Consider an ordinary binary min-heap data structure with n elements. supporting the instructions INSERT and EXTRACT-MIN in O(lgn) worst- case time. Give a potential function such that the amortized cost of INSERT is O(lgn) and the amortized cost of EXTRACT-MIN is 0(1), and show that it works.
Expert Solution
trending now

Trending now

This is a popular solution!

steps

Step by step

Solved in 3 steps

Blurred answer