# Anyone Know HEAP ?

• 09-11-2002
Kam
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?
Thanx alot~^.^
• 09-11-2002
Dr. Bebop
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() )```
• 09-11-2002
Nick
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.
• 09-12-2002
Kam
Thanx Dr.Bebop, and Nick
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!!!
• 09-12-2002
Nick
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--; }```
• 09-14-2002
Kam
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!!!