Generate a random heap.

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]