What do you mean by Heapify?

code must be done in c++ thank you

heapify. (algorithm) Definition: Rearrange a heap to maintain the heap property, that is, the key of the root node is more extreme (greater or less) than or equal to the keys of its children.

Note: For an array implementation, heapify takes O(log2 n) or O(h) time under the comparison model, where n is the number of nodes and h is the height.

link to video

https://www.youtube.com/watch?v=WsNQuCa_-PU

Max Heap Construction Algorithm

We shall use the same example to demonstrate how a Max Heap is created. The procedure to create Min Heap is similar but we go for min values instead of max values.

We are going to derive an algorithm for max heap by inserting one element at a time. At any point of time, heap must maintain its property. While insertion, we also assume that we are inserting a node in an already heapified tree.

Step 1 - Create a new node at the end of heap. Step 2 - Assign new value to the node. Step 3 - Compare the value of this child node with its parent. Step 4 - If value of parent is less than child, then swap them. Step 5 - Repeat step 3 & 4 until Heap property holds. 

Note - In Min Heap construction algorithm, we expect the value of the parent node to be less than that of the child node.

Let's understand Max Heap construction by an animated illustration. We consider the same input sample that we used earlier.

Write a program to prompt the use for a set of integers and enqueue each one into a heap of integers. Then print the heap (binary tree). Then dequeue all of the integers into an array, effectively executing a Heap Sort.