Heap Sort

                          Heap Sort

Time Complexity: Time complexity of heapify is O(nLogn). Time complexity of createAndBuildHeap() is O(n) and overall time complexity of Heap Sort is O(nLogn).

hackerearth

GeeksForGeeks

visualization

	#include<bits/stdc++.h>
	using namespace std;
	void heapify(int a[], int n, int i)
	{
	int largest = i;
	int l = 2*i + 1;
	int r = 2*i + 2;
	// If left child is larger than root
	if(l < n && a[l] > a[largest])
	largest = l;
	if(r < n && a[r] > a[largest])
	largest = r;
	if(largest != i)
	{
	swap(a[i], a[largest]);
	heapify(a, n,largest);
	}
	}
	void heapSort(int ar[], int n)
	{
	for(int i = n/2 - 1; i >= 0; i--){
	heapify(ar, n,i);
	}
	for(int i = n - 1; i >= 0; i--){
	swap(ar[0], ar[i]);
	heapify(ar,i,0);
	}
	}
	void print(int a[], int n)
	{
	for(int i = 0 ; i < n; i++){
	cout << a[i] << " ";
	}
	cout << endl;
	}
	int main()
	{
	int ar[] = {12, 11, 13, 5, 6, 7};
	int n = sizeof(ar)/sizeof(ar[0]);
	heapSort(ar,n);
	print(ar,n);
	return 0;
	}

view raw heapSort.cpp hosted with ❤ by GitHub

Share: