Hi Tsung-Hsien,
I’am currently solving the task 11.6 and come on with a recursive solution instead of the max-heap of possible candidates.
The idea is:
1 start from the root
2. collect the biggest child
3. recursively explore the biggest child
4. and on recursion return collect and explore the 2nd child (if it exists and if we have not yet found required k elements)
The question is: is the recursive solution OK? Will it give the same complexity?
Thank you!
Elmira
Java implementation, max-heap is stored in the array where the 0-element is ignored, so the left child = 2* parent, right child = 2*parent+1 :
public static Iterable find(int[] maxHeap, int k) {
if (maxHeap == null || maxHeap.length == 0 || k <= 0) return null;
if (k >= maxHeap.length) return Arrays.asList(maxHeap);
Queue<Integer> queue = new Queue<>();
queue.enqueue(maxHeap[1]);
find(maxHeap, queue, 1, k, maxHeap.length - 1);
return queue;
}
private static void find(int[] maxHeap, Queue queue, int parentIndex, int k, int N) {
if (queue.size() == k) return;
if (parentIndex * 2 > N) return;
int left = parentIndex * 2;
int right = left == N ? -1 : left + 1;
if (right != -1 && maxHeap[right] > maxHeap[left]) {
queue.enqueue(maxHeap[right]);
find(maxHeap, queue, right, k, N);
if (queue.size() < k) {
queue.enqueue(maxHeap[left]);
find(maxHeap, queue, left, k, N);
}
} else {
queue.enqueue(maxHeap[left]);
find(maxHeap, queue, left, k, N);
if (right != -1 && queue.size() < k) {
queue.enqueue(maxHeap[right]);
find(maxHeap, queue, right, k, N);
}
}
}