Heap Sort Algorithm - Javatpoint

In this article, we will discuss the Heapsort Algorithm. Heap sort processes the elements by creating the min-heap or max-heap using the elements of the ... ⇧SCROLLTOTOP Home DataStructure C C++ C# Java SQL HTML CSS JavaScript Ajax Android Cloud DesignPattern Quiz Projects InterviewQ Comment Forum DSTutorial DSTutorial DSIntroduction DSAlgorithm AsymptoticAnalysis DSPointer DSStructure DSArray DSArray 2DArray DSLinkedList LinkedList TypesofLinkedList SinglyLinkedList DoublyLinkedList CircularLinkedList CircularDoublyList SkiplistinDS DSStack DSStack ArrayImplementation LinkedListImplementation DSQueue DSQueue TypesofQueues ArrayRepresentation LinkedListRepresentation CircularQueue Deque PriorityQueue DSTree DSTree BinaryTree BinarySearchTree AVLTree BTree B+Tree DSGraph DSGraph GraphImplementation BFSAlgorithm DFSAlgorithm SpanningTree DSSearching LinearSearch BinarySearch DSSorting BubbleSort BucketSort CombSort CountingSort HeapSort InsertionSort MergeSort QuickSort RadixSort SelectionSort ShellSort BitonicSort CocktailSort CycleSort TimSort Differences Linearvsnon-linear Arrayvslinkedlist Stackvsqueue LinearvsCircularQueue LinearSearchvsBinarySearch SinglyLinkedListvsDoublyLinkedList BinaryvsBinarySearchTree TreevsGraph BinarySearchtreevsAVLtree RedBlackTreevsAVLtree BtreevsB+tree QuickSortvsMergeSort BFSvsDFS StackvsHeap Bubblesortvs.Selectionsort StackvsArray FullBinaryTreevsCompleteBinaryTree BinaryTreevsBTree Primitivevsnon-primitivedatastructure Datatypesvsdatastructure Misc TrieDataStructure HeapDataStructure SplayTree FundamentaloftheDS HashTable PreorderTraversal TreeTraversal ImplementationofQueueusingStacks ImplementationofStackusingQueue BinomialHeap PostorderTraversal SparseMatrix DetectloopinaLinkedlist InorderTraversal ConvertInfixtoPostfixnotation Convertinfixtoprefixnotation ConversionofPrefixtoPostfixexpression ConversionofPostfixtoPrefixexpression RemovetheloopinaLinkedList Implementtwostacksinanarray Reverseastackusingrecursion Detectcycleinadirectedgraph OptimalBinarySearchTree PriorityQueueusingLinkedlist BalancedBinarySearchTree BoundaryTraversalofBinarytree DiagonalTraversalofBinaryTree VerticalTraversalofaBinarytree GraphAlgorithms TimeComplexityofSortingAlgorithms ApplicationsofStackinDataStructure DictionaryDataStructure StructuredDataandUnstructuredData ListDataStructure TypesofTreeinDataStructure Abstractdatatypeindatastructure Disjointsetdatastructure DynamicDataStructure HashFunctioninDataStructure CompleteBinaryTree ThreadedBinaryTree DiameterofBinaryTree HeightofBinaryTree InorderTreeTraversalwithoutStack EnumerationofBinaryTrees MaximumWidthofaBinaryTree TypesofGraphinDataStructure PrimitiveDataType Semi-StructuredData AdvanceDataStructures SortanArrayof0's,1's,and2's StockSpanProblem ImplementationofDequebyCircularArray RotateOperationinLinkedList Subarraywithgivensum Self-organizingList UnrolledLinkedList TypesofSparseMatrices ApplicationofLinkedList TopologicalSorting TernarySearchTree StockSpanProblem TreapDataStructure QuicksortonDoublyLinkedList Inversioncount ExpressiontreeinDS GarbageCollectioninDS MergeSortonDoublyLinkedList SortStackusingRecursion LIFOApproachindatastructure BigONotationinDS BinaryTreeTraversalinDS QueueOperationsinDS WhatisaNon-LinearDataStructure FIFOApproachindatastructure Whatareconnectedgraphsindatastructure WhichPythondatastructureisimmutable Whichdatastructureisusedbymap Whatisiterationindatastructure Whatarelinearsearchandbinarysearchindatastructure HashTablevsSTLMap Recaman'sSequence Maximumarearectanglecreatedbyselectingfoursidesfromanarray Maximumnumberofdistinctnodesinaroot-to-leafpath DSMCQ DataStructureMCQ AdvancedDSMCQ next→ ←prev HeapSortAlgorithm Inthisarticle,wewilldiscusstheHeapsortAlgorithm.Heapsortprocessestheelementsbycreatingthemin-heapormax-heapusingtheelementsofthegivenarray.Min-heapormax-heaprepresentstheorderingofarrayinwhichtherootelementrepresentstheminimumormaximumelementofthearray. Heapsortbasicallyrecursivelyperformstwomainoperations- BuildaheapH,usingtheelementsofarray. Repeatedlydeletetherootelementoftheheapformedin1stphase. Beforeknowingmoreabouttheheapsort,let'sfirstseeabriefdescriptionofHeap. Whatisaheap? Aheapisacompletebinarytree,andthebinarytreeisatreeinwhichthenodecanhavetheutmosttwochildren.Acompletebinarytreeisabinarytreeinwhichallthelevelsexceptthelastlevel,i.e.,leafnode,shouldbecompletelyfilled,andallthenodesshouldbeleft-justified. Whatisheapsort? Heapsortisapopularandefficientsortingalgorithm.Theconceptofheapsortistoeliminatetheelementsonebyonefromtheheappartofthelist,andtheninsertthemintothesortedpartofthelist. Heapsortisthein-placesortingalgorithm. Now,let'sseethealgorithmofheapsort. Algorithm HeapSort(arr) BuildMaxHeap(arr) fori=length(arr)to2 swaparr[1]witharr[i] heap_size[arr]=heap_size[arr]?1 MaxHeapify(arr,1) End BuildMaxHeap(arr) BuildMaxHeap(arr) heap_size(arr)=length(arr) fori=length(arr)/2to1 MaxHeapify(arr,i) End MaxHeapify(arr,i) MaxHeapify(arr,i) L=left(i) R=right(i) ifL?heap_size[arr]andarr[L]>arr[i] largest=L else largest=i ifR?heap_size[arr]andarr[R]>arr[largest] largest=R iflargest!=i swaparr[i]witharr[largest] MaxHeapify(arr,largest) End WorkingofHeapsortAlgorithm Now,let'sseetheworkingoftheHeapsortAlgorithm. Inheapsort,basically,therearetwophasesinvolvedinthesortingofelements.Byusingtheheapsortalgorithm,theyareasfollows- Thefirststepincludesthecreationofaheapbyadjustingtheelementsofthearray. Afterthecreationofheap,nowremovetherootelementoftheheaprepeatedlybyshiftingittotheendofthearray,andthenstoretheheapstructurewiththeremainingelements. Nowlet'sseetheworkingofheapsortindetailbyusinganexample.Tounderstanditmoreclearly,let'stakeanunsortedarrayandtrytosortitusingheapsort.Itwillmaketheexplanationclearerandeasier. First,wehavetoconstructaheapfromthegivenarrayandconvertitintomaxheap. Afterconvertingthegivenheapintomaxheap,thearrayelementsare- Next,wehavetodeletetherootelement(89)fromthemaxheap.Todeletethisnode,wehavetoswapitwiththelastnode,i.e.(11).Afterdeletingtherootelement,weagainhavetoheapifyittoconvertitintomaxheap. Afterswappingthearrayelement89with11,andconvertingtheheapintomax-heap,theelementsofarrayare- Inthenextstep,again,wehavetodeletetherootelement(81)fromthemaxheap.Todeletethisnode,wehavetoswapitwiththelastnode,i.e.(54).Afterdeletingtherootelement,weagainhavetoheapifyittoconvertitintomaxheap. Afterswappingthearrayelement81with54andconvertingtheheapintomax-heap,theelementsofarrayare- Inthenextstep,wehavetodeletetherootelement(76)fromthemaxheapagain.Todeletethisnode,wehavetoswapitwiththelastnode,i.e.(9).Afterdeletingtherootelement,weagainhavetoheapifyittoconvertitintomaxheap. Afterswappingthearrayelement76with9andconvertingtheheapintomax-heap,theelementsofarrayare- Inthenextstep,againwehavetodeletetherootelement(54)fromthemaxheap.Todeletethisnode,wehavetoswapitwiththelastnode,i.e.(14).Afterdeletingtherootelement,weagainhavetoheapifyittoconvertitintomaxheap. Afterswappingthearrayelement54with14andconvertingtheheapintomax-heap,theelementsofarrayare- Inthenextstep,againwehavetodeletetherootelement(22)fromthemaxheap.Todeletethisnode,wehavetoswapitwiththelastnode,i.e.(11).Afterdeletingtherootelement,weagainhavetoheapifyittoconvertitintomaxheap. Afterswappingthearrayelement22with11andconvertingtheheapintomax-heap,theelementsofarrayare- Inthenextstep,againwehavetodeletetherootelement(14)fromthemaxheap.Todeletethisnode,wehavetoswapitwiththelastnode,i.e.(9).Afterdeletingtherootelement,weagainhavetoheapifyittoconvertitintomaxheap. Afterswappingthearrayelement14with9andconvertingtheheapintomax-heap,theelementsofarrayare- Inthenextstep,againwehavetodeletetherootelement(11)fromthemaxheap.Todeletethisnode,wehavetoswapitwiththelastnode,i.e.(9).Afterdeletingtherootelement,weagainhavetoheapifyittoconvertitintomaxheap. Afterswappingthearrayelement11with9,theelementsofarrayare- Now,heaphasonlyoneelementleft.Afterdeletingit,heapwillbeempty. Aftercompletionofsorting,thearrayelementsare- Now,thearrayiscompletelysorted. Heapsortcomplexity Now,let'sseethetimecomplexityofHeapsortinthebestcase,averagecase,andworstcase.WewillalsoseethespacecomplexityofHeapsort. 1.TimeComplexity Case TimeComplexity BestCase O(nlogn) AverageCase O(nlogn) WorstCase O(nlogn) BestCaseComplexity-Itoccurswhenthereisnosortingrequired,i.e.thearrayisalreadysorted.Thebest-casetimecomplexityofheapsortisO(nlogn). AverageCaseComplexity-Itoccurswhenthearrayelementsareinjumbledorderthatisnotproperlyascendingandnotproperlydescending.TheaveragecasetimecomplexityofheapsortisO(nlogn). WorstCaseComplexity-Itoccurswhenthearrayelementsarerequiredtobesortedinreverseorder.Thatmeanssupposeyouhavetosortthearrayelementsinascendingorder,butitselementsareindescendingorder.Theworst-casetimecomplexityofheapsortisO(nlogn). ThetimecomplexityofheapsortisO(nlogn)inallthreecases(bestcase,averagecase,andworstcase).Theheightofacompletebinarytreehavingnelementsislogn. 2.SpaceComplexity SpaceComplexity O(1) Stable N0 ThespacecomplexityofHeapsortisO(1). ImplementationofHeapsort Now,let'sseetheprogramsofHeapsortindifferentprogramminglanguages. Program:WriteaprogramtoimplementheapsortinClanguage. #include /*functiontoheapifyasubtree.Here'i'isthe indexofrootnodeinarraya[],and'n'isthesizeofheap.*/ voidheapify(inta[],intn,inti) { intlargest=i;//Initializelargestasroot intleft=2*i+1;//leftchild intright=2*i+2;//rightchild //Ifleftchildislargerthanroot if(lefta[largest]) largest=left; //Ifrightchildislargerthanroot if(righta[largest]) largest=right; //Ifrootisnotlargest if(largest!=i){ //swapa[i]witha[largest] inttemp=a[i]; a[i]=a[largest]; a[largest]=temp; heapify(a,n,largest); } } /*Functiontoimplementtheheapsort*/ voidheapSort(inta[],intn) { for(inti=n/2-1;i>=0;i--) heapify(a,n,i); //Onebyoneextractanelementfromheap for(inti=n-1;i>=0;i--){ /*Movecurrentrootelementtoend*/ //swapa[0]witha[i] inttemp=a[0]; a[0]=a[i]; a[i]=temp; heapify(a,i,0); } } /*functiontoprintthearrayelements*/ voidprintArr(intarr[],intn) { for(inti=0;i usingnamespacestd; /*functiontoheapifyasubtree.Here'i'isthe indexofrootnodeinarraya[],and'n'isthesizeofheap.*/ voidheapify(inta[],intn,inti) { intlargest=i;//Initializelargestasroot intleft=2*i+1;//leftchild intright=2*i+2;//rightchild //Ifleftchildislargerthanroot if(lefta[largest]) largest=left; //Ifrightchildislargerthanroot if(righta[largest]) largest=right; //Ifrootisnotlargest if(largest!=i){ //swapa[i]witha[largest] inttemp=a[i]; a[i]=a[largest]; a[largest]=temp; heapify(a,n,largest); } } /*Functiontoimplementtheheapsort*/ voidheapSort(inta[],intn) { for(inti=n/2-1;i>=0;i--) heapify(a,n,i); //Onebyoneextractanelementfromheap for(inti=n-1;i>=0;i--){ /*Movecurrentrootelementtoend*/ //swapa[0]witha[i] inttemp=a[0]; a[0]=a[i]; a[i]=temp; heapify(a,i,0); } } /*functiontoprintthearrayelements*/ voidprintArr(inta[],intn) { for(inti=0;ia[largest]) largest=left; //Ifrightchildislargerthanroot if(righta[largest]) largest=right; //Ifrootisnotlargest if(largest!=i){ //swapa[i]witha[largest] inttemp=a[i]; a[i]=a[largest]; a[largest]=temp; heapify(a,n,largest); } } /*Functiontoimplementtheheapsort*/ staticvoidheapSort(int[]a,intn) { for(inti=n/2-1;i>=0;i--) heapify(a,n,i); //Onebyoneextractanelementfromheap for(inti=n-1;i>=0;i--){ /*Movecurrentrootelementtoend*/ //swapa[0]witha[i] inttemp=a[0]; a[0]=a[i]; a[i]=temp; heapify(a,i,0); } } /*functiontoprintthearrayelements*/ staticvoidprintArr(int[]a,intn) { for(inti=0;ia[largest]) largest=left; //Ifrightchildislargerthanroot if(righta[largest]) largest=right; //Ifrootisnotlargest if(largest!=i){ //swapa[i]witha[largest] inttemp=a[i]; a[i]=a[largest]; a[largest]=temp; heapify(a,n,largest); } } /*Functiontoimplementtheheapsort*/ staticvoidheapSort(inta[],intn) { for(inti=n/2-1;i>=0;i--) heapify(a,n,i); //Onebyoneextractanelementfromheap for(inti=n-1;i>=0;i--){ /*Movecurrentrootelementtoend*/ //swapa[0]witha[i] inttemp=a[0]; a[0]=a[i]; a[i]=temp; heapify(a,i,0); } } /*functiontoprintthearrayelements*/ staticvoidprintArr(inta[],intn) { for(inti=0;i