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~^.^

Printable View

- 09-11-2002KamAnyone 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~^.^ - 09-11-2002Dr. 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-2002Nick
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-2002Kam
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!!! - 09-12-2002Nick
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-2002Kam
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!!!