Heap Sort

Heap sort is a comparison based sorting technique based on Binary Heap data structure. It is similar to selection sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for remaining element.

What is Heap ?

Heap is a special tree-based data structure. A binary tree is said to follow a heap data structure if

it is a complete binary tree

All nodes in the tree follow the property that they are greater than their children i.e. the largest element is at the root and both its children and smaller than the root and so on. Such a heap is called a max-heap. If instead all nodes are smaller than their children, it is called a min-heap

Following example diagram shows Max-Heap and Min-Heap.

How to Create Max Heap (Heapify)

Starting from a complete binary tree, we can modify it to become a Max-Heap by running a function called heapify on all the non-leaf elements of the heap.

For Example

There are some scenario to Create a Max Heapify:

The example above shows two scenarios - one in which the root is the largest element and we don’t need to do anything. And another in which root had larger element as a child and we needed to swap to maintain max-heap property.

If you’re worked with recursive algorithms before, you’ve probably identified that this must be the base case.

Now let’s think of another scenario in which there are more than one levels.

The top element isn’t a max-heap but all the sub-trees are max-heaps.

To maintain the max-heap property for the entire tree, we will have to keep pushing 2 downwards until it reaches its correct position.

Thus, to maintain the max-heap property in a tree where both sub-trees are max-heaps, we need to run heapify on the root element repeatedly until it is larger than its children or it becomes a leaf node.

Insertion Operation in Max Heap

Insertion Operation in max heap is performed as follows...

Step 1: Insert the newNode as last leaf from left to right.

Step 2: Compare newNode value with its Parent node.

Step 3: If newNode value is greater than its parent, then swap both of them.

Step 4: Repeat step 2 and step 3 until newNode value is less than its parent nede (or) newNode reached to root.

Example

Consider the above max heap. Insert a new node with value 85.

Step 1: Insert the newNode with value 85 as last leaf from left to right. That means newNode is added as a right child of node with value 75. After adding max heap is as follows...

Step 2: Compare newNode value (85) with its Parent node value (75). That means 85 > 75

Step 3: Here newNode value (85) is greater than its parent value (75), then swap both of them. After wsapping, max heap is as follows...

Step 4: Now, again compare newNode value (85) with its parent nede value (89).

Here, newNode value (85) is smaller than its parent node value (89). So, we stop insertion process. Finally, max heap after insetion of a new node with value 85 is as follows...

Deletion Operation in Max Heap

In a max heap, deleting last node is very simple as it is not disturbing max heap properties.

Deleting root node from a max heap is title difficult as it disturbing the max heap properties. We use the following steps to delete root node from a max heap...

Step 1: Swap the root node with last node in max heap
Step 2: Delete last node.
Step 3: Now, compare root value with its left child value.
Step 4: If root value is smaller than its left child, then compare left child with its right sibling. Else goto Step 6
Step 5: If left child value is larger than its right sibling, then swap root with left child. otherwise swap root with its right child.
Step 6: If root value is larger than its left child, then compare root value with its right child value.
Step 7: If root value is smaller than its right child, then swap root with rith child. otherwise stop the process.
Step 8: Repeat the same until root node is fixed at its exact position.

Example

Consider the above max heap. Delete root node (90) from the max heap.

Step 1: Swap the root node (90) with last node 75 in max heap After swapping max heap is as follows...
Step 2: Delete last node. Here node with value 90. After deleting node with value 90 from heap, max heap is as follows...
Step 3: Compare root node (75) with its left child (89).
Here, root value (75) is smaller than its left child value (89). So, compare left child (89) with its right sibling (70).
Step 4: Here, left child value (89) is larger than its right sibling (70), So, swap root (75) with left child (89).
Step 5: Now, again compare 75 with its left child (36).
Here, node with value 75 is larger than its left child. So, we compare node with value 75 is compared with its right child 85.
Step 6: Here, node with value 75 is smaller than its right child (85). So, we swap both of them. After swapping max heap is as follows...
Step 7: Now, compare node with value 75 with its left child (15).
Here, node with value 75 is larger than its left child (15) and it does not have right child. So we stop the process.

Finally, max heap after deleting root node (90) is as follows...