CompSci 100e 8.1 Scoreboard !! What else might we want to do with a data structure? Algorithm Insertion Deletion Search Unsorted Vector/array Sorted vector/array Linked list Hash Maps Binary search tree AVL tree CompSci 100e 8.2 Priority Queues !! Basic operations !! Insert !! Remove largest !! What properties must the data have? !! Applications !! Event-driven simulation: Colliding particles !! AI A* - Best-first search !! Operating systems Load balancing & scheduling !! Statistics Maintain largest m values !! Graph searching Dijkstra's algorithm !! Data Compression: Huffman coding CompSci 100e 8.3 Data Compression !! Compression is a high-profile application !! .zip, .mp3, .jpg, .gif, .gz, … !! What property of MP3 was a significant factor in what made Napster work (why did Napster ultimately fail?) !! Why do we care? !! Secondary storage capacity doubles every year !! Disk space fills up quickly on every computer system !! More data to compress than ever before CompSci 100e 8.4 More on Compression !! What’s the difference between compression techniques? !! .mp3 files and .zip files? !! .gif and .jpg? !! Lossless and lossy !! Is it possible to compress (lossless) every file? Why? !! Lossy methods !! Good for pictures, video, and audio (JPEG, MPEG, etc.) !! Lossless methods !! Run-length encoding, Huffman, LZW, … 11 3 5 3 2 6 2 6 5 3 5 3 5 3 10!CompSci 100e 8.5 Priority Queue !! Compression motivates the study of the ADT priority queue !! Supports two basic operations •! insert -– an element into the priority queue •! delete – the minimal element from the priority queue !! Implementations may allow getmin separate from delete •! Analogous to top/pop, front/dequeue in stacks, queues !! See PQDemo.java and UsePQ.java, !! code below sorts, complexity? Scanner s; PriortyQueue pq = new PriorityQueue(); while (s.hasNext()) pq.add(s.next()); while (pq.size() > 0) { System.out.println(pq.remove()); } CompSci 100e 8.6 Priority Queue implementations !! Implementing priority queues: average and worst case Insert average Getmin (delete) Insert worst Getmin (delete) Unsorted vector Sorted vector Search tree Balanced tree Heap !! Heap has O(1) find-min (no delete) and O(n) build heap CompSci 100e 8.7 PriorityQueue.java (Java 5) !! What about objects inserted into pq? !! If deletemin is supported, what properties must inserted objects have, e.g., insert non-comparable? !! Change what minimal means? !! Implementation uses heap !! If we use a Comparator for comparing entries we can make a min-heap act like a max-heap, see PQDemo !! Where is class Comparator declaration? How used? !! What's a static inner class? A non-static inner class? !! In Java 5 there is a Queue interface and PriorityQueue class !! The PriorityQueue class also uses a heap CompSci 100e 8.8 Sorting w/o Collections.sort(…) public static void sort(ArrayList<String> a) { PriorityQueue pq = new PriorityQueue<String>(); for(int k=0; k < a.size(); k++) pq.add(a.get(k)); for(int k=0; k < a.size(); k++) a.set(k,pq.remove()); } !! How does this work, regardless of pqueue implementation? !! What is the complexity of this method? !! add O(1), remove O(log n)? If add O(log n)? !! heapsort uses array as the priority queue rather than separate pq object. !! From a big-Oh perspective no difference: O(n log n) •!Is there a difference? What’s hidden with O notation?CompSci 100e 8.9 Priority Queue implementation !! PriorityQueue uses heaps, fast and reasonably simple !! Why not use inheritance hierarchy as was used with Map? !! Trade-offs when using HashMap and TreeMap: •! Time, space •! Ordering properties, e.g., what does TreeMap support? !! Changing method of comparison when calculating priority? !! Create object to replace, or in lieu of compareTo •! Comparable interface compares this to passed object •! Comparator interface compares two passed objects !! Both comparison methods: compareTo() and compare() •! Compare two objects (parameters or self and parameter) •! Returns –1, 0, +1 depending on <, ==, > CompSci 100e 8.10 Creating Heaps !! Heap is an array-based implementation of a binary tree used for implementing priority queues, supports: !! insert, findmin, deletemin: complexities? !! Using array minimizes storage (no explicit pointers), faster too --- children are located by index/position in array !! Heap is a binary tree with shape property, heap/value property !! shape: tree filled at all levels (except perhaps last) and filled left-to-right (complete binary tree) !! each node has value smaller than both children CompSci 100e 8.11 Array-based heap !! store “node values” in array beginning at index 1 !! for node with index k !! left child: index 2*k !! right child: index 2*k+1 !! why is this conducive for maintaining heap shape? !! what about heap property? !! is the heap a search tree? !! where is minimal node? !! where are nodes added? deleted? 0 1 2 3 4 5 6 7 8 9 10 6 10 7 17 13 25 9 21 19 6 10 7 17 13 9 21 19 25 CompSci 100e 8.12 Thinking about heaps !! Where is minimal element? !! Root, why? !! Where is maximal element? !! Leaves, why? !! How many leaves are there in an N-node heap (big-Oh)? !! O(n), but exact? !! What is complexity of find max in a minheap? Why? !! O(n), but ! N? !! Where is second smallest element? Why? !! Near root? 6 10 7 17 13 9 21 19 25 0 1 2 3 4 5 6 7 8 9 10 6 10 7 17 13 25 9 21 19CompSci 100e 8.13 Adding values to heap !! to maintain heap shape, must add new value in left-to-right order of last level !! could violate heap property !! move value “up” if too small !! change places with parent if heap property violated !! stop when parent is smaller !! stop when root is reached !! pull parent down, swapping isn’t necessary (optimization) 13 6 10 7 17 9 21 19 25 8 13 6 10 7 17 9 21 19 25 6 10 7 17 9 21 19 25 13 8 insert 8 bubble 8 up 6 7 17 9 21 19 25 8 13 10 CompSci 100e 8.14 Adding values, details (pseudocode) void add(Object elt) { // add elt to heap in myList myList.add(elt); int loc = myList.size(); while (1 < loc && elt < myList[loc/2]) { myList[loc] = myList[loc/2]; loc = loc/2; // go to parent } // what’s true here? myList.set(loc,elt); } 13 6 10 7 17 9 21 19 25 8 13 6 10 7 17 9 21 19 25 0 1 2 3 4 5 6 7 8 9 10 6 10 7 17 13 25 9 21 19 tvector myList CompSci 100e 8.15 Removing minimal element !! Where is minimal
View Full Document
Unlocking...