## 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

```#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;
}```

### 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