Fast Priority Queue that\'s too fast prove it wrong The answer should focus on e
ID: 641686 • Letter: F
Question
Fast Priority Queue that's too fast prove it wrong
The answer should focus on explaning the 3 reasons above. show that quenue is not omparison-based. Why the implementation is not correct. Analyze the running time.
You receive a sales call from a new start-up called MYPD (which stands for "Manage Your Pr orities... Differently"). The MYPD agent tells you that they just developed a ground-breaking comparison-based priority queue. This queue implements Insert in time log2(Vn) and Ertract mar in time log2n. Explain to the agent that the company can soon be sued by its competitors be cause either (1) the queue is not comparison-based; or (2) the queue implementation is not correct; or (3) the running time they claim cannot be so good. To put differently, no such comparison-based priority queue can exist. (Hint: You can use the following Sterling's approximation:n!() (where e is euler's constant))Explanation / Answer
(1)
A priority queue is not comparison based. It is an abstract data type which is like a regular queue or stack data structure, but where additionally each element has a "priority" associated with it. In a priority queue, an element with high priority is served before an element with low priority. If two elements have the same priority, they are served according to their order in the queue.
Insert just puts the element onto the linked list.Insert increases the size of the heap, then chases up the tree looking for the right place for the new element .
Extract-Max (S) removes and returns the element with largest key.
While priority queues are often implemented with heaps, they are conceptually distinct from heaps. A priority queue is an abstract concept like "a list" or "a map"; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods such as an unordered array.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.