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~^.^
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
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
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!!!
TO RUN FOR FAILURE
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!!!
TO RUN FOR FAILURE