Binomial and Fibonacci Heap Quiz Online Practice Test

1. What sets a binomial heap apart from a binary heap?

2. How many trees are there in a binomial heap with n nodes?

3. In a binomial heap, is the root value always greater than the left child and less than the right child?

4. Based on the given pseudocode, is the function for merging two heaps correct?

mergeTree(p, q) {
if (p.root.value <= q.root.value)
return p.addTree(q);
else
return q.addTree(p);
}

5. After merging two trees of order k, what is the order of the resulting heap?

6. What is the time complexity for decreasing a node's value in a binomial heap?

7. What does the following pseudocode return?

int myfun(heap_arr[]) {
int mini = INF;
for (int i = 0; i < tot_node; i++)
mini = min(mini, heap_arr[i]);
return mini;
}

8. Which pair of operations have identical time complexities?

9. Is the statement "A Fibonacci heap has better amortized running time compared to a binomial heap" correct?

10. For a heap with n nodes, what is the maximum number of trees that can be present when building the heap?

11. Which pair of operations in a Fibonacci heap have the same time complexity?

12. Identify the issue in the following Fibonacci heap insertion code. Select the correct option.

FIB-INSERT(H, x) {
degree[x] = 0;
p[x] = NIL;
child[x] = NIL;
left[x] = x;
right[x] = x;
mark[x] = FALSE;
concatenate the root list containing x with root list H;
if (min[H] == NIL || key[x] < key[min[H]])
min[H] = x;
n[H] = n[H] + 1;
}

13. What will be the order of the new heap after performing the union of heaps H1 and H2 using the following code, given that both heaps initially have an order of n?

FIB_UNION(H1, H2) {
H = MAKE_HEAP();
min[H] = min[H1];
concatenate the root list of H2 with the root list of H;
if (min[H1] == NIL || (min[H2] != NIL && min[H2] < min[H1]))
min[H] = min[H2];
n[H] = n[H1] + n[H2];
free the objects H1 and H2;
return H;
}