프로그래밍/자료구조
Bionomial heap
shnec
2016. 12. 18. 00:05
https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%ED%9E%99
-- merge : merge two binomial trees of the same order
l To mearge two binomial heaps is analogous to the binary addition of
the sizes of the two heaps
l Insert
1. Create a new heap containing only this element
2. Merge the new heap with the original heap
l Find –min
- Use a pointer : O(1)
l Delete – min
1. Find the root containing min
2. Remove the root from its binomial tree, and obtain a list of its subtrees
3. Transform this list of subtrees into a separate binomial heap
4. Merge the new heap with the original heap except the removed binomial tree
l Decrese –key
The same as the binary heap
