6.006 Introduction to Algorithms, Lecture 8: Binary Heaps

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Lecture 8: Binary Heaps Lecture 8: Binary Heaps Priority Queue Interface • Keep track of many items, quickly access/remove the most important – Example: router with limited bandwidth, must prioritize certain kinds of messages – Example: process scheduling in operating system kernels – Example: discrete-event simulation (when is next occurring event?) – Example: graph algorithms (later in the course) • Order items by key = priority so Set interface (not Sequence interface) • Optimized for a particular subset of Set operations: build(X) insert(x) delete max() find max() build priority queue from iterable X add item x to data structure remove and return stored item with largest key return stored item with largest key • (Usually optimized for max or min, not both) • Focus on insert and delete max operations: build can repeatedly insert; find max() can insert(delete min()) Priority Queue Sort • Any priority queue data structure translates into a sorting algorithm: – build(A), e.g., insert items one by one in input order – Repeatedly delete min() (or delete max()) to determine (reverse) sorted order • All the hard work happens inside the data structure • Running time is Tbuild + n · Tdelete max ≤ n · Tinsert + n · Tdelete max • Many sorting algorithms we’ve seen can be viewed as priority queue sort: Priority Queue Data Structure Dynamic Array Sorted Dynamic Array Set AVL Tree Goal Operations O(·) build(A) insert(x) delete max() n n log n n log n 1(a) n log n n 1(a) log n Priority Queue Sort Time In-place? 2 n Y n2 Y n log n N log n(a) log n(a) n log n n Y Selection Sort Insertion Sort AVL Sort Heap Sort 2 Lecture 8: Binary Heaps Priority Queue: Set AVL Tree • Set AVL trees support insert(x), find min(), find max(), delete min(), and delete max() in O(log n) time per operation • So priority queue sort runs in O(n log n) time – This is (essentially) AVL sort from Lecture 7 • Can speed up find min() and find max() to O(1) time via subtree augmentation • But this data structure is complicated and resulting sort is not in-place • Is there a simpler data structure for just priority queue, and in-place O(n lg n) sort? YES, binary heap and heap sort • Essentially implement a Set data structure on top of a Sequence data structure (array), using what we learned about binary trees Priority Queue: Array • Store elements in an unordered dynamic array • insert(x): append x to end in amortized O(1) time • delete max(): find max in O(n), swap max to the end and remove • insert is quick, but delete max is slow • Priority queue sort is selection sort! (plus some copying) Priority Queue: Sorted Array • Store elements in a sorted dynamic array • insert(x): append x to end, swap down to sorted position in O(n) time • delete max(): delete from end in O(1) amortized • delete max is quick, but insert is slow • Priority queue sort is insertion sort! (plus some copying) • Can we find a compromise between these two array priority queue extremes? Lecture 8: Binary Heaps 3 Array as a Complete Binary Tree • Idea: interpret an array as a complete binary tree, with maximum 2i nodes at depth i except at the largest depth, where all nodes are left-aligned 1 2 3 4 d0 d1 d2 d3 ______O____ ____O____ __O__ __O__ __O O O O O O • Equivalently, complete tree is filled densely in reading order: root to leaves, left to right • Perspective: bijection between arrays and complete binary trees 1 2 3 4 5 Q = [0,1,2,3,4,5,6,7,8,9] d0 0 d1 1 2 d2 3 4 5 6 d3 7 8 9 -> -> -> -> ______0____ ____1____ __2__ __3__ __4 5 6 7 8 9 • Height of complete tree perspective of array of n item is dlg ne, so balanced binary tree Implicit Complete Tree • Complete binary tree structure can be implicit instead of storing pointers • Root is at index 0 • Compute neighbors by index arithmetic: left(i) = 2i + 1 right(i) = 2i + 2   i−1 parent(i) = 2 4 Lecture 8: Binary Heaps Binary Heaps • Idea: keep larger elements higher in tree, but only locally • Max-Heap Property at node i: Q[i] ≥ Q[j] for j ∈ {left(i), right(i)} • Max-heap is an array satisfying max-heap property at all nodes • Claim: In a max-heap, every node i satisfies Q[i] ≥ Q[j] for all nodes j in subtree(i) • Proof: – Induction on d = depth(j) − depth(i) – Base case: d = 0 implies i = j implies Q[i] ≥ Q[j] (in fact, equal) – depth(parent(j)) − depth(i) = d − 1 < d, so Q[i] ≥ Q[parent(j)] by induction – Q[parent(j)] ≥ Q[j] by Max-Heap Property at parent(j) • In particular, max item is at root of max-heap Heap Insert • Append new item x to end of array in O(1) amortized, making it next leaf i in reading order • max heapify up(i): swap with parent until Max-Heap Property – Check whether Q[parent(i)] ≥ Q[i] (part of Max-Heap Property at parent(i)) – If not, swap items Q[i] and Q[parent(i)], and recursively max heapify up(parent(i)) • Correctness: – Max-Heap Property guarantees all nodes ≥ descendants, except Q[i] might be > some of its ancestors (unless i is the root, so we’re done) – If swap necessary, same guarantee is true with Q[parent(i)] instead of Q[i] • Running time: height of tree, so Θ(log n)! Lecture 8: Binary Heaps 5 Heap Delete Max • Can only easily remove last element from dynamic array, but max key is in root of tree • So swap item at root node i = 0 with last item at node n − 1 in heap array • max heapify down(i): swap root with larger child until Max-Heap Property – Check whether Q[i] ≥ Q[j] for j ∈ {left(i), right(i)} (Max-Heap Property at i) – If not, swap Q[i] with Q[j] for child j ∈ {left(i), right(i)} with maximum key, and recursively max heapify down(j) • Correctness: – Max-Heap Property guarantees all nodes ≥ descendants, except Q[i] might be < some descendants (unless i is a leaf, so we’re done) – If swap is necessary, same guarantee is true with Q[j] instead of Q[i] • Running time: height of tree, so Θ(log n)! Heap Sort • Plugging max-heap into priority queue sort gives us a new sorting algorithm • Running time is O(n log n) because each insert and delete max takes O(log n) • But often include two improvements to this sorting algorithm: In-place Priority Queue Sort • Max-heap Q is a prefix of a larger array A, remember how many items |Q| belong to heap • |Q| is initially zero, eventually |A| (after inserts), then zero again (after deletes) • insert() absorbs next item in array at index |Q| into heap • delete max() moves max item to end, then abandons it by decrementing |Q| • In-place priority queue sort with Array is exactly Selection Sort • In-place priority queue sort with Sorted Array is exactly Insertion Sort • In-place priority queue sort with binary Max Heap is Heap Sort 6 Lecture 8: Binary Heaps Linear Build Heap • Inserting n items into heap calls max heapify up(i) for i from 0 to n − 1 (root down): worst-case swaps ≈ n−1 X depth(i) = n−1 X i=0 lg i = lg(n!) ≥ (n/2) lg(n/2) = Ω(n lg n) i=0 • Idea! Treat full array as a complete binary tree from start, then max heapify down(i) for i from n − 1 to 0 (leaves up):   n−1 n−1 X X nn nn worst-case swaps ≈ height(i) = (lg n−lg i) = lg = Θ lg √ = O(n) n! n(n/e)n i=0 i=0 • So can build heap in O(n) time • (Doesn’t speed up O(n lg n) performance of heap sort) Sequence AVL Tree Priority Queue • Where else have we seen linear build time for an otherwise logarithmic data structure? Sequence AVL Tree! • Store items of priority queue in Sequence AVL Tree in arbitrary order (insertion order) • Maintain max (and/or min) augmentation: node.max = pointer to node in subtree of node with maximum key – This is a subtree property, so constant factor overhead to maintain • find min() and find max() in O(1) time • delete min() and delete max() in O(log n) time • build(A) in O(n) time • Same bounds as binary heaps (and more) Set vs. Multiset • While our Set interface assumes no duplicate keys, we can use these Sets to implement Multisets that allow items with duplicate keys: – Each item in the Set is a Sequence (e.g., linked list) storing the Multiset items with the same key, which is the key of the Sequence • In fact, without this reduction, binary heaps and AVL trees work directly for duplicate-key items (where e.g. delete max deletes some item of maximum key), taking care to use ≤ constraints (instead of < in Set AVL Trees)