The puzzle was here.
Solution
I will be brief.
For O(n) random number calls, the idea is to grow the heap top down.
n has to be the topmost element. Now n-1 could be any of its two children. Pick a spot for that, randomly.
Now there are 3 new spots available for n-2. Pick one of those three randomly.
This leads to 4 new spots for n-3 and so on.
At the end, you have a random heap.
For an O(1) random number calls algorithm, try proving that there are exactly n! (i.e. factorial of n) heaps, and provide a way to encode/decode a heap given a random number from 1 to n!.
Solution
I will be brief.
For O(n) random number calls, the idea is to grow the heap top down.
n has to be the topmost element. Now n-1 could be any of its two children. Pick a spot for that, randomly.
Now there are 3 new spots available for n-2. Pick one of those three randomly.
This leads to 4 new spots for n-3 and so on.
At the end, you have a random heap.
For an O(1) random number calls algorithm, try proving that there are exactly n! (i.e. factorial of n) heaps, and provide a way to encode/decode a heap given a random number from 1 to n!.
No comments:
Post a Comment