Презентация CSE 326: Data Structures. Mergeable Heaps. Lecture 22 онлайн

Содержание слайда: CSE 326: Data Structures Lecture #22 Mergeable Heaps Henry Kautz Winter Quarter 2002

Содержание слайда: Summary of Heap ADT Analysis Consider a heap of N nodes Space needed: O(N) Actually, O(MaxSize) where MaxSize is the size of the array Pointer-based implementation: pointers for children and parent Total space = 3N + 1 (3 pointers per node + 1 for size) FindMin: O(1) time; DeleteMin and Insert: O(log N) time BuildHeap from N inputs: What is the run time? N Insert operations = O(N log N) O(N): Treat input array as a heap and fix it using percolate down Thanks, Floyd!

Содержание слайда: Other Heap Operations Find and FindMax: O(N) DecreaseKey(P,,H): Subtract  from current key value at position P and percolate up. Running Time: O(log N) IncreaseKey(P,,H): Add  to current key value at P and percolate down. Running Time: O(log N) E.g. Schedulers in OS often decrease priority of CPU-hogging jobs Delete(P,H): Use DecreaseKey (to 0) followed by DeleteMin. Running Time: O(log N) E.g. Delete a job waiting in queue that has been preemptively terminated by user

Содержание слайда: But What About... Merge(H1,H2): Merge two heaps H1 and H2 of size O(N). E.g. Combine queues from two different sources to run on one CPU. Can do O(N) Insert operations: O(N log N) time Better: Copy H2 at the end of H1 (assuming array implementation) and use Floyd’s Method for BuildHeap. Running Time: O(N) Can we do even better? (i.e. Merge in O(log N) time?)

Содержание слайда: Binomial Queues Binomial queues support all three priority queue operations Merge, Insert and DeleteMin in O(log N) time Idea: Maintain a collection of heap-ordered trees Forest of binomial trees Recursive Definition of Binomial Tree (based on height k): Only one binomial tree for a given height Binomial tree of height 0 = single root node Binomial tree of height k = Bk = Attach Bk-1 to root of another Bk-1

Содержание слайда: Building a Binomial Tree To construct a binomial tree Bk of height k: Take the binomial tree Bk-1 of height k-1 Place another copy of Bk-1 one level below the first Attach the root nodes Binomial tree of height k has exactly 2k nodes (by induction)

Содержание слайда: Building a Binomial Tree To construct a binomial tree Bk of height k: Take the binomial tree Bk-1 of height k-1 Place another copy of Bk-1 one level below the first Attach the root nodes Binomial tree of height k has exactly 2k nodes (by induction)

Содержание слайда: Building a Binomial Tree To construct a binomial tree Bk of height k: Take the binomial tree Bk-1 of height k-1 Place another copy of Bk-1 one level below the first Attach the root nodes Binomial tree of height k has exactly 2k nodes (by induction)

Содержание слайда: Building a Binomial Tree To construct a binomial tree Bk of height k: Take the binomial tree Bk-1 of height k-1 Place another copy of Bk-1 one level below the first Attach the root nodes Binomial tree of height k has exactly 2k nodes (by induction)

Содержание слайда: Building a Binomial Tree To construct a binomial tree Bk of height k: Take the binomial tree Bk-1 of height k-1 Place another copy of Bk-1 one level below the first Attach the root nodes Binomial tree of height k has exactly 2k nodes (by induction)

Содержание слайда: Building a Binomial Tree To construct a binomial tree Bk of height k: Take the binomial tree Bk-1 of height k-1 Place another copy of Bk-1 one level below the first Attach the root nodes Binomial tree of height k has exactly 2k nodes (by induction)

Содержание слайда: Building a Binomial Tree To construct a binomial tree Bk of height k: Take the binomial tree Bk-1 of height k-1 Place another copy of Bk-1 one level below the first Attach the root nodes Binomial tree of height k has exactly 2k nodes (by induction)

Содержание слайда: Why Binomial? Why are these trees called binomial? Hint: how many nodes at depth d?

Содержание слайда: Why Binomial? Why are these trees called binomial? Hint: how many nodes at depth d? Number of nodes at different depths d for Bk = [1], [1 1], [1 2 1], [1 3 3 1], … Binomial coefficients of (a + b)k = k!/((k-d)!d!)

Содержание слайда: Definition of Binomial Queues

Содержание слайда: Binomial Queue Properties Suppose you are given a binomial queue of N nodes There is a unique set of binomial trees for N nodes What is the maximum number of trees that can be in an N-node queue? 1 node  1 tree B0; 2 nodes  1 tree B1; 3 nodes  2 trees B0 and B1; 7 nodes  3 trees B0, B1 and B2 … Trees B0, B1, …, Bk can store up to 20 + 21 + … + 2k = 2k+1 – 1 nodes = N. Maximum is when all trees are used. So, solve for (k+1). Number of trees is  log(N+1) = O(log N)

Содержание слайда: Binomial Queues: Merge Main Idea: Merge two binomial queues by merging individual binomial trees Since Bk+1 is just two Bk’s attached together, merging trees is easy Steps for creating new queue by merging: Start with Bk for smallest k in either queue. If only one Bk, add Bk to new queue and go to next k. Merge two Bk’s to get new Bk+1 by making larger root the child of smaller root. Go to step 2 with k = k + 1.

Содержание слайда: Example: Binomial Queue Merge Merge H1 and H2

Содержание слайда: Example: Binomial Queue Merge Merge H1 and H2

Содержание слайда: Example: Binomial Queue Merge Merge H1 and H2

Содержание слайда: Example: Binomial Queue Merge Merge H1 and H2

Содержание слайда: Example: Binomial Queue Merge Merge H1 and H2

Содержание слайда: Example: Binomial Queue Merge Merge H1 and H2

Содержание слайда: Example: Binomial Queue Merge Merge H1 and H2

Содержание слайда: Example: Binomial Queue Merge Merge H1 and H2

Содержание слайда: Example: Binomial Queue Merge Merge H1 and H2

Содержание слайда: Binomial Queues: Merge and Insert What is the run time for Merge of two O(N) queues? How would you insert a new item into the queue?

Содержание слайда: Binomial Queues: Merge and Insert What is the run time for Merge of two O(N) queues? O(number of trees) = O(log N) How would you insert a new item into the queue? Create a single node queue B0 with new item and merge with existing queue Again, O(log N) time Example: Insert 1, 2, 3, …,7 into an empty binomial queue

Содержание слайда: Insert 1,2,…,7

Содержание слайда: Insert 1,2,…,7

Содержание слайда: Insert 1,2,…,7

Содержание слайда: Insert 1,2,…,7

Содержание слайда: Insert 1,2,…,7

Содержание слайда: Insert 1,2,…,7

Содержание слайда: Insert 1,2,…,7

Содержание слайда: Insert 1,2,…,7

Содержание слайда: Binomial Queues: DeleteMin Steps: Find tree Bk with the smallest root Remove Bk from the queue Delete root of Bk (return this value); You now have a new queue made up of the forest B0, B1, …, Bk-1 Merge this queue with remainder of the original (from step 2) Run time analysis: Step 1 is O(log N), step 2 and 3 are O(1), and step 4 is O(log N). Total time = O(log N) Example: Insert 1, 2, …, 7 into empty queue and DeleteMin

Содержание слайда: Insert 1,2,…,7

Содержание слайда: DeleteMin

Содержание слайда: Merge

Содержание слайда: Merge

Содержание слайда: Merge

Содержание слайда: Merge

Содержание слайда: Implementation of Binomial Queues Need to be able to scan through all trees, and given two binomial queues find trees that are same size Use array of pointers to root nodes, sorted by size Since is only of length log(N), don’t have to worry about cost of copying this array At each node, keep track of the size of the (sub) tree rooted at that node Want to merge by just setting pointers Need pointer-based implementation of heaps DeleteMin requires fast access to all subtrees of root Use First-Child/Next-Sibling representation of trees

Содержание слайда: Other Mergeable Priority Queues: Leftist and Skew Heaps Leftist Heaps: Binary heap-ordered trees with left subtrees always “longer” than right subtrees Main idea: Recursively work on right path for Merge/Insert/DeleteMin Right path is always short  has O(log N) nodes Merge, Insert, DeleteMin all have O(log N) running time (see text) Skew Heaps: Self-adjusting version of leftist heaps (a la splay trees) Do not actually keep track of path lengths Adjust tree by swapping children during each merge O(log N) amortized time per operation for a sequence of M operations We will skip details… just recognize the names as mergeable heaps!

Содержание слайда: Coming Up Some random randomized data structures Treaps Skip Lists FOR MONDAY: Read section on randomized data structures in Weiss. Be prepared, if called on, to explain in your own words why we might want to use a data structure that incorporates randomness!