Thread: Has anyone ever heard about the WEAK HEAP?

  1. #1
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74

    Unhappy Has anyone ever heard about the WEAK HEAP?

    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.

  2. #2
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    This is the only website about weak heap I can access. Chinese government doesn't let me visit most foreign websites.
    Array Sorting 2

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    18
    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.

  4. #4
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    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...

  5. #5
    Registered User
    Join Date
    Mar 2010
    Posts
    18
    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.)

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    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
    Last edited by iMalc; 03-19-2010 at 01:56 PM.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Mar 2010
    Location
    China
    Posts
    74
    Thank you, Malc. That's what I'm look for. But I think I will have too spend several days to understand this passage...

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. heap
    By George2 in forum Windows Programming
    Replies: 2
    Last Post: 11-10-2007, 11:49 PM
  2. Suggestions on this C style code
    By Joelito in forum C Programming
    Replies: 11
    Last Post: 06-07-2007, 03:22 AM
  3. Heap Work
    By AndyBomstad in forum C++ Programming
    Replies: 1
    Last Post: 05-16-2005, 12:09 PM
  4. Do you know...
    By davejigsaw in forum C++ Programming
    Replies: 1
    Last Post: 05-10-2005, 10:33 AM
  5. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM