What's the most efficient way to convert a binomial tree into a sorted array of keys?

Question

Say we are given a single-tree binomial heap, such that the binomial tree is of rank r, and thus holding 2^r keys. What's the most efficient way to convert it into a k<2^r length sorted array, with the k smallest keys of the tree? Let's assume we can't use any other data structure but Lazy Binomial Heaps, and Binomial Trees. Notice that at each level the children are unnecessarily linked by order, so you might have to make some comparisons at some point.

My solution was (assuming 1<=k<=2^r):

1. Create a new empty lazy binomial heap H.
2. Insert the root's key into the heap.
3. Create a new counter x, and set x=1.
4. For each level i=0,1,... (where the root is at level 0):
   • Let c be the number of nodes at level i.
   • Set x=x+c.
   • Iterate over the nodes in level i and:
     • Insert each node N to H. (In O(1))
     • If x < k, recursively make the same process for each node N, passing through x so the counting continues.
5. Repeat k times:
   • Extract the minimal key out of the heap and place it in the output array.
   • Delete the minimal key form the heap. (amortized cost: O(1))
6. Return output array.

There might be some holes in the pseudo-code, but I think the idea itself is clear. I also managed to implement it. However, I'm not sure that's the most efficient algorithm for this task.

Answer 1

Thanks to Gene's comment I see that the earlier algorithm I suggested will not always work, as it assumes the maximal node at level x is smaller than the minimal node at level x-1, which is not a reasonable assumption.

Yet, I believe this one makes the job efficiently:

public static int[] kMin(FibonacciHeap H, int k) {
    if (H == null || H.isEmpty() || k <= 0)
        return new int[0];
    HeapNode tree = H.findMin();
    int rank = tree.getRank();
    int size = H.size();
    size = (int) Math.min(size, Math.pow(2, rank));
    if (k > size)
        k = size;
    int[] result = new int[k];
    FibonacciHeap heap = new FibonacciHeap();
    HeapNode next = H.findMin();

    for(int i = 0; i < k; i++) { // k iterations
        if(next != null)
            for (Iterator<HeapNode> iter = next.iterator(); iter.hasNext(); ) { // rank nCr next.getParent().getRank() iterations.
                next = iter.next();
                HeapNode node = heap.insert(next.getKey()); // O(1)
                node.setFreePointer(next);
            }
        next = heap.findMin().getFreePointer();
        result[i] = next.getKey();
        heap.deleteMin(); // O(log n) amortized cost.
        next = next.child;
    }

    return result;
}

"freePointer" is a field in HeapNode, where I can store a pointer to another HeapNode. It is basically the "info field" most heaps have.

let r be the rank of the tree. Every iteration we insert at most r items to the external heap. In addition, every iteration we use Delete-Min to delete one item from the heap. Therefore, the total cost of insertions is O(kr), and the total cost of Delete-Min is O(k*log(k)+k*log(r)). So the total cost of everything becomes O(k(log(k)+r))