CSI 2110 Lecture Notes - Lecture 5: Priority Queue, Total Order, Insertion Sort
7 Nov 2017
School
Department
Course
Professor
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.
