Heapsort Algorithm | CODE Implementation

This video explains a very important heap concept which is the heapsort algorithm using a dry run example. I have explained all the required concepts for doing heapsort given an array.First, we need to build a heap from the given array.We can build either a maxheap or a minheap.Once our heap is formed, we need to do EXTRACT MAX for N-1 elements if we have total N elements in our array.Extract Max internally makes use of HEAPIFY algorithm.If we are using a maxheap then we do MAX-HEAPIFY otherwise we use MIN-HEAPIFY.All the concepts are explained using a dry run example.The code implementation is also shown at the end of the video.

Heapsort Algorithm Implementation

using namespace std;

void heapify(vector<int>& heap,int curr,int size)
	int largest = curr;
	int l = 2*curr+1;	//left child
	int r = 2*curr+2;	//right child

	if(l<size and heap[l]>heap[largest])
		largest = l;
	if(r<size and heap[r]>heap[largest])
		largest = r;
		int temp = heap[curr];
		heap[curr] = heap[largest];
		heap[largest] = temp;


void heapSort(vector<int>& heap)
	// Build heap (rearrange array)
    for (int i = heap.size() / 2 - 1; i >= 0; i--)
        heapify(heap, i);

	for(int i=heap.size()-1;i>0;--i)
		int temp = heap[0];	//Swap heap root with last element
		heap[0] = heap[i];
		heap[i] = temp;

		heapify(heap,0,i);	//Heapify root with heapsize = i

int main()
	vector<int> heap{ 9, 6, 8, 2, 1, 4, 3};	//Max-Heap

	cout<<"Heap in ASC is:\n";
	for(int i=0;i<heap.size();++i)
		cout<<heap[i]<<" ";
	return 0;

3 comment on “Heapsort Algorithm | CODE Implementation”

  • Tech Dose November 5, 2021

    for building heap you passed only heap and i not passed size .

    • Tech Dose November 13, 2021

      since we are using vector array for building and storing heap, the size can be found using size() function.

  • Tech Dose November 14, 2021

    plz provide code for extract heap,increase key,decrease key,insert element as soon as possible I need that

Write a comment