Thread: a priority queue quesiton..

  1. #1
    Compiling
    Join Date
    Jun 2003
    Posts
    69

    a priority queue quesiton..

    This is a question in my textbook, but I do not fully understand it, could anyone give me an explanation about this? Thx a lot!
    ...We can perform BuildHeap in linear time for the leftist heaps by considering each element as one-node leftist heap, placing all these heaps on a queue and performing the following step, until only one heap is on the queue, dequeue two heaps, merge them, and enqueue the result...
    Last edited by NightWalker; 10-07-2003 at 01:07 AM.

  2. #2
    root
    Join Date
    Sep 2003
    Posts
    232
    Damn, that has more techie buzzwords than a hardware vendor's sales pitch. Well, not really, but it sure seems that way. Basically it says that you'll have a queue of heaps. You remove the first two heaps from the queue and merge them, then add the merged heap to the queue. Depending on your implementation, the queue could be an array or a linked list and the heaps could be arrays or linked lists. So you have the following combinations:

    array of arrays
    array of lists
    list of arrays
    list of lists

    Without knowing it's hard to tell you how to do it, but here's some pseudocode that may help:
    Code:
    while (size(heap) > 1) {
      heap1 = dequeue(&heap);
      heap2 = dequeue(&heap);
      merged = merge(heap1, heap2);
      enqueue(&heap, merged);
    }
    The information given in this message is known to work on FreeBSD 4.8 STABLE.
    *The above statement is false if I was too lazy to test it.*
    Please take note that I am not a technical writer, nor do I care to become one.
    If someone finds a mistake, gleaming error or typo, do me a favor...bite me.
    Don't assume that I'm ever entirely serious or entirely joking.

  3. #3
    Compiling
    Join Date
    Jun 2003
    Posts
    69

    Lightbulb

    Haha, Thank u..

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help with FIFO QUEUE
    By jackfraust in forum C++ Programming
    Replies: 23
    Last Post: 04-03-2009, 08:17 AM
  2. Fixing my program
    By Mcwaffle in forum C Programming
    Replies: 5
    Last Post: 11-05-2008, 03:55 AM
  3. Priority Queue Help
    By cjwenigma in forum C++ Programming
    Replies: 6
    Last Post: 11-15-2007, 12:48 AM
  4. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 09:09 PM
  5. help with queues
    By Unregistered in forum C Programming
    Replies: 3
    Last Post: 05-21-2002, 11:39 AM