Question

Given the following list of keys 49, 53, 25, 40, 3, 60, 2, 48, 1, 49, 40.

Show the result of using the linear-time algorithm to build a binary heap (BuildHeap) using the same list of keys. Are these the same, if not explain why.

Answer 1

Explinatation:-

1) in the question they didn’t mention about the max heap are min heap let us consider min heap.

2) that means at any node the value of that node is smaller than its children except leaf nodes since leaf node doesn’t have children.

3)now initially we inserted 49 by default one element is min heap

4)next insert 53 left to 49 so it is satisfying min heap property

5)next insert 25 right to 53 after this it is failing the min heap property so now we needo swap 49 and 25 now it will satisfy the min heap property.

6)next insert 40 next 3 now after inserting 3 it is failing the min heap property and swap with above its parent again go to till root node until it should not fail min heap property.

7)so like that continue for remaining elements.