CSC 3102 Chapter : Heaps And Priority Queues

11 views2 pages
15 Mar 2019
School
Course
Professor

Document Summary

A priority queue is a queue where removal depends not upon order of insertion but upon importance. Keys must have a comparison operation that is reflexive, antisymmetric, and transitive. Such a queue is straightforwardly implemented using a list. A priority queue gives a straightforward scheme for sorting: insert all elements into the priority queue and simply read them back out. The priority queue sorting scheme, implemented using sorted and unsortes lists, gives rise to the insertion-sort and selection-sort algorithms, respectively. If we can improve the performance of the priority queue, we can naturally improve the performance of sorting. If v is the root then f(v)=1 . Applying the priority queue sorting scheme to a heap results in an o(nlogn) sort. The vector representation of the heap also gives rise to an extremely efficient in- place sorting algorithm. If u is the right child of v then f(u)=2f(v)+1 . If u is the left child of v then f(u)=2f(v) .

Get access

Grade+20% off
$8 USD/m$10 USD/m
Billed $96 USD annually
Grade+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
40 Verified Answers
Class+
$8 USD/m
Billed $96 USD annually
Class+
Homework Help
Study Guides
Textbook Solutions
Class Notes
Textbook Notes
Booster Class
30 Verified Answers

Related Documents