In the array the heap is stored in the form of a binary tree. Each node has two child nodes. The value of the node is always greater than its children. This property is called the heap property. The number of nodes in each level of the tree is always a power of two, except for the lowest level.

if Lower=0, the first item in the heap is stored in Heap[0], the second level is stored in Heap[1] and Heap[2], the third level is stored in Heap[3]....Heap[6], etc.

Post conditions of the Heap-Insert and Heap-Remove operations must be such that the heap property is maintained by reorganization of the Heap array. This operation of converting an existing array to conform to the heap property is called heapify.

Use your experience with creating classes for stacks and queues to implement the heap.
[Ref. stacks (Pg 187, Ford & Topp) and queues (Pg 206, Ford & Topp)]

• Assignment
  
  1. Implement a class for heap using an array. The class implementation and definitions can be in <heap.h>
     It should have private data members such as Lower and Upper (bounds of the array).
     It should have public methods to manipulate the heap:
     
     • Heap-Insert
     • Heap-Remove
     • Heap-Size
     • Heap-Initialize
  2. Write a method called Heapify, which takes as input a list of numbers and converts it into a Heap array.
  3. Heap-Insert and Heap-Remove should call Heapify to reorganize the heap array after an insertion or a deletion.
  4. By ensuring that the left child node is always less than its right sibling, the same heap can be used to do binary search. Prompt the user for an item to be searched. Use a binary search procedure that returns the index of the item in the array.
  5. Use the Heap-Remove method to return a sorted list of items in the heap. What will be the complexity of this sorting algorithm.