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

#include<iostream>
#include<bits/stdc++.h>
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;
	if(largest!=curr)
	{
		int temp = heap[curr];
		heap[curr] = heap[largest];
		heap[largest] = temp;

		heapify(heap,largest,size);
	}
}

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
	heapSort(heap);

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