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
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~^.^
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() )
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.
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!!!
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--;
}
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!!!