Question

Design document for a MinHeap

Create a design document and run a manual paper and pencil approach to the implementation, insert and deletion of a MinHeap.

Use the input values:

50, 30, 45, 15, 65, 25, 10, 25, 15, 5

Part-1

1. Show insert of each item to the Heap implemented as array and show all the state of the array on the process of each insertion.

2. Show the first index and the last index of the heap in your array.

3. Show the formed array that is your Heap.

4. Draw a binary tree representation of your Heap from the array.

Part-2

1. Delete element, one at a time, from the Heap formed above by swapping the root with the last element in the array.

2. Show deletion of each item from the Heap from the array and show all the state of the array on the process of each deletion.

3. Show clearly the first index and the last index of your Heap after each deletion.

4. Show the final array, verify it is sorted.

Answer 1

A Heap is a special Tree-based data structure in which the tree is a complete binary tree. Generally, Heaps can be of two types:

1. Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
2. Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

Process of Insertion: Elements can be inserted to the heap following a similar approach as discussed above for deletion. The idea is to:

• First increase the heap size by 1, so that it can store the new element.
• Insert the new element at the end of the Heap.
• This newly inserted element may distort the properties of Heap for its parents. So, in order to keep the properties of Heap, heapify this newly inserted element following a bottom-up approach.

Heapify:

• If inserted element is smaller than its parent node in case of Min-Heap OR greater than its parent node in case of Max-Heap, swap the element with its parent.
• Keep repeating the above step, if node reaches its correct.

Process of Deletion:
Since deleting an element at any intermediary position in the heap can be costly, so we can simply replace the element to be deleted by the last element and delete the last element of the Heap.

• Replace the root or element to be deleted by the last element.
• Delete the last element from the Heap.
• Since, the last element is now placed at the position of the root node. So, it may not follow the heap property. Therefore, heapify the last node placed at the position of root.

Heapify:

• If replaced element is greater than any of its child node in case of Min-Heap OR smaller than any if its child node in case of Max-Heap, swap the element with its smallest child(Min-Heap) or with its greatest child(Max-Heap).
• Keep repeating the above step, if node reaches its correct position, STOP.