What is a Heap Sort Algorithm in Data Structure? | Data Structure Tutorial

In this article, you will understand the Heap Sort Algorithm of the Data Structure in better detail.

A heap is nothing but a complete binary tree that satisfies the heap property, where the given nodes are:

• Always greater than its child node or nodes and the key of the root node is always greater than all other nodes. This property is known as the max heap property.
• Always smaller than its child node or nodes and the key of the root node is always smaller than the other nodes. This property is known as the min-heap property. 

This type of data structure is called a binary heap data structure.

Heap Operations

The operations on the heap data structure are:

1. Heapify: Heapify is the process of creating a heap data structure from a binary tree. It is used to generate a min-heap and a max-heap.
1. Assume the input array.
2. Create a complete binary tree from the given array.
3. Begin from the first index of a non-leaf node whose index is given by n/2-1.
4. Set current element j as greatest.
5. The index of the left child is given by 2j + 1 and the right child is given by 2j+1.

If leftChild is greater than the currentElement, set leftChildIndex as greatest.

If rightChild is greater than the element in greatest, set rightChildIndex as greatest.

1. Swap greatest with currentElement.
2. Repeat steps 3-7 to completely heapify the tree.

Algorithm 

Heap_sort(array, size, i)

   set j as the greatest

   leftChild = 2i+1

   rightChild = 2i+2

   if leftChild > array[greatest]

      set leftChildIndex as the greatest

   if rightChild > array[greatest]

      set rightChildIndex as the greatest

swap array[i] and array[greatest]

To create a Max-Heap:

Max_heap(array, size)

   loop from the first index of the non-leaf node down to zero

     call heapify

For Min-heap, both leftChild and RightChild must be greater than the parent of all nodes. 

Insert Element into Heap

Algorithm for insertion in Max Heap

if there is no node, 

   create a newNode

else ( a node is already available)

   insert the newNode at the end (last node from left to right)

heapify the array

1. Insert the new element always at the end of the tree.
2. Heapify the tree.

To perform the min heap, the above algorithm is modified so that parentNode is always smaller than newNode.

Delete Element From Heap

Algorithm for deletion in Max Heap

if nodeToBeDeleted is the leafNode

    remove the node

Else swap nodeToBeDeleted with the lastLeafNode

    remove node

Heapify the array

1. Choose the element to be deleted
2. Swap the element with the last element in the array.
3. Remove the last element
4. Heapify the array

Applications of Heap Data Structure

• It is used in Heap Sort
• It is used in implementing Dijkstra’s Algorithm
• It is used in the priority queue.