Kĩ thuật lập trình - Heaps and priority queues

Heaps and Priority Queues2HCREA6TPCopyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Learn about heaps Review the java.util.PriorityQueue classLearn about Heapsort2Priority QueuesA priority queue is a data structure for temporary storage that delivers the stored items in order of their priority: an item with higher priority is delivered first.The objects in a priority queue are Comparable (or a comparator is provided).According to a convention, the smaller item has higher priority.3Possible ImplementationsA sorted list: items are stored in order of priority remove and peek are O(1), but add is O(n).An unsorted list: items are stored in order of their arrival add is O(1) but remove and peek are O(n).Either way, one of the methods creates a bottleneck.4HeapsA heap is a particular kind of a binary tree.Heaps provide a way to implement priority queues in such a way that both add and remove take O(log n) time.A heap can be stored in an array (or in an ArrayList).5Full and Complete Binary TreesFull tree:all levels are filled; a full tree with h levels holds 2h - 1 nodes.Complete tree:all levels are filled, except perhaps the bottom one 6Complete TreesNodes can be numbered in level-by-level order: The parent of the i-th node is the node i / 2The left child of the i-th node is the node 2*i and the right child is the node 2*i + 17Complete Trees (cont’d)It is convenient to store a complete binary tree in an array in the order of nodes, starting at index 1: 8Heaps (cont’d)A (min) heap is a complete binary treeThe value in each node does not exceed any of the values in that node’s left and right subtrees.In a heap, the root holds the smallest value. 3 / \ 12 8 / \ 12 20 3 / \ 12 20 / \ 12 8A heap:Not a heap:9Heaps (cont’d)The algorithm for add uses the reheap-up procedure.The algorithm for remove uses the reheap-down procedure.Either adding or removing an item takes O(log n) time.Remove the root and place the last leaf at the root. Starting at the root, swap the node with its smaller child, as many times as needed to repair the heap.Add a leaf. Starting at the last leaf, swap the node with its parent as many times as needed to repair the heap.10The add AlgorithmStep 1: the new value is added as the rightmost leaf at the bottom level, keeping the tree completeStep 2: “reheap up”: the new value keeps swapping places with its parent until it falls into place11The remove AlgorithmStep 1: the root is removed Step 2: the rightmost leaf from the bottom level replaces the rootStep 3: “reheap down”: the new root value keeps swapping places with its smaller child until it falls into place12 boolean isEmpty (); void add (E obj); E remove (); E peek ();java.util.PriorityQueueImplements java.util.Queue with methods:The implementation is a heap.add and remove are O(log n); peek is O(1).13HeapsortA relatively fast algorithm for sortingPlace all values into a heapRemove values one by one (they come out in ascending order) and add them to the output listHeapsort can be implemented in the same array, without a temporary heap:1. Rearrange the values to make a max-heap2. Rearrange the values again to get a sorted arrayThe running time is O(n log n).14Review:What is a priority queue?What is wrong with implementing a priority queue as a sorted list?What is a complete binary tree?If a complete tree is stored in an array with the first node in items [1], where can we find the parent of the 5-th node? Its left and right children?15Review (cont’d):What is a heap?Describe the main steps in the algorithm for removing the smallest value from a heap.Describe the main steps in the algorithm for adding a value to a heap.What is the main idea of Heapsort?16