Very recently I posted a puzzle on generating a random binary tree.
This time, the puzzle is to generate a uniformly random binary heap.
Specifically, generate a heap implemented as a binary tree of $n$ nodes, where each node takes exactly one of the values in $\{1,2, \dots, n\}$, and satisfies the max-heap property: each node value is larger than the values of its children (number of children could be zero, one or two).
The tree does not have to be full/almost complete (so a linked list of $n$ nodes is a valid heap for our purposes).
The left and right children are distinct, so the heap with 3 at the top, and left child 1, right child 2, is different from the heap with 3 at the top, left child 2 and right child 1.
Assume you have a random number oracle which gives you a random number in the range $\{1,2, \dots, K\}$, with probability $\frac{1}{K}$, $K$ is input and could be as large as you want it to be.
A) Give an algorithm that makes $O(n)$ calls to the random number generator.
B) Give an algorithm that makes $O(1)$ calls.
[Solution]
This time, the puzzle is to generate a uniformly random binary heap.
Specifically, generate a heap implemented as a binary tree of $n$ nodes, where each node takes exactly one of the values in $\{1,2, \dots, n\}$, and satisfies the max-heap property: each node value is larger than the values of its children (number of children could be zero, one or two).
The tree does not have to be full/almost complete (so a linked list of $n$ nodes is a valid heap for our purposes).
The left and right children are distinct, so the heap with 3 at the top, and left child 1, right child 2, is different from the heap with 3 at the top, left child 2 and right child 1.
Assume you have a random number oracle which gives you a random number in the range $\{1,2, \dots, K\}$, with probability $\frac{1}{K}$, $K$ is input and could be as large as you want it to be.
A) Give an algorithm that makes $O(n)$ calls to the random number generator.
B) Give an algorithm that makes $O(1)$ calls.
[Solution]
No comments:
Post a Comment