Anyone Know HEAP ?

This is a discussion on Anyone Know HEAP ? within the C Programming forums, part of the General Programming Boards category; I am suffuring on priority queue about HEAP. Now i am trying to build up a heap from an array ...

  1. #1
    Kam
    Kam is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    24

    Question Anyone Know HEAP ?

    I am suffuring on priority queue about HEAP.
    Now i am trying to build up a heap from an array with 100 numbers....
    Is there anyone know how to do it with loop or recursion?
    Please teach me....
    Thanx alot~^.^
    TO RUN FOR FAILURE

  2. #2
    Registered User Dr. Bebop's Avatar
    Join Date
    Sep 2002
    Posts
    96
    Search for the number with the highest priority and then insert it into a binary tree. When you're done you have a heap. Since you only have 100 items there's no problem about speed. Here's some pseudocode.
    Code:
    def search():
            highest = priority[0]
            for next in priority:
                    if next > highest: highest = next
            priority.remove( highest )
            return highest
    
    def buildtree():
            while not priority: # If priority is not empty
                    addtree( search() )
    Processing error: Stupidity detected.
    ------------------------------
    Dr. Bebop
    Windows XP Professional Ed.
    Microsoft Visual Studio 6

  3. #3
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    It's possible to do this faster. By inserting n numbers into
    a binary heap is O(n lg n) but it's possible to
    create a binary heap from an array of n elements in O(n).
    I recommend you look up the algorithm using google.
    Basically you find the bottom internal node. Then you you
    percolate it downward. You keep doing this for each node upwards from right to left until the root.

  4. #4
    Kam
    Kam is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    24
    Thanx Dr.Bebop, and Nick
    According to your reply~
    i am sure Nick you know what definately what i want...
    I am trying to do what you just trying to explain. But i cannot manage it.....@.@
    I am trying to use for loop...with percolateDown function..but still, i failed.
    I know it just i am too suck!
    So can you or anyone tell me the algorithm with code? THANX ALOT!!!
    TO RUN FOR FAILURE

  5. #5
    Blank
    Join Date
    Aug 2001
    Posts
    1,034
    All you do is find the the index of the bottom internal
    node. I think it's something like n/2 where n
    the size of the heap. Then keep percolating down
    Code:
    k = n/2.
    while(k >= 0)
    {
         percolate_down(k);
         k--;
    }

  6. #6
    Kam
    Kam is offline
    Registered User
    Join Date
    Sep 2002
    Posts
    24
    Yes~
    Something like that~
    i solve the problem man!
    Thanx lot, you two guys!
    I will give more feedback on this forum@.@
    Nice to learn from here!!!
    TO RUN FOR FAILURE

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. Heap Work
    By AndyBomstad in forum C++ Programming
    Replies: 1
    Last Post: 05-16-2005, 01:09 PM
  3. Do you know...
    By davejigsaw in forum C++ Programming
    Replies: 1
    Last Post: 05-10-2005, 11:33 AM
  4. heap question
    By mackol in forum C Programming
    Replies: 1
    Last Post: 11-30-2002, 05:03 AM
  5. stach and heap.
    By Unregistered in forum C Programming
    Replies: 1
    Last Post: 01-26-2002, 09:37 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21