# Heap Sort (Introduction, Algorithm and Program using C)

Learn: In this article we are going to study about **Heap sort, Implementation of heap sort in C language and the algorithm for heap sort**.

Submitted by Abhishek Kataria, on June 13, 2018

## Heap sort

**Heap sort** was invented by John Williams. Heap sort is a sorting technique of data structure which uses the approach just opposite to selection sort. The selection sort finds the smallest element among n elements then the smallest element among n-1 elements and so on. Until the end of the array heap sort finds the largest element and put it at end of the array, the second largest element is found and this process is repeated for all other elements

## What is Heap?

Heap is a complete binary tree in which every parent node be either greater or lesser than its child nodes. Heap can be of two types that are:

**1) Max heap**

A max heap is a tree in which value of each node is greater than or equal to the value of its children node.

**Example of max heap:**

**2) Min heap**

A min heap is a tree in which value of each node is less than or equal to the value of its children node.

**Example of min heap:**

### Working of Heap Sort

- The heap sort begins by building a heap out of the data set and then removing the largest item and placing it at the end of the sorted array.
- After removing the largest item, it reconstructs the heap and removes the largest remaining item and places it in the next open position from the open position from the end of the sorted array.
- This is repeated until there is no item left in the heap and the sorted array is full.
- Elementary implementation requires two arrays one to hold the heap and the other to hold the sorted elements.

### Algorithm for heap sort

**Procedure 1:**

INSHEAP(TREE, N, HEAP):

- A heap H with N elements is stored in the array TREE, and VALUE information is given.
- This procedure inserts ITEM as a new element of H.
- PTR gives the location of ITEM as it rises in the tree, and PAR denotes the location of the parent of VALUE.

**[Add new node to H and initialize PTR]**

Set N: N+1 and PTR: =N**[Find location to insert VALUE]**

[Find location to insert VALUE]- Set PAR:=[PTR/2] {Location of parent node}
- If VALUE <=TREE[PAR],Then:

Set TREE[PTR]:=VALUE ,and return - Set TREE[PTR]:=TREE[PAR]
- Set PTR:=PAR

[End of step 2 loop] **[Assign VALUE as the root of H]**

Set TREE[1]:=VALUE- Return

**Procedure 2:**

DELHEAP(TREE,N,VALUE):

- A Heap H with N elements is stored in the array TREE.
- This procedure assigns the root TREE [1] of H to the variable VALUE and then reheaps the remaining elements.
- The variable LAST saves the value of the original last node of H.
- The pointer PTR, LEFT and RIGHT gives the location of LAST and its left and right children as LAST sinks in the tree.

- Set VALUE:=TREE[1]
- Set LAST:=TREE[N] and N :=N-1
- Set PTR:=1,LEFT:=2 and RIGHT:=3
- Repeats steps 5 to 7 while RIGHT<=N:
- If LAST >=TREE[LEFT] and LAST>=TREE [RIGHT], then:

Set TREE[PTR]:=LAST and return - If TREE [RIGHT]<=TREE[LEFT],then:

Set TREE[PTR]:=TREE[LEFT] and PTR:=LEFT

Else:

Set TREE[PTR]:=TREE[RIGHT] and PTR:=RIGHT - Set LEFT:=2*PTR and RIGHT:=LEFT+1
- If LEFT=N and if LAST<TREE[LEFT],then: set PTR :=LEFT
- Set TREE[PTR]:=LAST
- Return

**Algorithm**

HEAPSORT (A, N):

- An array A with N elements is given.
- This algorithm sorts the element of A.

- [Build a heap A ,using a procedure 1]

Repeat for J=1 to N-1

Call INSHEAP(A, J, A[J+1]) - [sort A by repeatedly deleting the root of H, using procedure 2]

Repeat while N>1:

Call DELHEAP(A , N,VALUE)

Set A[n+1]:=value - Exit

### Performance of heap sort

Heap Sort has O(nlog^{n}) time complexities for all the cases (best case, average case and worst case).

### Program for heap sort in C language

#include<stdio.h> void create(int []); void down_adjust(int [],int); int main() { int heap[30],n,i,last,temp; printf("Enter no. of elements:"); scanf("%d",&n); printf("\nEnter elements:"); for(i=1;i<=n;i++) scanf("%d",&heap[i]); //create a heap heap[0]=n; create(heap); //sorting while(heap[0] > 1) { //swap heap[1] and heap[last] last=heap[0]; temp=heap[1]; heap[1]=heap[last]; heap[last]=temp; heap[0]--; down_adjust(heap,1); } //print sorted data printf("\nArray after sorting:\n"); for(i=1;i<=n;i++) printf("%d ",heap[i]); return 0; } void create(int heap[]) { int i,n; n=heap[0]; //no. of elements for(i=n/2;i>=1;i--) down_adjust(heap,i); } void down_adjust(int heap[],int i) { int j,temp,n,flag=1; n=heap[0]; while(2*i<=n && flag==1) { j=2*i; //j points to left child if(j+1<=n && heap[j+1] > heap[j]) j=j+1; if(heap[i] > heap[j]) flag=0; else { temp=heap[i]; heap[i]=heap[j]; heap[j]=temp; i=j; } } }

**Output**

Enter no. of elements:5 Enter elements:12 8 46 3 7 Array after sorting: 7 8 12 23 46

TOP Interview Coding Problems/Challenges

- Run-length encoding (find/print frequency of letters in a string)
- Sort an array of 0's, 1's and 2's in linear time complexity
- Checking Anagrams (check whether two string is anagrams or not)
- Relative sorting algorithm
- Finding subarray with given sum
- Find the level in a binary tree with given sum K
- Check whether a Binary Tree is BST (Binary Search Tree) or not
- 1[0]1 Pattern Count
- Capitalize first and last letter of each word in a line
- Print vertical sum of a binary tree
- Print Boundary Sum of a Binary Tree
- Reverse a single linked list
- Greedy Strategy to solve major algorithm problems
- Job sequencing problem
- Root to leaf Path Sum
- Exit Point in a Matrix
- Find length of loop in a linked list
- Toppers of Class
- Print All Nodes that don't have Sibling
- Transform to Sum Tree
- Shortest Source to Destination Path

Comments and Discussions

**Ad:**
Are you a blogger? Join our Blogging forum.