A min heap is a special type of binary tree with two essential properties: 

2. The values in each node are smaller than all of their children nodes,
4. The binary tree is complete; all of the levels in the tree are full except possibly the lowest level of the tree, which is filled in from left to right.

What is a heap good for? It is a very good data structure for storing / retrieving N data values, where the largest value is always on the root of the tree. Since a binary tree is used, the cost of each insertion or deletion is O(log N) steps, which is far faster than we could expect using an unsorted or sorted array or linked list.

By restricting a heap to be a complete binary tree, it turns out that we can store the values in a heap in an array instead of using nodes with left, right, parent pointers. The trick is to store the root at location 0. For all nodes in the tree, we store the left child of node K in location 2K+1, and the right child of node K in location 2K+2. The result is that as we fill the array from positions 0 N-1 by traversing the heap from top-bottom, and left-right. This is illustrated below.

Figure 1: Minimum Heap

Consider the following C++ declaration of the Heap class. You will see that the class has five public operations:

2. Insert
4. Remove
6. IsFull
8. IsEmpty
10. Print

TASK

Implement the methods of class MinHeap which are declared above.

Implement max heap from above MinHeap class definition.

Transcribed Image Text:

12 18 5 9 8 3 59 68 20 10 12 18 9 1 2 3 4 5 6 7 8 9 10 20) 10 12 18 5 9 8 3 59 68 20 10 12 18 9 1 2 3 4 5 6 7 8 9 10 20) 10