Heap Sort (With Code in Python, C++, Java and C) - Programiz

Heap sort works by visualizing the elements of the array as a special kind of complete binary tree called a heap. Note: As a prerequisite, you must know ... CourseIndex ExploreProgramiz Python JavaScript SQL C C++ Java Kotlin Swift C# DSA PopularTutorials QuicksortAlgorithm MergeSortAlgorithm LinkedListDataStructure HashTableDataStructure DynamicProgramming StartLearningDSA LearningPaths Challenges LearnPythonInteractively TryforFree Courses BecomeaPythonMaster BecomeaCMaster BecomeaJavaMaster ViewallCourses Python JavaScript SQL C C++ Java Kotlin Swift C# DSA PopularTutorials QuicksortAlgorithm MergeSortAlgorithm LinkedListDataStructure HashTableDataStructure DynamicProgramming StartLearningDSA AllDSATutorials Python JavaScript C C++ Java Kotlin PopularExamples Addtwonumbers Checkprimenumber Findthefactorialofanumber PrinttheFibonaccisequence Checkleapyear AllPythonExamples DSAIntroduction Whatisanalgorithm? DataStructureandTypes WhylearnDSA? AsymptoticNotations MasterTheorem DivideandConquerAlgorithm DataStructures(I) Stack Queue TypesofQueue CircularQueue PriorityQueue Deque DataStructures(II) LinkedList LinkedListOperations TypesofLinkedList HashTable HeapDataStructure FibonacciHeap DecreaseKeyandDeleteNodeOperationsonaFibonacciHeap TreebasedDSA(I) TreeDataStructure TreeTraversal BinaryTree FullBinaryTree PerfectBinaryTree CompleteBinaryTree BalancedBinaryTree BinarySearchTree AVLTree TreebasedDSA(II) BTree InsertioninaB-tree DeletionfromaB-tree B+Tree InsertiononaB+Tree DeletionfromaB+Tree Red-BlackTree Red-BlackTreeInsertion Red-BlackTreeDeletion GraphbasedDSA GraphDataStructure SpanningTree StronglyConnectedComponents AdjacencyMatrix AdjacencyList DFSAlgorithm Breadth-firstSearch BellmanFord'sAlgorithm SortingandSearchingAlgorithms BubbleSort SelectionSort InsertionSort MergeSort Quicksort CountingSort RadixSort BucketSort HeapSort ShellSort LinearSearch BinarySearch GreedyAlgorithms GreedyAlgorithm Ford-FulkersonAlgorithm Dijkstra'sAlgorithm Kruskal'sAlgorithm Prim'sAlgorithm HuffmanCoding DynamicProgramming DynamicProgramming Floyd-WarshallAlgorithm LongestCommonSequence OtherAlgorithms BacktrackingAlgorithm Rabin-KarpAlgorithm RelatedTopics HeapDataStructure PriorityQueue CompleteBinaryTree TreeDataStructure SortingAlgorithm FibonacciHeap HeapSortAlgorithm Inthistutorial,youwilllearnabouttheheapsortalgorithmanditsimplementationinPython,Java,C,andC++. HeapSortisapopularandefficientsortingalgorithmincomputerprogramming.Learninghowtowritetheheapsortalgorithmrequiresknowledgeoftwotypesofdatastructures-arraysandtrees. Theinitialsetofnumbersthatwewanttosortisstoredinanarraye.g.[10,3,76,34,23,32]andaftersorting,wegetasortedarray[3,10,23,32,34,76]. Heapsortworksbyvisualizingtheelementsofthearrayasaspecialkindofcompletebinarytreecalledaheap. Note:Asaprerequisite,youmustknowaboutacompletebinarytreeandheapdatastructure. RelationshipbetweenArrayIndexesandTreeElements Acompletebinarytreehasaninterestingpropertythatwecanusetofindthechildrenandparentsofanynode. Iftheindexofanyelementinthearrayisi,theelementintheindex2i+1willbecometheleftchildandelementin2i+2indexwillbecometherightchild.Also,theparentofanyelementatindexiisgivenbythelowerboundof(i-1)/2. RelationshipbetweenarrayandheapindicesLet'stestitout, Leftchildof1(index0) =elementin(2*0+1)index =elementin1index =12 Rightchildof1 =elementin(2*0+2)index =elementin2index =9 Similarly, Leftchildof12(index1) =elementin(2*1+1)index =elementin3index =5 Rightchildof12 =elementin(2*1+2)index =elementin4index =6 Letusalsoconfirmthattherulesholdforfindingparentofanynode Parentof9(position2) =(2-1)/2 =½ =0.5 ~0index =1 Parentof12(position1) =(1-1)/2 =0index =1 UnderstandingthismappingofarrayindexestotreepositionsiscriticaltounderstandinghowtheHeapDataStructureworksandhowitisusedtoimplementHeapSort. WhatisHeapDataStructure? Heapisaspecialtree-baseddatastructure.Abinarytreeissaidtofollowaheapdatastructureif itisacompletebinarytree Allnodesinthetreefollowthepropertythattheyaregreaterthantheirchildreni.e.thelargestelementisattherootandbothitschildrenandsmallerthantherootandsoon.Suchaheapiscalledamax-heap.Ifinstead,allnodesaresmallerthantheirchildren,itiscalledamin-heap ThefollowingexamplediagramshowsMax-HeapandMin-Heap. MaxHeapandMinHeapTolearnmoreaboutit,pleasevisitHeapDataStructure. Howto"heapify"atree Startingfromacompletebinarytree,wecanmodifyittobecomeaMax-Heapbyrunningafunctioncalledheapifyonallthenon-leafelementsoftheheap. Sinceheapifyusesrecursion,itcanbedifficulttograsp.Solet'sfirstthinkabouthowyouwouldheapifyatreewithjustthreeelements. heapify(array) Root=array[0] Largest=largest(array[0],array[2*0+1].array[2*0+2]) if(Root!=Largest) Swap(Root,Largest) HeapifybasecasesTheexampleaboveshowstwoscenarios-oneinwhichtherootisthelargestelementandwedon'tneedtodoanything.Andanotherinwhichtheroothadalargerelementasachildandweneededtoswaptomaintainmax-heapproperty. Ifyou'reworkedwithrecursivealgorithmsbefore,you'veprobablyidentifiedthatthismustbethebasecase. Nowlet'sthinkofanotherscenarioinwhichthereismorethanonelevel. HowtoheapifyrootelementwhenitssubtreesarealreadymaxheapsThetopelementisn'tamax-heapbutallthesub-treesaremax-heaps. Tomaintainthemax-heappropertyfortheentiretree,wewillhavetokeeppushing2downwardsuntilitreachesitscorrectposition. Howtoheapifyrootelementwhenitssubtreesaremax-heapsThus,tomaintainthemax-heappropertyinatreewherebothsub-treesaremax-heaps,weneedtorunheapifyontherootelementrepeatedlyuntilitislargerthanitschildrenoritbecomesaleafnode. Wecancombineboththeseconditionsinoneheapifyfunctionas voidheapify(intarr[],intn,inti){ //Findlargestamongroot,leftchildandrightchild intlargest=i; intleft=2*i+1; intright=2*i+2; if(leftarr[largest]) largest=left; if(rightarr[largest]) largest=right; //Swapandcontinueheapifyingifrootisnotlargest if(largest!=i){ swap(&arr[i],&arr[largest]); heapify(arr,n,largest); } } Thisfunctionworksforboththebasecaseandforatreeofanysize.Wecanthusmovetherootelementtothecorrectpositiontomaintainthemax-heapstatusforanytreesizeaslongasthesub-treesaremax-heaps. Buildmax-heap Tobuildamax-heapfromanytree,wecanthusstartheapifyingeachsub-treefromthebottomupandendupwithamax-heapafterthefunctionisappliedtoalltheelementsincludingtherootelement. Inthecaseofacompletetree,thefirstindexofanon-leafnodeisgivenbyn/2-1.Allothernodesafterthatareleaf-nodesandthusdon'tneedtobeheapified. So,wecanbuildamaximumheapas //Buildheap(rearrangearray) for(inti=n/2-1;i>=0;i--) heapify(arr,n,i); CreatearrayandcalculateiStepstobuildmaxheapforheapsortStepstobuildmaxheapforheapsortStepstobuildmaxheapforheapsortAsshownintheabovediagram,westartbyheapifyingthelowestsmallesttreesandgraduallymoveupuntilwereachtherootelement. Ifyou'veunderstoodeverythingtillhere,congratulations,youareonyourwaytomasteringtheHeapsort. WorkingofHeapSort SincethetreesatisfiesMax-Heapproperty,thenthelargestitemisstoredattherootnode. Swap:Removetherootelementandputattheendofthearray(nthposition)Putthelastitemofthetree(heap)atthevacantplace. Remove:Reducethesizeoftheheapby1. Heapify:Heapifytherootelementagainsothatwehavethehighestelementatroot. Theprocessisrepeateduntilalltheitemsofthelistaresorted. Swap,Remove,andHeapifyThecodebelowshowstheoperation. //Heapsort for(inti=n-1;i>=0;i--){ swap(&arr[0],&arr[i]); //Heapifyrootelementtogethighestelementatrootagain heapify(arr,i,0); } HeapSortCodeinPython,Java,andC/C++ Python Java C C++ #HeapSortinpython defheapify(arr,n,i): #Findlargestamongrootandchildren largest=i l=2*i+1 r=2*i+2 ifl=0;i--){ heapify(arr,n,i); } //Heapsort for(inti=n-1;i>=0;i--){ inttemp=arr[0]; arr[0]=arr[i]; arr[i]=temp; //Heapifyrootelement heapify(arr,i,0); } } voidheapify(intarr[],intn,inti){ //Findlargestamongroot,leftchildandrightchild intlargest=i; intl=2*i+1; intr=2*i+2; if(larr[largest]) largest=l; if(rarr[largest]) largest=r; //Swapandcontinueheapifyingifrootisnotlargest if(largest!=i){ intswap=arr[i]; arr[i]=arr[largest]; arr[largest]=swap; heapify(arr,n,largest); } } //Functiontoprintanarray staticvoidprintArray(intarr[]){ intn=arr.length; for(inti=0;i //Functiontoswapthethepositionoftwoelements voidswap(int*a,int*b){ inttemp=*a; *a=*b; *b=temp; } voidheapify(intarr[],intn,inti){ //Findlargestamongroot,leftchildandrightchild intlargest=i; intleft=2*i+1; intright=2*i+2; if(leftarr[largest]) largest=left; if(rightarr[largest]) largest=right; //Swapandcontinueheapifyingifrootisnotlargest if(largest!=i){ swap(&arr[i],&arr[largest]); heapify(arr,n,largest); } } //Mainfunctiontodoheapsort voidheapSort(intarr[],intn){ //Buildmaxheap for(inti=n/2-1;i>=0;i--) heapify(arr,n,i); //Heapsort for(inti=n-1;i>=0;i--){ swap(&arr[0],&arr[i]); //Heapifyrootelementtogethighestelementatrootagain heapify(arr,i,0); } } //Printanarray voidprintArray(intarr[],intn){ for(inti=0;i usingnamespacestd; voidheapify(intarr[],intn,inti){ //Findlargestamongroot,leftchildandrightchild intlargest=i; intleft=2*i+1; intright=2*i+2; if(leftarr[largest]) largest=left; if(rightarr[largest]) largest=right; //Swapandcontinueheapifyingifrootisnotlargest if(largest!=i){ swap(arr[i],arr[largest]); heapify(arr,n,largest); } } //mainfunctiontodoheapsort voidheapSort(intarr[],intn){ //Buildmaxheap for(inti=n/2-1;i>=0;i--) heapify(arr,n,i); //Heapsort for(inti=n-1;i>=0;i--){ swap(arr[0],arr[i]); //Heapifyrootelementtogethighestelementatrootagain heapify(arr,i,0); } } //Printanarray voidprintArray(intarr[],intn){ for(inti=0;i