August 14, 2009 9:00 AM
We previously implemented priority queues using leftist heaps. In this exercise we will implement the same library using a different data structure known as a pairing heap. Pairing heaps are an unusual data structure; they are simple to implement, and performance is good, but their time complexity is not proved, only conjectured, and the analysis has defied many good algorithmists. Our presentation is based on Chris Okasaki’s book Purely Functional Data Structures.
Pairing heaps are heap-ordered multi-way trees, with each node of each tree less than its children. A pairing heap is either empty or is a node consisting of an item and a list of pairing heaps, none of which may be empty. The find-first function simply returns the item at the root of the tree of nodes. Merge takes two trees and makes the tree with the larger root the leftmost child of the tree with the smaller root. Insert builds a singleton node, then calls merge.
The fundamental operation on pairing heaps is the delete-first operation, which discards the root of the tree and merges its children in two passes. The first pass runs from left to right, merging child nodes pair-wise, the first child with the second, the third child with the fourth, and so on. The second pass merges the resulting trees, again pair-wise, from right to left.
Your task is to implement priority queues using pairing heaps, using the same interface as the prior exercise. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.
Posted by programmingpraxis
Categories: Exercises
Tags:
Mobile Site | Full Site
Get a free blog at WordPress.com Theme: WordPress Mobile Edition by Alex King.
[…] Remco Niemeijer Righty, I’m back from vacation so let’s get right back to business. In today’s Programming Praxis problem we have another data structure to implement. Let’s get […]
By Programming Praxis – Pairing Heaps « Bonsai Code on August 14, 2009 at 11:22 AM
My Haskell solution (see http://bonsaicode.wordpress.com/2009/08/14/programming-praxis-pairing-heaps/ for a version with comments):
data PairingHeap a = Empty | Node a [PairingHeap a] findFirst :: PairingHeap a -> Maybe a findFirst Empty = Nothing findFirst (Node n _) = Just n merge :: Ord a => PairingHeap a -> PairingHeap a -> PairingHeap a merge Empty p = p merge p Empty = p merge m@(Node x ps) n@(Node y qs) | y < x = Node y (m:qs) | otherwise = Node x (n:ps) insert :: Ord a => a -> PairingHeap a -> PairingHeap a insert x = merge (Node x []) deleteFirst :: Ord a => PairingHeap a -> PairingHeap a deleteFirst Empty = Empty deleteFirst (Node _ ps) = foldr merge Empty $ pair ps where pair (a:b:xs) = merge a b : pair xs pair xs = xs fromList :: Ord a => [a] -> PairingHeap a fromList = foldr insert Empty toList :: Ord a => PairingHeap a -> [a] toList Empty = [] toList n@(Node x _) = x : toList (deleteFirst n) pqSort :: Ord a => [a] -> [a] pqSort = toList . fromList main :: IO () main = print $ pqSort [3, 7, 8, 1, 2, 9, 6, 4, 5]By Remco Niemeijer on August 14, 2009 at 11:22 AM
How’s this for a Programming Praxis: Fix your damn website so it does not break in Opera when you get 1/3 of the way down the front page.
By DS on August 14, 2009 at 7:09 PM
[…] […]
By Posts about Programming from google blogs as of August 14, 2009 « tryfly.com on August 15, 2009 at 12:10 AM
my implementation in C
#include <stdlib.h> typedef struct PairingHeapNode { int key; struct PairingHeapNode* child; struct PairingHeapNode* sibling; struct PairingHeapNode* prev; }PairHeap; static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q); static PairHeap* combine_siblings(PairHeap *p); PairHeap* PairHeap_insert(PairHeap *p, int key) { PairHeap *node; node = (PairHeap*)malloc(sizeof(*node)); if(node == NULL) return NULL; node->key = key; node->child = node->sibling = node->prev = NULL; if(p == NULL) return node; else return merge_subheaps(p, node); } PairHeap* PairHeap_DecreaseKey(PairHeap *p, PairHeap *pos, int d) { if(d < 0) return p; pos->key = pos->key - d; if(p == pos) return p; if(pos->sibling != NULL) pos->sibling->prev = pos->prev; if(pos->prev->child = pos) pos->prev->child = pos->sibling; else pos->prev->sibling = p->sibling; p->sibling = NULL; return merge_subheaps(p, pos); } PairHeap* PairHeap_DeleteMin(int *key, PairHeap *p) { PairHeap *new_root; if(p == NULL) return NULL; else { *key = p->key; if(p->child != NULL) new_root = combine_siblings(p->child); free(p); } return new_root; } static PairHeap* combine_siblings(PairHeap *p) { PairHeap *tree_array[1024]; int i, count; if(p->sibling == NULL) return p; for(count = 0; p != NULL; count++) { tree_array[count] = p; p->prev->sibling = NULL; p = p->sibling; } tree_array[count] = NULL; for(i = 1; i < count; i++) tree_array[i] = merge_subheaps(tree_array[i-1], tree_array[i]); return tree_array[count-1]; } static PairHeap* merge_subheaps(PairHeap *p, PairHeap *q) { if(q == NULL) return p; else if(p->key <= q->key) { q->prev = p; p->sibling = q->sibling; if(p->sibling != NULL) p->sibling->prev = p; q->sibling = p->child; if(q->sibling != NULL) q->sibling->prev = q; p->child = q; return p; } else { q->prev = p->prev; p->prev = q; p->sibling = q->child; if(p->sibling != NULL) p->sibling->prev = p; q->child = p; return q; } }By Vikas Tandi on May 5, 2011 at 9:55 AM
[…] a program to implement the algorithm described above, using the Scheme programming language. First, here is a library implementation of priority queues using the pairing heap […]
By Generating integers in ascending order using a set of prime numbers | PHP Developer Resource on May 23, 2012 at 1:56 PM
thank you!
By seungjoo kim on November 24, 2017 at 6:12 AM
[…] a program to implement the algorithm described above, using the Scheme programming language. First, here is a library implementation of priority queues using the pairing heap […]
By [SOLVED] Generating integers in ascending order using a set of prime numbers – BugsFixing on April 22, 2022 at 8:19 AM