6.006 Introduction to Algorithms, Recitation 8

Introduction to Algorithms: 6.006 Massachusetts Institute of Technology Instructors: Erik Demaine, Jason Ku, and Justin Solomon Recitation 8 Recitation 8 Priority Queues Priority queues provide a general framework for at least three sorting algorithms, which differ only in the data structure used in the implementation. algorithm Selection Sort Insertion Sort Heap Sort data structure Array Sorted Array Binary Heap insertion O(1) O(n) O(log n) extraction O(n) O(1) O(log n) total O(n2 ) O(n2 ) O(n log n) Let’s look at Python code that implements these priority queues. We start with an abstract base class that has the interface of a priority queue, maintains an internal array A of items, and trivially implements insert(x) and delete max() (the latter being incorrect on its own, but useful for subclasses). 1 2 3 class PriorityQueue: def __init__(self): self.A = [] 4 5 6 def insert(self, x): self.A.append(x) 7 8 9 10 11 def delete_max(self): if len(self.A) < 1: raise IndexError(’pop from empty priority queue’) return self.A.pop() # NOT correct on its own! 12 13 14 15 16 17 18 19 20 @classmethod def sort(Queue, A): pq = Queue() for x in A: pq.insert(x) out = [pq.delete_max() for _ in A] out.reverse() return out # make empty priority queue # n x T_insert # n x T_delete_max Shared across all implementations is a method for sorting, given implementations of insert and delete max. Sorting simply makes two loops over the array: one to insert all the elements, and another to populate the output array with successive maxima in reverse order. Recitation 8 2 Array Heaps We showed implementations of selection sort and merge sort previously in recitation. Here are implementations from the perspective of priority queues. If you were to unroll the organization of this code, you would have essentially the same code as we presented before. 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 class PQ_Array(PriorityQueue): # PriorityQueue.insert already correct: appends to end of self.A def delete_max(self): # O(n) n, A, m = len(self.A), self.A, 0 for i in range(1, n): if A[m].key < A[i].key: m = i A[m], A[n] = A[n], A[m] # swap max with end of array return super().delete_max() # pop from end of array class PQ_SortedArray(PriorityQueue): # PriorityQueue.delete_max already correct: pop from end of self.A def insert(self, *args): # O(n) super().insert(*args) # append to end of array i, A = len(self.A) - 1, self.A # restore array ordering while 0 < i and A[i + 1].key < A[i].key: A[i + 1], A[i] = A[i], A[i + 1] i -= 1 We use *args to allow insert to take one argument (as makes sense now) or zero arguments; we will need the latter functionality when making the priority queues in-place. Recitation 8 3 Binary Heaps The next implementation is based on a binary heap, which takes advantage of the logarithmic height of a complete binary tree to improve performance. The bulk of the work done by these functions are encapsulated by max heapify up and max heapify down below. 1 2 3 4 5 class PQ_Heap(PriorityQueue): def insert(self, *args): # O(log n) super().insert(*args) # append to end of array n, A = self.n, self.A max_heapify_up(A, n, n - 1) 6 7 8 9 10 11 def delete_max(self): # O(log n) n, A = self.n, self.A A[0], A[n] = A[n], A[0] max_heapify_down(A, n, 0) return super().delete_max() # pop from end of array Before we define max heapify operations, we need functions to compute parent and child indices given an index representing a node in a tree whose root is the first element of the array. In this implementation, if the computed index lies outside the bounds of the array, we return the input index. Always returning a valid array index instead of throwing an error helps to simplify future code. 1 2 3 def parent(i): p = (i - 1) // 2 return p if 0 < i else i 4 5 6 7 def left(i, n): l = 2 * i + 1 return l if l < n else i 8 9 10 11 def right(i, n): r = 2 * i + 2 return r if r < n else i Recitation 8 4 Here is the meat of the work done by a max heap. Assuming all nodes in A[:n] satisfy the Max-Heap Property except for node A[i] makes it easy for these functions to maintain the Node Max-Heap Property locally. 1 2 3 4 5 1 2 3 4 5 6 def max_heapify_up(A, n, c): p = parent(c) if A[p].key < A[c].key: A[c], A[p] = A[p], A[c] max_heapify_up(A, n, p) # # # # # T(c) O(1) O(1) O(1) T(p) = O(log c) index of parent (or c) compare swap parent = T(c/2) recursive call on parent def max_heapify_down(A, n, p): # T(p) = O(log n - log p) l, r = left(p, n), right(p, n) # O(1) indices of children (or p) c = l if A[r].key < A[l].key else r # O(1) index of largest child if A[p].key < A[c].key: # O(1) compare A[c], A[p] = A[p], A[c] # O(1) swap child max_heapify_down(A, n, c) # T(c) recursive call on child O(n) Build Heap P Recall that repeated insertion using a max heap priority queue takes time ni=0 log i = log n! = O(n log n). We can build a max heap in linear time if the whole array is accessible to you. The idea is to construct the heap in reverse level order, from the leaves to the root, all the while maintaining that all nodes processed so far maintain the Max-Heap Property by running max heapify down at each node. As an optimization, we note that the nodes in the last half of the array are all leaves, so we do not need to run max heapify down on them. 1 2 3 4 def build_max_heap(A): n = len(A) for i in range(n // 2, -1, -1): # O(n) loop backward over array max_heapify_down(A, n, i) # O(log n - log i)) fix max heap To see that this procedure takes O(n) instead of O(n log n) time, we compute an upper √ bound explicitly using summation. In the derivation, we use Stirling’s approximation: n! = Θ( n(n/e)n ).  n    n X n nn T (n) < (log n − log i) = log = O log √ n! n(n/e)n i=0 √ √ = O(log(en / n)) = O(n log e − log n) = O(n) Note that using this linear-time procedure to build a max heap does not affect the asymptotic efficiency of heap sort, because each of n delete max still takes O(log n) time each. But it is practically more efficient procedure to initially insert n items into an empty heap. Recitation 8 5 In-Place Heaps To make heap sort in place1 (as well as restoring the in-place property of selection sort and insertion sort), we can modify the base class PriorityQueue to take an entire array A of elements, and maintain the queue itself in the prefix of the first n elements of A (where n <= len(A)). The insert function is no longer given a value to insert; instead, it inserts the item already stored in A[n], and incorporates it into the now-larger queue. Similarly, delete max does not return a value; it merely deposits its output into A[n] before decreasing its size. This approach only works in the case where all n insert operations come before all n delete max operations, as in priority queue sort. 1 2 3 class PriorityQueue: def __init__(self, A): self.n, self.A = 0, A 4 def insert(self): # absorb element A[n] into the queue if not self.n < len(self.A): raise IndexError(’insert into full priority queue’) self.n += 1 5 6 7 8 9 def delete_max(self): # remove element A[n - 1] from the queue if self.n < 1: raise IndexError(’pop from empty priority queue’) self.n -= 1 # NOT correct on its own! 10 11 12 13 14 @classmethod def sort(Queue, A): pq = Queue(A) # make empty priority queue for i in range(len(A)): # n x T_insert pq.insert() for i in range(len(A)): # n x T_delete_max pq.delete_max() return pq.A 15 16 17 18 19 20 21 22 This new base class works for sorting via any of the subclasses: PQ Array, PQ SortedArray, PQ Heap. The first two sorting algorithms are even closer to the original selection sort and insertion sort, and the final algorithm is what is normally referred to as heap sort. We’ve made a CoffeeScript heap visualizer which you can find here: https://codepen.io/mit6006/pen/KxOpep 1 Recall that an in-place sort only uses O(1) additional space during execution, so only a constant number of array elements can exist outside the array at any given time. Recitation 8 6 Exercises 1. Draw the complete binary tree associated with the sub-array array A[:8]. Turn it into a max heap via linear time bottom-up heap-ification. Run insert twice, and then delete max twice. 1 A = [7, 3, 5, 6, 2, 0, 3, 1, 9, 4] 2. How would you find the minimum element contained in a max heap? Solution: A max heap has no guarantees on the location of its minimum element, except that it may not have any children. Therefore, one must search over all n/2 leaves of the binary tree which takes Ω(n) time. 3. How long would it take to convert a max heap to a min heap? Solution: Run a modified build max heap on the original heap, enforcing a Min-Heap Property instead of a Max-Heap Property. This takes linear time. The fact that the original heap was a max heap does not improve the running time. Recitation 8 7 4. Proximate Sorting: An array of distinct integers is k-proximate if every integer of the array is at most k places away from its place in the array after being sorted, i.e., if the ith integer of the unsorted input array is the jth largest integer contained in the array, then |i − j| ≤ k. In this problem, we will show how to sort a k-proximate array faster than Θ(n log n). (a) Prove that insertion sort (as presented in this class, without any changes) will sort a k-proximate array in O(nk) time. Solution: To prove O(nk), we show that each of the n insertion sort rounds swap an item left by at most O(k). In the original ordering, entries that are ≥ 2k slots apart must already be ordered correctly: indeed, if A[s] > A[t] but t − s ≥ 2k, there is no way to reverse the order of these two items while moving each at most k slots. This means that for each entry A[i] in the original order, fewer than 2k of the items A[0], . . . , A[i − 1] are greater than A[i]. Thus, on round i of insertion sort when A[i] is swapped into place, fewer than 2k swaps are required, so round i requires O(k) time. It’s possible to prove a stronger bound: that ai = A[i] is swapped at most k times in round i (instead of 2k). This is a bit subtle: the final sorted index of ai is at most k slots away from i by the k-proximate assumption, but ai might not move to its final position immediately, but may move past its final sorted position and then be bumped to the right in future rounds. Suppose for contradiction a loop swaps the pth largest item A[i] to the left by more than k to position p0 < i − k, past at least k items larger than A[i]. Since A is k-proximate, i − p ≤ k, i.e. i − k ≤ p, so p0 < p. Thus at least one item less than A[i] must exist to the right of A[i]. Let A[j] be the smallest such item, the qth largest item in sorted order. A[j] is smaller than k + 1 items to the left of A[j], and no item to the right of A[j] is smaller than A[j], so q ≤ j − (k + 1), i.e. j − q ≥ k + 1. But A is k-proximate, so j − q ≤ k, a contradiction. (b) Θ(nk) is asymptotically faster than Θ(n2 ) when k = o(n), but is not asymptotically faster than Θ(n log n) when k = ω(log n). Describe an algorithm to sort a k-proximate array in O(n log k) time, which can be faster (but no slower) than Θ(n log n). Solution: We perform a variant of heap sort, where the heap only stores k + 1 items at a time. Build a min-heap H out of A[0], . . . , A[k − 1]. Then, repeatedly, insert the next item from A into H, and then store H.delete min() as the next entry in sorted order. So we first call H.insert(A[k]) followed by B[0] = H.delete min(); the next iteration calls H.insert(A[k+1]) and B[1] = H.delete min(); and so on. (When there are no more entries to insert into H, do only the delete min step.) B is the sorted answer. This algorithm works because the ith smallest entry in array A must be one of A[0], A[1], . . . , A[i + k] by the k-proximate assumption, and by the time we’re about to write B[i], all of these entries have already been inserted into H (and some also deleted). Assuming entries B[0], . . . , B[i − 1] are correct (by induction), this means the ith smallest value is still in H while all smaller values have already been removed, so this ith smallest value is in fact H.delete min(), and B[i] gets filled correctly. Each heap operation takes time O(log k) because there are at most k + 1 items in the heap, so the n insertions and n deletions take O(n log k) total.