7. In-place heap #

Created Saturday 15 February 2020

• We need to convert an array into a heap.
• To start, visualize like this:
  1. The first element is a heap.
  2. We insert the a new element at the end o fthe array. Which it is, naturally.
  3. Here we sift the newly inserted element up. Till the heap property is satisfied.
  4. Eventually, we have a heap.

T.C for this operation:

• We have a heap. To sort the elements, do this.

  1. removeMIn(). We swap the end of the heap and the root, i.e index 0.
  2. We sift the index 0 element down, until the heap order property is satisfied. Which will happen eventually.
  3. continue till we all the elements are over.

• We have the sorted array in decreasing(non-increasing) order.

• minHeap is used for reverse sort.

• max heap for sorting.

We