Question

Binary Heap

a. Show the result of using the linear-time algorithm to build a binary heap (Min Heap) using the inputs 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2 (Show step by step work)
b. Consider the Binary Heap from 4(a). Show the result of performing three deleteMin operations in the heap of the previous exercise.

Answer 1

a. Building a Min Heap using the given inputs:

Step 1: Insert 10 (Heap: [10])

Step 2: Insert 12 (Heap: [10, 12])

Step 3: Insert 1 (Heap: [1, 12, 10])

Step 4: Insert 14 (Heap: [1, 12, 10, 14])

Step 5: Insert 6 (Heap: [1, 6, 10, 14, 12])

Step 6: Insert 5 (Heap: [1, 5, 10, 14, 12, 6])

Step 7: Insert 8 (Heap: [1, 5, 8, 14, 12, 6, 10])

Step 8: Insert 15 (Heap: [1, 5, 8, 14, 12, 6, 10, 15])

Step 9: Insert 3 (Heap: [1, 3, 8, 5, 12, 6, 10, 15, 14])

Step 10: Insert 9 (Heap: [1, 3, 8, 5, 9, 6, 10, 15, 14, 12])

Step 11: Insert 7 (Heap: [1, 3, 7, 5, 9, 6, 8, 15, 14, 12, 10])

Step 12: Insert 4 (Heap: [1, 3, 4, 5, 9, 6, 7, 15, 14, 12, 10, 8])

Step 13: Insert 11 (Heap: [1, 3, 4, 5, 9, 6, 7, 15, 14, 12, 10, 8, 11])

Step 14: Insert 13 (Heap: [1, 3, 4, 5, 9, 6, 7, 15, 14, 12, 10, 8, 11, 13])

Step 15: Insert 2 (Heap: [1, 2, 4, 5, 3, 6, 7, 15, 14, 9, 10, 8, 11, 13, 12])

b. Performing three deleteMin operations:

DeleteMin 1: Remove 1 (Heap: [2, 3, 4, 5, 8, 6, 7, 15, 14, 9, 10, 11, 13, 12])

DeleteMin 2: Remove 2 (Heap: [3, 5, 4, 9, 8, 6, 7, 15, 14, 12, 10, 11, 13])

DeleteMin 3: Remove 3 (Heap: [4, 5, 6, 9, 8, 13, 7, 15, 14, 12, 10, 11])

The Complete Question

Consider the following series of integers: 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, and 2. Apply the linear-time algorithm to build a Min Heap step-by-step using these inputs. Show the sequence of steps taken to construct the Min Heap.

After constructing the Min Heap, perform three deleteMin operations on the heap obtained from the previous exercise. Display the sequence of steps involved and the resulting Min Heap after each deletion.