min heap
Computer Science
Answer the following questions with your words, not writing code.
Suppose we use a binary min heap to store data. What is the structure of the heap in the following five configurations C1, . . . , C4?
-
Starting from an empty heap, insert 1, 8, 3, 4, 2, 11, 6, 9, 12, 5, 10, 7 sequentially, the resulting configuration is C1.
-
Starting from C1, perform Extract-MIN, the resulting configuration is C2.
-
Starting from C2, perform Decrease(x, 1), where x is a pointer pointing to the data with key 11,
the resulting configuration is C3.
-
Starting from C3, perform Delete(y), where y is a pointer pointing to the data with key 6, the
resulting configuration is C4.
Repeat the above question on binomial heap and Fibonacci heap. (You need to describe the structure of the trees, the key on each node, and the MIN pointer / marked nodes for Fibonacci heaps. Some explanations are needed, but you do not need to describe the pointers and number of children on nodes.)
Trending now
This is a popular solution!
Step by step
Solved in 4 steps with 4 images
