Lesson plan
Pairing heap
A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations (assuming a min-heap): * find-min: simply return the top element of the heap. * meld: compare the two root elements, the smaller remains the root of the result, the larger element and its subtree is appended as a child of this root. * insert: create a new heap for the inserted element and meld into the original heap. * decrease-key (optional): remove the subtree rooted at the key to be decreased, replace the key with a smaller key, then meld the result back into the heap. * delete-min: remove the root and do repeated melds of its subtrees until one tree remains. Various merging strategies are employed. The analysis of pairing heaps' time complexity was initially inspired by that of splay trees. The amortized time per delete-min is , and the operations find-min, meld, and insert run in time.…
Article summary
A pairing heap is a type of heap data structure with relatively simple implementation and excellent practical amortized performance, introduced by Michael Fredman, Robert Sedgewick, Daniel Sleator, and Robert Tarjan in 1986. Pairing heaps are heap-ordered multiway tree structures, and can be considered simplified Fibonacci heaps. They are considered a "robust choice" for implementing such algorithms as Prim's MST algorithm, and support the following operations (assuming a min-heap): * find-min: simply return the top element of the heap. * meld: compare the two root elements, the smaller remains the root of the result, the larger element and its subtree is appended as a child of this root. * insert: create a new heap for the inserted element and meld into the original heap. * decrease-key (optional): remove the subtree rooted at the key to be decreased, replace the key with a smaller key, then meld the result back into the heap. * delete-min: remove the root and do repeated melds of its subtrees until one tree remains. Various merging strategies are employed. The analysis of pairing heaps' time complexity was initially inspired by that of splay trees. The amortized time per delete-min is , and the operations find-min, meld, and insert run in time.…
Key claims
No claims recorded.
Discussion questions
- Summarise the article in your own words. Which single claim would you verify first, and why?
- Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
- If two sources disagreed about one of these facts, what would you need in order to trust one over the other?
Bibliography
No sources recorded.
Key claims and bibliography are generated from the same tracked claims and sources as the article page.