Heaps Usage : Heapify Vs Heap-Sort

Definition of Heap : Heap is a Complete Binary Tree, which satisfy the property that parent node value is larger than child nodes' (in case of MAX-HEAP) or smaller (in case of MIN-HEAP). This property of Heap has to be followed by each node with it's child nodes at each level of tree.

Storage in memory : Binary Tree is being stored in memory in form of array as data structure, following level traversal to order elements such that, for each index i as parent, children would be 2i+1 and 2i+2

Heapify(Construct Heap) is an approach (either top-down or bottom-up), which arranges elements in any array such that, when checked for any index i as parent, its child nodes values at index 2i+1 and 2i+2 would follow either MAX-HEAP or MIN-HEAP property. It doesn't sort array in ascending or descending order.

Heap-Sort : Sort array in ascending or descending order. As name suggests, we are using Heap BT property here to rearrange array elements. Heap Sort is an application of Heap BT.

Steps to sort an input array via Heap-Sort:

1. Arrange array elements in order as of MAX-HEAP or MIN-HEAP, using Heapify(Construct Heap) logic. (Logically it will follow Heap BT property, but storage wise it is still an array)
2. Put a loop over array, start from root node, compare it with last leaf node, swap if required and delete leaf node. Insert deleted element in a different array. Follow this until all nodes are deleted. Now, when we delete any node in Heap, we need to do Heapify residual array as part of delete operation on Heap BT. And the deleted elements while insertion in array follows order as ascending (MIN-HEAP) or descending (MAX-HEAP).

This is similar to selection sort, which on comparison in each pass, places max/min element to final position and gets excluded in comparison in next pass.