Sing, Pray Announcements =============== * How were the Help sessions? * Lab 7 (Hashing) Assigned - Map portion * Lab 6 (AVL) Due tomorrow - start with BSTree.java and then balance it. * Keep working to finish the projects! Outline =========================== Review * 20.3 Linear Probing * 20.4 Quadratic Probing * 20.5 Chaining New * 20.6 Hash Tables vs BSTs * 20.7 Hashing Applications * Lab 7 assigned (Hash Tables) * 21.1-21.2 Binary Heap Reading Notes: =========================== 21.1-21.2 Binary Heap ----------------------------- - A linked list or array requires that some operation use linear time. - An unbalanced binary search tree does not have a good worst case. A balanced search tree requires lots of work. - The priority queue has properties that are a compromise between a queue and a binary search tree - The binary heap is the classic method used to implement priority queues - The heap is a complete binary tree, allowing representation by a simple array and guaranteeing logarithmic depth <> - The parent is in position floor(i/2), the left child is in position 2i, and the right child is in position 2i+1 - The heap-order property states that, in a heap, the item in the parent is never larger than the item in a node. (heap-order property: In a heap, for every node X with parent P, the key in P is smaller than or equal to the key in X.) <> - A max heap supports acces to the maximum instead of the minimum. Minor changes can be used to implement max heaps. << Play "Heap or Not?" >> - If we need to place N items in the heap before the first deleteMin, pacing them in the array sloppily and then doing one buildHeap is more efficient than doing N insertions. << Show heap insertion >> - Insertion takes constant time on average but logarithmic time in the worst case. << Show deleteMin Operation >> - Deletion of the minimum involves placing the former last item in a hole that is created at the root. The hole is percolated down the tree through minumum children until the item can be placed without violating the heap property. - The deleteMin operation is logarithmic in both the worst and average cases. - The buildHeap operation can be done in linear time by applying a percolate down routine to nodes in reverse order. * buildHeap - Te buildHeap operation can be done in linear time by applying a percolate down routine to nodes in reverse level order. - The linear time bound can be shown by computing the sum of the heights of all the nodes in the heap. - We prove the bound for perfect trees by using a marking argument. * heapsort - By using parts of the array, we can perform the sort in place. - If we use a max heap, we obtain items in increasing order - Minor changes are required for the heapsort because the root is stored in position 0. 20.5 Chaining --------------- Separate chaining hashing is a space-efficient alternative to quadratic probing in which an array of linked lists is maintained. It is less sensitive to high load factors For separate chaining hashing, a reasonable load factor is 1.0. A lower load factor does not significantly improve performance; a moderately higher load factor is acceptable and can save space.