What is a Heap Sort Algorithm in Data Structure? | Data Structure Tutorial
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:
- 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.
- Assume the input array.
- Create a complete binary tree from the given array.
- Begin from the first index of a non-leaf node whose index is given by n/2-1.
- Set current element j as greatest.
- 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.
- Swap greatest with currentElement.
- 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
- Insert the new element always at the end of the tree.
- 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
- Choose the element to be deleted
- Swap the element with the last element in the array.
- Remove the last element
- 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.