1More on ADTs: Priority Queues & DictionariesLecture 17CS211 – Fall 2005Announcements• Assignment 5 is online (since Friday) Due Wednesday, Nov 2 Multiple small tasksHeaps• A heap is a tree that Has a particular shape (we’ll come back to this) and Has the heap property• Heap property Each node’s value (its priority) is ≤ the value of its parent This version is for a max-heap (max value at the root)• There is a similar heap property for a min-heap (min at the root)4115202733221041152033272210Has heap propertyDoes not have heap propertyHeap Implementation (the Big Trick)• Can avoid using pointers!• Use a complete binary tree stored in an array Definition: Complete means that each level of the tree is filled except possibly the last, which is filled from left to right•For A[i] left child = 2 * i right child = 2 * i + 1 parent = i / 2A[i]A[2∗i] A[2∗i+1]Insert and GetMax Pseudocodeinsert (Item):Place item in a leaf (= next empty position in array);while (item > parent) {Swap item with parent;} // BubbleUpgetMax ():max = root.value;Swap root and last item (call it v) in heap; // Ensures same shape for heapDecrease heap size by 1 (i.e., access less of the array);while (v < one of its children) // BubbleDown{Swap v with its largest child;}return max;To Build a Heap• How long to construct a heap, given the items?• Worst-case time for insert() is O(log n)• Total time to build heap using insert() isO(log 1) + O(log 2) + ... + O(log n)or O(n log n)Can we do better?• We had two heap-fixing methodsbubbleUp: move up the tree as long as we’re > our parentbubbleDown: move down the tree as long as we’re < one of our children• If we build the heap from the bottom-up using bubbleDown then we can build it in time O(n) (Wow!)2Efficient Heap Building• Build from the bottom-up• If there are n items in the heap then... There are about n/2 mini-heaps of height 1 There are about n/4 mini-heaps of height 2 There are about n/8 mini-heaps of height 3 and so on• The time to fix up a mini-heap is O(its height)• Total time spent fixing heaps is thus bounded byn/2 + 2n/4 + 3n/8 + ....• This can be rewritten asn(1/2 + 2/4 + ... + i/2i+ ...)= n(2)• Thus total heap-building time (using the bottom-up method) is O(n)HeapSort• Given a Comparable[ ] array of length n, Put all n elements into a heap: O(n) or O(n log n) Repeatedly get the min: O(n log n)public static void heapSort(Comparable[] a) {PriorityQueue<Comparable> pq = new PQ<Comparable>();for (Comparable x : a) { pq.put(x); }for (int i = 0; i < a.length; i++) { a[i] = pq.get(); }}PQ Application: Simulation• Example: Given a probabilistic model of bank-customer arrival times and transaction times, how many tellers are needed Assume we have a way to generate random inter-arrival times Assume we have a way to generate transaction times Can simulate the bank to get some idea of how long customers must waitTime-Driven Simulation• Check at each tick to see if any event occursEvent-Driven Simulation• Advance clock to next event, skipping intervening ticks• This uses a PQ!Another PQ Implementation• If there are only a few possible priorities then can use an array of queues Each array position represents a priority (0..m-1 where m is the array size) Each queue holds all items that have that priority• One text [Skiena] calls this a bounded height priority queue• Time for insert: O(1)• Time for getMax: O(m) in the worst-case Generally, faster• Example: airline check-inm-101Other PQ Operationsdeletea particular itemupdatean item (change its priority)jointwo priority queues• For delete and update, we need to be able to find the item One way to do this: Use a Dictionary to keep track of the item’s position in the heap• Efficient joining of 2 Priority Queues requires another data structure Skew Heaps or Pairing Heaps (Chapter 23 in text)Recall: Sets & Dictionaries• ADT SetOperations:void insert (Object element);boolean contains (Object element);void remove (Object element);boolean isEmpty ( );void makeEmpty ( ); Note: no duplicates allowed• A “set” with duplicates is usually called a bag• Where used: Wide use within other algorithms• ADT DictionaryOperations:void insert (Object key, Object value);void update (Object key, Object value);Object find (Object key);void remove (Object key);boolean isEmpty ( );void makeEmpty ( ); Think of key = word; value = definition• Where used: Symbol tables Wide use within other algorithms3Implementing Sets• Recall: ADT SetOperations:void insert (Object element);boolean contains (Object element);void remove (Object element);boolean isEmpty ( );void makeEmpty ( );• Can use a Dictionary Values in (key, value) pairs are ignored All operations are expected time O(1) using hash table (see next several slides)• If the universe is not too large Can use a table of bits (i.e., a bit-vector)• We need n bits for a universe of size n This implementation also allows for fast union, intersection, and complementGoal: Design a Dictionary• Operations void insert (key,value) void update (key, value) Object find (key) void remove (key)Array implementation:Uses an array of (key,value) pairsUnsorted Sortedinsert O(1) O(n)update O(n) O(log n)find O(n) O(log n)remove O(n) O(n)n is the number of items currently held in the arrayDirect Address Table• Assumes the key set is from a small Universe• Example: Addresses on my street Start at 1, go to 40 A few lots don’t have houses• For a Direct Address Table, we make an array as large as the Universe• To find an entry, we just index to that entry of the array• Dictionary operations all take O(1) timeWhat if the Universe is large?• Idea is to re-use table entries via a hash functionh•h: U → [0,…,m-1]where m = table size•h must Be easy to compute Cause few collisions Have equal probability for each table positionTypical situation:U = all legal identifiersTypical hash function:h converts each letter to a number and we compute a function of these numbersA Hashing Example• Suppose each word below has the following hashCodejan 7feb 0mar 5apr 2may 4jun 7jul 3aug 7sep 2oct 5• How do we resolve collisions? We’ll use chaining: each table position is the head of a list For any particular problem, this might work terribly• In practice, using a good hash function, we
View Full Document
Unlocking...