Printable View
I've learnd that a weak heap is more efficient and elegant than a normal heap. But I don't know how to implement this data structure and use it for sorting an array. Could anyone give me some detail information about weak heap for me?
Sorry for my poor English. I hope you have no problem understanding my word.
This is the only website about weak heap I can access. Chinese government doesn't let me visit most foreign websites.
Array Sorting 2
In a (Min) "weak" (or "relaxed") heap, only the right child of each node is guaranteed to have a greater key than the parent node, and the root has no left child (thus, the root is the max element). As in normal heaps, the "heap form" has to be satisfied (i.e., all external nodes have a height difference of at most 1).
If you have access to the ACM Digital Library: Relaxed heaps: an alternative to Fibonacci heaps with applications to parallel computation
If you have access to Springer books: "Algorithms and Combinatorics" by Korte & Vygen has a nice, clean mathematical description of Fibonacci Heaps, which might also be of interest to you.
Thank you for your reply.
I have no ACM account and Springer is too expensive for me.
I know what a weak heap is. But I don't know how to use this data structure for sorting. Is it similar to a normal heap sort?
It seems that few Chinese know this data structure...
I thought you might have access via a university/library.
Anyways, how would sorting with a relaxed heap be different from sorting with another type of heap? You get your min element and remove it until you are done, requiring n get/pop min operations, where O(1)/O(log n) suffices for each, plus heap construction, possible in O(n log n), therefore an overall O(n log n) suffices. (And indeed Ω(n log n) is required for sorting on the Real RAM, so you have implemented Yet Another Optimal Sorting Algorithm). Anything fancy like in-place implementation is left as an exercise to the reader (seriously, why else would one implement a sorting algorithm but for the exercise? You *do* have access to the STL, I hope. Though I'm really sorry for the restriction of access to research papers. They did it in my country too, until 20 years ago. Not a very smart idea.)
Hi, that was my site you found above :)
There must be other implementations out there because I certainly based my implementation off another.
Well here's one similar implementation, though I don't think it's he actual one I based mine off: Algorithm engineering: 4th ... - Google Books
Thank you, Malc. That's what I'm look for. But I think I will have too spend several days to understand this passage...