"Introduction to Algorithms, the 'bible' of the field, is a comprehensive textbook covering the full spectrum of modern algorithms: from the fastest algorithms and data structures to polynomial-time algorithms for seemingly intractable problems, from classical algorithms in graph theory to special algorithms for string matching, computational geometry, and number theory. The revised third edition notably adds a chapter on van Emde Boas trees, one of the most useful data structures, and on multithreaded algorithms, a topic of increasing importance."--Daniel Spielman, Department of Computer Science, Yale University

(Daniel Spielman )

(b) 3 2 i 4 2 1 7 1 4 3 i 7 (c) (d) 1 i 2 4 3 A 7 1 2 3 4 7 (e) Analysis • • • • B UILD -M AX -H EAP: O(n) for loop: n − 1 times exchange elements: O(1) M AX -H EAPIFY: O(lg n) Total time: O(n lg n). Though heapsort is a great algorithm, a well-implemented quicksort usually beats it in practice. Heap implementation of priority queue Heaps efÞciently implement priority queues. These notes will deal with maxpriority queues implemented with max-heaps. Min-priority queues are

for a complete tree. Proof By induction on h. Basis: Show that it’s true for h = 0 (i.e., that # of leaves ≤ n/2h+1 = n/2 ). In fact, we’ll show that the # of leaves = n/2 . The tree leaves (nodes at height 0) are at depths H and H − 1. They consist of • • all nodes at depth H , and the nodes at depth H − 1 that are not parents of depth-H nodes. Let x be the number of nodes at depth H —that is, the number of nodes in the bottom (possibly incomplete) level. Note that n − x is odd, because the n

mergesort. If they are unbalanced, then quicksort can run as slowly as insertion sort. Worst case • • • • • Occurs when the subarrays are completely unbalanced. Have 0 elements in one subarray and n − 1 elements in the other subarray. Get the recurrence T (n) = T (n − 1) + T (0) + (n) = T (n − 1) + (n) = (n 2) . Same running time as insertion sort. In fact, the worst-case running time occurs when quicksort takes a sorted array as input, but insertion sort runs in O(n) time in this case. Best

height h has black-height ≥ h/2. Proof By property 4, ≤ h/2 nodes on the path from the node to a leaf are red. (claim) Hence ≥ h/2 are black. Claim The subtree rooted at any node x contains ≥ 2bh(x) − 1 internal nodes. Lecture Notes for Chapter 13: Red-Black Trees 13-3 Proof By induction on height of x. Basis: Height of x = 0 ⇒ x is a leaf ⇒ bh(x) = 0. The subtree rooted at x has 0 internal nodes. 20 − 1 = 0. Inductive step: Let the height of x be h and bh(x) = b. Any child of x has height h

Notes for Chapter 13: Red-Black Trees 13-5 7 4 11 x 9 18 y 14 LEFT-ROTATE(T, x) 19 17 22 7 4 18 y x 11 9 19 14 22 17 • • • Before rotation: keys of x’s left subtree ≤ 11 ≤ keys of y’s left subtree ≤ 18 ≤ keys of y’s right subtree. Rotation makes y’s left subtree into x’s right subtree. After rotation: keys of x’s left subtree ≤ 11 ≤ keys of x’s right subtree ≤ 18 ≤ keys of y’s right subtree. Time: O(1) for both L EFT-ROTATE and R IGHT-ROTATE, since a constant number of pointers are