------------------------------------------------- Today: A little probabality review, and heaps. * Monday lecture: verifying matrix equality, quicksort. * Wednesday lecture: linear-time randomized and deterministic select. * How's PS2 going? * Office Hours changing: T10-12. Check Stellar for updated office hours for everyone. ------------------------------------------------- SOME PROBABILITY BACKGROUND REVIEW Suppose I flip a coin (heads probability = p) until I get heads. How long do I wait in expectation? Pr[get heads on flip one] = p. Pr[get heads on flip two, tails on one] = p * (1-p) Pr[get heads on flip three, tails on one/two] = p * (1-p)^2 Let X := E[waiting time]. X = (probability of heads) + (probability of tails) (1 + E[waiting time | tails]) X = p + (1-p) (1 + X) X = p + 1 + X - p - pX pX = 1 X = 1/p. (see CLRS p. 1112 for an alternate proof.) --------- Here are some dice. What is E[value showing on dice] ? E[value showing on dice] = sum_i i /6 = 21 / 6 = 3.5 What's E[sum value on top and value bottom] ? E[sum value on top and value bottom] = E[value on top] + E[value on bottom] = 3.5 + 3.5 = 7. No matter WHAT the configuration!! --------- ------------------------------------------------- DYNAMIC SETS (or sometimes "dictionaries") A data structure that supports the following operations: SEARCH(D,x) return pointer to x in D if it's there. INSERT(D,x) add element x to D. DELETE(D,p) delete element pointed to by p from D. MIN(D) smallest element in D. MAX(D) largest element in D. SUCC(D,p) next-largest element after element pointed to by p. PRED(D,p) next-smallest element before element pointed to by p. Sometimes called an _abstract data type_ (ADT). Sort of misleading: always assume that we're talking about a _key_ $k$ with associated data $v$. (dictionary = word, definition.) ---------------------- PRIORITY QUEUES Very useful data structure for many applications: _max-priority queue_. You can think of this as a data structure for a dynamic set in which we want to be able to find the most "important" element in the set. Like dictionaries, but with fewer required operations. Formally, we need: INSERT(D,x) insert element x into D. MAX(D) returns the element in D with the largest key. EXTRACT-MAX(D) returns and removes the element in D with the largest key. How could you implement this? * unsorted linked list. INSERT is O(1). MAX,EXTRACT-MAX are O(N). * sorted doubly linked list. INSERT is O(N). MAX, EXTRACT-MAX are O(1). * we're going to give an implementation using _heaps_ today. also simultaneously will give a new sorting algorithm. ------------------------------------------------- HEAPS A _heap_ is a (nearly) complete binary tree that satisfies the following: [_heap property_] key(i) <= key(parent(i)). e.g., 9 7 4 6 5 1 2 3 How do you implement MAX? MAX(D) = return root(D). (Can you prove correctness inductively?) ----- BUILD-MAX-HEAP: want a function to build a max heap from an array. ----- important subroutine: MAX-HEAPIFY // clrs p. 130 given two heaps H_1, H_2, and an element n, make one heap H. idea: be recursive, and shove the problem down in the tree. n this is a heap if n >= max(H_1) and max(H_2). H_1 H_2 suppose n is not the maximum overall. Then, say, max(H_1) > n. n r r H_2 ---> n H_2 H_1 H_1 now the "problem" heap is n H_1. recurse. How long with this take to run? O(log n) -- the height of an (almost) complete binary tree is log N. ----- Now, how do we do BUILD-MAX-HEAP? Any single-node tree is a heap! Given a tree, inductively MAX-HEAPIFY every node (from the bottom up). Each MAX-HEAPIFY takes O(log N) time. There are N nodes ==> BUILD-MAX-HEAP takes O(N log N) time. Actually, we can give a tighter analysis. \sum_{h=1}^{log n} (#nodes at height h) * h <= \sum_{h=1}^{log n} (n/2^h) * h /\ / \ / \ / \ <--- 2^i in ith row / \ / \ ht = log n ==> 2^i in (log n - i)th from bottom / \ /______________\ 2^(log n - i) = n/2^i. = n \sum_{h=1}^{log n} h/2^h <= n \sum h/2^h = n (0.5/(1-0.5)^2) by (A.8 p. 1061) = 2n. So BUILD-MAX-HEAP takes O(n) time! ---- Can implement a heap in an array as follows: store the children of A[i] at array cells A[2i] and A[2i+1]. then: PARENT(i) == floor(i/2). LEFT(i) == 2i. RIGHT(i) == 2i+1. This makes implementation easier and more efficient than using pointers and a "real" tree, but it's a little harder to see what's going on. ----- PRIORITY QUEUES USING HEAPS MAX(D): -- return the root. INSERT(D,x) -- add a new leaf node x at the end of the tree. -- Swap with its parent until the heap property is satisfied. EXTRACT-MAX(D) -- save the root. -- take the last leaf node, and put it at the root. -- HEAPIFY again. (Swap with a child until the heap property is satisfied.) MAX is O(1). INSERT, EXTRACT-MAX are O(log N). --- HEAPSORT: Given an array A of elements to sort: size <- |A|. BUILD-MAX-HEAP(A). While size > 0 swap A[size] and A[1] size-- MAX-HEAPIFY the new root (considering the heap as A[1..size]). ---- What's so great about heapsort? * in place * Theta(n log n) * deterministic