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

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №1 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №2 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №3 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №4 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №5 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №6 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №7 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №8 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №9 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №10 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №11 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №12 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №13 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №14 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №15 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №16 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №17 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №18 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №19 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №20 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №21 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №22 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №23 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №24 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №25 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №26 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №27 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №28 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №29 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №30 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №31 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №32 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №33 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №34 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №35 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №36 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №37 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №38 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №39 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №40 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №41 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №42 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №43 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №44 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №45 CSE 326: Data Structures. Mergeable Heaps. Lecture #22, слайд №46
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему CSE 326: Data Structures. Mergeable Heaps. Lecture #22. Доклад-сообщение содержит 46 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


CSE 326: Data Structures Lecture #22 Mergeable Heaps Henry Kautz Winter Quarter 2002
Описание слайда:
CSE 326: Data Structures Lecture #22 Mergeable Heaps Henry Kautz Winter Quarter 2002

Слайд 2


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...
Описание слайда:
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!

Слайд 3


Other Heap Operations Find and FindMax: O(N) DecreaseKey(P,,H): Subtract  from current key value at position P and percolate up. Running Time:...
Описание слайда:
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

Слайд 4


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)...
Описание слайда:
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?)

Слайд 5


Binomial Queues Binomial queues support all three priority queue operations Merge, Insert and DeleteMin in O(log N) time Idea: Maintain a collection...
Описание слайда:
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

Слайд 6


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...
Описание слайда:
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)

Слайд 7


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...
Описание слайда:
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)

Слайд 8


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...
Описание слайда:
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)

Слайд 9


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...
Описание слайда:
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)

Слайд 10


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...
Описание слайда:
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)

Слайд 11


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...
Описание слайда:
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)

Слайд 12


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...
Описание слайда:
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)

Слайд 13


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?

Слайд 14


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...
Описание слайда:
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!)

Слайд 15


Definition of Binomial Queues
Описание слайда:
Definition of Binomial Queues

Слайд 16


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...
Описание слайда:
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)

Слайд 17


Binomial Queues: Merge Main Idea: Merge two binomial queues by merging individual binomial trees Since Bk+1 is just two Bk’s attached together,...
Описание слайда:
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.

Слайд 18


Example: Binomial Queue Merge Merge H1 and H2
Описание слайда:
Example: Binomial Queue Merge Merge H1 and H2

Слайд 19


Example: Binomial Queue Merge Merge H1 and H2
Описание слайда:
Example: Binomial Queue Merge Merge H1 and H2

Слайд 20


Example: Binomial Queue Merge Merge H1 and H2
Описание слайда:
Example: Binomial Queue Merge Merge H1 and H2

Слайд 21


Example: Binomial Queue Merge Merge H1 and H2
Описание слайда:
Example: Binomial Queue Merge Merge H1 and H2

Слайд 22


Example: Binomial Queue Merge Merge H1 and H2
Описание слайда:
Example: Binomial Queue Merge Merge H1 and H2

Слайд 23


Example: Binomial Queue Merge Merge H1 and H2
Описание слайда:
Example: Binomial Queue Merge Merge H1 and H2

Слайд 24


Example: Binomial Queue Merge Merge H1 and H2
Описание слайда:
Example: Binomial Queue Merge Merge H1 and H2

Слайд 25


Example: Binomial Queue Merge Merge H1 and H2
Описание слайда:
Example: Binomial Queue Merge Merge H1 and H2

Слайд 26


Example: Binomial Queue Merge Merge H1 and H2
Описание слайда:
Example: Binomial Queue Merge Merge H1 and H2

Слайд 27


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? How would you insert a new item into the queue?

Слайд 28


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...
Описание слайда:
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

Слайд 29


Insert 1,2,…,7
Описание слайда:
Insert 1,2,…,7

Слайд 30


Insert 1,2,…,7
Описание слайда:
Insert 1,2,…,7

Слайд 31


Insert 1,2,…,7
Описание слайда:
Insert 1,2,…,7

Слайд 32


Insert 1,2,…,7
Описание слайда:
Insert 1,2,…,7

Слайд 33


Insert 1,2,…,7
Описание слайда:
Insert 1,2,…,7

Слайд 34


Insert 1,2,…,7
Описание слайда:
Insert 1,2,…,7

Слайд 35


Insert 1,2,…,7
Описание слайда:
Insert 1,2,…,7

Слайд 36


Insert 1,2,…,7
Описание слайда:
Insert 1,2,…,7

Слайд 37


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...
Описание слайда:
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

Слайд 38


Insert 1,2,…,7
Описание слайда:
Insert 1,2,…,7

Слайд 39


DeleteMin
Описание слайда:
DeleteMin

Слайд 40


Merge
Описание слайда:
Merge

Слайд 41


Merge
Описание слайда:
Merge

Слайд 42


Merge
Описание слайда:
Merge

Слайд 43


Merge
Описание слайда:
Merge

Слайд 44


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...
Описание слайда:
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

Слайд 45


Other Mergeable Priority Queues: Leftist and Skew Heaps Leftist Heaps: Binary heap-ordered trees with left subtrees always “longer” than right...
Описание слайда:
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!

Слайд 46


Coming Up Some random randomized data structures Treaps Skip Lists FOR MONDAY: Read section on randomized data structures in Weiss. Be prepared, if...
Описание слайда:
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!

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию