Priority QueuesPriority queueA priority queue ADTJava 5’s PriorityQueue, IJava 5’s PriorityQueue, IIEvaluating implementationsArray implementationsLinked list implementationsBinary tree implementationsHeap implementationArray representation of a heapUsing the heapCommentsThe EndPriority Queues2Priority queueA stack is first in, last outA queue is first in, first outA priority queue is least-first-outThe “smallest” element is the first one removed(You could also define a largest-first-out priority queue)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 firstRemove any “smallest” element (don’t care which)Remove the first one added3A priority queue ADTHere is one possible ADT:PriorityQueue(): a constructorvoid add(Comparable o): inserts o into the priority queueComparable removeLeast(): removes and returns the least elementComparable getLeast(): returns (but does not remove) the least elementboolean isEmpty(): returns true iff emptyint size(): returns the number of elementsvoid clear(): discards all elementsJava now has a PriorityQueue class (new in Java 5)4Java 5’s PriorityQueue, I boolean add(E o)Adds the specified element to this queue. boolean offer(E o)Inserts the specified element into this priority queue. E peek()Retrieves, but does not remove, the head of this queue, returning null if this queue is empty. E poll()Retrieves and removes the head of this queue, or null if this queue is empty. int size()Returns the number of elements in this collection.5Java 5’s PriorityQueue, II void clear()Remove all elements from the priority queue. Comparator<? super E> comparator()Returns the comparator used to order this collection, or null if this collection is sorted according to its elements natural ordering (using Comparable). Iterator<E> iterator()Returns an iterator over the elements in this queue. boolean remove(Object o)Removes a single instance of the specified element from this collection, if it is present (optional operation).6Evaluating implementationsWhen we choose a data structure, it is important to look at usage patternsIf we load an array once and do thousands of searches on it, we want to make searching fast—so we would probably sort the arrayIf we load a huge array and expect to do only a few searches, we probably don’t want to spend time sorting the arrayFor almost all uses of a queue (including a priority queue), we eventually remove everything that we addHence, when we analyze a priority queue, neither “add” nor “remove” is more important—we need to look at the timing for “add + remove”7Array implementationsA 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) timeThis is an inefficient representationA 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) timeAgain, this is inefficient8Linked list implementationsA priority queue could be implemented as an unsorted linked listAdding 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 listAdding 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) timeAgain, these are inefficient implementations9Binary tree implementationsA priority queue could be represented as a (not necessarily balanced) binary search treeInsertion 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 treeInsertion and removal could destroy the balanceWe need an algorithm to rebalance the binary treeGood rebalancing algorithms require only O(log n) time, but are complicated10Heap implementationA priority queue can be implemented as a heapIn order to do this, we have to define the heap propertyIn Heapsort, a node has the heap property if it is at least as large as its childrenFor a priority queue, we will define a node to have the heap property if it is as least as small as its children (since we are using smaller numbers to represent higher priorities)128 3Heapsort: Blue node has the heap property38 12Priority queue: Blue node has the heap property11Array representation of a heapLeft child of node i is 2*i + 1, right child is 2*i + 2Unless the computation yields a value larger than lastIndex, in which case there is no such childParent of node i is (i – 1)/2Unless i == 01214186833 12 6 18 14 8 0 1 2 3 4 5 6 7 8 9 10 11 12lastIndex = 512Using the heapTo add an element:Increase lastIndex and put the new value thereReheap the newly added nodeThis is called up-heap bubbling or percolating upUp-heap bubbling requires O(log n) timeTo remove an element:Remove the element at location 0Move 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 downDown-heap bubbling requires O(log n) timeThus, it requires O(log n) time to add and remove an element13CommentsA priority queue is a data structure that is designed to return elements in order of priorityEfficiency is usually measured as the sum of the time it takes to add and to remove an elementSimple implementations take O(n) timeA heap implementation takes O(log n) timeThus, for any sort of heavy-duty use, a heap implementation is betterMy recommendation:If you need a priority queue, define it as an ADTStart with a simple implementationKeep the implementation hidden so you can change it later14The
View Full Document
Unlocking...