DOC PREVIEW
Penn CIT 594 - Priority Queues

This preview shows page 1-2-3 out of 10 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 10 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Priority QueuesPriority queueA priority queue ADTArray implementationsLinked list implementationsBinary tree implementationsHeap implementationArray representation of a heapUsing the heapThe EndPriority QueuesPriority queue•A stack is first in, last out•A queue is first in, first out•A priority queue is least-first-out–The “smallest” element is the first one removed–The definition of “smallest” is up to the programmer (for example, you might define it by implementing Comparator or Comparable)–If there are several “smallest” elements, the implementer must decide which to remove first•Remove any “smallest” element (don’t care which)•Remove the first one addedA priority queue ADT•Here is one possible ADT:–PriorityQueue(): a constructor–void add(Comparable o): inserts o into the priority queue–Comparable removeLeast(): removes and returns the least element–Comparable getLeast(): returns (but does not remove) the least element–boolean isEmpty(): returns true iff empty–int size(): returns the number of elements–clear(): discards all elementsArray implementations•A priority queue could be implemented as an unsorted array (with a count of elements)–Adding an element would take O(1) time (why?)–Removing an element would take O(n) time (why?)–Hence, adding and removing an element takes O(n) time–This is a very inefficient representation•A priority queue could be implemented as a sorted array (again, with a count of elements)–Adding an element would take O(n) time (why?)–Removing an element would take O(1) time (why?)–Hence, adding and removing an element takes O(n) time–Again, this is very inefficientLinked list implementations•A priority queue could be implemented as an unsorted linked list–Adding an element would take O(1) time (why?)–Removing an element would take O(n) time (why?)•A priority queue could be implemented as a sorted linked list–Adding an element would take O(n) time (why?)–Removing an element would take O(1) time (why?)•As with array representations, adding and removing an element takes O(n) time–Again, this is very inefficientBinary tree implementations•A priority queue could be represented as a (not necessarily balanced) binary search tree–Insertion times would range from O(log n) to O(n) (why?)–Removal times would range from O(log n) to O(n) (why?)•A priority queue could be represented as a balanced binary search tree–Insertion and removal could destroy the balance–We haven’t discussed yet how to rebalance a binary tree–Good rebalancing algorithms require only O(log n) time, but are complicatedHeap implementation•A priority queue can be implemented as a heap•In order to do this, we have to redefine the heap property–In Heapsort, a node had the heap property if it was at least as large as its children–For a priority queue, we will define a node to have the heap property if it is as least as small as its children128 3Heapsort: Blue node has the heap property38 12Priority queue: Blue node has the heap propertyArray representation of a heap•Left child of node i is 2*i + 1, right child is 2*i + 2–Unless the computation yields a value larger than lastIndex, in which case there is no such child•Parent of node i is (i – 1)/2–Unless i == 01214186833 12 6 18 14 8 0 1 2 3 4 5 6 7 8 9 10 11 12lastIndex = 5Using the heap•To add an element:–Increase lastIndex and put the new value there–Reheap the newly added node•This is called up-heap bubbling or percolating up•Up-heap bubbling requires O(log n) time•To remove an element:–Remove the element at location 0–Move the element at location lastIndex to location 0, and decrement lastIndex –Reheap the new root node (the one now at location 0)•This is called down-heap bubbling or percolating down•Down-heap bubbling requires O(log n) time•Thus, it requires O(log n) time to add and remove an elementThe


View Full Document

Penn CIT 594 - Priority Queues

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Priority Queues
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Priority Queues and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Priority Queues 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?