Question

(Data Structure)

Suppose we want to store the data of a binary heap in an array. Show the data of that array after inserting the given keys one by one. Assume that initially binary heap is empty. Show all steps of insertions.

Note: No need to show the changes for each step of “percolate up”. The contents of the array must be shown after completing one insertion.

Create the “Min Heap” for the following data set

7,      3,      18,    -9,     1,      50,    15,    4,      27,    0

Answer 1

Features of Heap data structure:

1) The left child of a node can be accessed by the formula, 2*i+1, "i" is the position of the parent, in the array
2) The right child of a node can be accessed by the formula, 2*i+2, "i" is the position of the parent, in the array
3) Minheap is a data structure where the parent is the smallest when compared to both their children.

To insert a node in binary min heap, put the element at the last position, recursively call for its parent and check if it's the smallest.

Steps of insertion:

1) Increase the heap size by 1.
2) Insert the new element at the end of the heap.
3)Heapify using a bottom up approach.

Following the steps, the heap obtained after constructing a binary min heap will be:

Note that the output produced is the resultant array and the min heap in C++ is represented by priority_queue.