CSI 2110 Lecture Notes - Lecture 5: Priority Queue, Total Order, Insertion Sort

83 views2 pages

Document Summary

A set of elements each with a given priority. Elements are sorted based on priority not position. In a priority queue, each entry is a pair of (key, element) Two distinct entries can have the same key. Elements are ranked with a total order relation. A total order relation but have totality, antisymmetry, and transitivity. For example: >= and <= are total ordering, but < and > are only partial ordering as they don"t have totality. External to keys and used to compare two objects. Implementation with an unsorted sequence removemin() is always o(n) Implementation with a sorted sequence removemin() is at most o(n) Input: a sequence s storing n elements on which a total order relation is defined, and a priority queue p that compares keys with the same relation. Output: the sequence s sorted by the total order relation. Variation of priorityqueuesort that uses an unorted sequence to implement the priority queue.

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