{"id":84249,"date":"2019-08-08T17:34:33","date_gmt":"2019-08-08T17:34:33","guid":{"rendered":"https:\/\/www.softwaretestinghelp.com\/?page_id=84249"},"modified":"2025-04-01T08:11:02","modified_gmt":"2025-04-01T08:11:02","slug":"heap-sort","status":"publish","type":"page","link":"https:\/\/www.softwaretestinghelp.com\/heap-sort\/","title":{"rendered":"Heap Sort In C++ With Examples"},"content":{"rendered":"<p><strong>An Introduction To Heap Sort With Examples.<\/strong><\/p>\n<p>Heapsort is one of the most efficient sorting techniques. This technique builds a heap from the given unsorted array and then uses the heap again to sort the array.<\/p>\n<p>Heapsort is a sorting technique based on comparison and uses binary heap.<\/p>\n<p>=&gt; <a href=\"https:\/\/www.softwaretestinghelp.com\/cpp-tutorials\/\"><strong>Read Through The Easy C++ Training Series.<\/strong><\/a><\/p>\n<p><em><strong> <\/strong><\/em><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Heap-Sort-1.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84510\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Heap-Sort-1.png\" alt=\"Heap Sort (1)\" width=\"650\" height=\"366\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Heap-Sort-1.png 650w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Heap-Sort-1-300x169.png 300w\" sizes=\"(max-width: 650px) 100vw, 650px\" \/><\/a><\/p>\n<h3>What Is A Binary Heap?<\/h3>\n<p>A binary heap is represented using a complete binary tree. A complete binary tree is a binary tree in which all the nodes at each level are completely filled except for the leaf nodes and the nodes are as far as left.<\/p>\n<p>A binary heap or simply a heap is a complete binary tree where the items or nodes are stored in a way such that the root node is greater than its two child nodes. This is also called max heap.<\/p>\n<p>The items in the binary heap can also be stored as min-heap wherein the root node is smaller than its two child nodes. We can represent a heap as a binary tree or an array.<\/p>\n<p>While representing a heap as an array, assuming the index starts at 0, the root element is stored at 0. In general, if a parent node is at the position I, then the left child node is at the position (2*I + 1) and the right node is at (2*I +2).<\/p>\n<h3>General Algorithm<\/h3>\n<p><strong>Given below is the general algorithm for heap sort technique.<\/strong><\/p>\n<ul>\n<li>Build a max heap from the given data such that the root is the highest element of the heap.<\/li>\n<li>Remove the root i.e. the highest element from the heap and replace or swap it\u00a0with the last element of the heap.<\/li>\n<li>Then adjust the max heap, so as to not to violate the max heap properties (heapify).<\/li>\n<li>The above step reduces the heap size by 1.<\/li>\n<li>Repeat the above three steps until the heap size is reduced to 1.<\/li>\n<\/ul>\n<p>As shown in the general algorithm to sort the given dataset in increasing order, we first construct a max heap for the given data.<\/p>\n<p><span style=\"text-decoration: underline;\"><strong>Let us take an example to construct a max heap with the following dataset.<\/strong><\/span><\/p>\n<p>6, 10, 2, 4, 1<\/p>\n<p><strong>We can construct a tree for this data set as follows.<\/strong><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/construct-a-tree.png\"><img decoding=\"async\" class=\"alignnone wp-image-84330 size-full\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/construct-a-tree.png\" alt=\"construct a tree - HEAP SORT\" width=\"336\" height=\"216\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/construct-a-tree.png 336w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/construct-a-tree-300x193.png 300w\" sizes=\"(max-width: 336px) 100vw, 336px\" \/><\/a><\/p>\n<p>In the above tree representation, the numbers in the brackets represent the respective positions in the array.<\/p>\n<p>In order to construct a max heap of the above representation, we need to fulfill the heap condition that the parent node should be greater than its child nodes. In other words, we need to \u201cheapify\u201d the tree so as to convert it to max-heap.<\/p>\n<p><strong>After heapification of the above tree, we will get the max-heap as shown below.<\/strong><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/max-heap.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84331\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/max-heap.png\" alt=\"max-heap\" width=\"685\" height=\"232\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/max-heap.png 685w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/max-heap-300x102.png 300w\" sizes=\"(max-width: 685px) 100vw, 685px\" \/><\/a><\/p>\n<p>As shown above, we have this max-heap generated from an array.<\/p>\n<p>Next, we present an illustration of a heap sort. Having seen the construction of max-heap, we will skip the detailed steps to construct a max-heap and will directly show the max heap at each step.<\/p>\n<h3><strong>Illustration<\/strong><\/h3>\n<p>Consider the following array of elements. We need to sort this array using the heap sort technique.<\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Illustration-array.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84332\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Illustration-array.png\" alt=\"Illustration array\" width=\"351\" height=\"86\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Illustration-array.png 351w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Illustration-array-300x74.png 300w\" sizes=\"(max-width: 351px) 100vw, 351px\" \/><\/a><\/p>\n<p><strong>Let us construct a max-heap as shown below for the array to be sorted.<\/strong><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/a-max-heap.png\"><img decoding=\"async\" class=\"alignnone wp-image-84333 size-full\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/a-max-heap.png\" alt=\"a max-heap EXAMPLE\" width=\"354\" height=\"229\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/a-max-heap.png 354w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/a-max-heap-300x194.png 300w\" sizes=\"(max-width: 354px) 100vw, 354px\" \/><\/a><\/p>\n<p><strong>Once the heap is constructed, we represent it in an Array form as shown below.<\/strong><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/array-form-of-heap.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84334\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/array-form-of-heap.png\" alt=\"array form of heap\" width=\"383\" height=\"136\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/array-form-of-heap.png 383w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/array-form-of-heap-300x107.png 300w\" sizes=\"(max-width: 383px) 100vw, 383px\" \/><\/a><\/p>\n<p>Now we compare the 1<sup>st<\/sup> node (root) with the last node and then swap them. Thus, as shown above, we swap 17 and 3 so that 17 is at the last position and 3 is in the first position.<\/p>\n<p>Now we remove the node 17 from the heap and put it in the sorted array as shown in the shaded portion below.<\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/remove-the-node-17.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84335\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/remove-the-node-17.png\" alt=\"remove the node 17\" width=\"541\" height=\"145\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/remove-the-node-17.png 541w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/remove-the-node-17-300x80.png 300w\" sizes=\"(max-width: 541px) 100vw, 541px\" \/><\/a><\/p>\n<p>Now we again construct a heap for the array elements. This time the heap size is reduced by 1 as we have deleted one element (17) from the heap.<\/p>\n<p><strong> The heap of the remaining elements is shown below.<\/strong><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/deleted-one-element-17-from-the-heap.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84336\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/deleted-one-element-17-from-the-heap.png\" alt=\"deleted one element (17) from the heap\" width=\"380\" height=\"283\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/deleted-one-element-17-from-the-heap.png 380w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/deleted-one-element-17-from-the-heap-300x223.png 300w\" sizes=\"(max-width: 380px) 100vw, 380px\" \/><\/a><\/p>\n<p>In the next step, we will repeat the same steps.<\/p>\n<p><strong>We compare and swap the root element and last element in the heap.<\/strong><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-the-root-element-and-last-element-in-the-heap.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84337\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-the-root-element-and-last-element-in-the-heap.png\" alt=\"swap the root element and last element in the heap\" width=\"370\" height=\"141\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-the-root-element-and-last-element-in-the-heap.png 370w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-the-root-element-and-last-element-in-the-heap-300x114.png 300w\" sizes=\"(max-width: 370px) 100vw, 370px\" \/><\/a><\/p>\n<p>After swapping, we delete the element 12 from the heap and shift it to the sorted array.<\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-the-element-12.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84338\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-the-element-12.png\" alt=\"delete the element 12\" width=\"352\" height=\"81\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-the-element-12.png 352w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-the-element-12-300x69.png 300w\" sizes=\"(max-width: 352px) 100vw, 352px\" \/><\/a><\/p>\n<p>Once again we construct a max heap for the remaining elements as shown below.<\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/we-construct-a-max-heap-for-the-remaining-elements.png\"><img decoding=\"async\" class=\"alignnone wp-image-84339 size-full\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/we-construct-a-max-heap-for-the-remaining-elements.png\" alt=\"again construct a max-heap\" width=\"297\" height=\"288\" \/><\/a><\/p>\n<p>Now we swap the root and the last element i.e. 9 and 3. After swapping, element 9 is deleted from the heap and put in a sorted array.<\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-9-and-3-and-9-is-deleted-from-the-heap.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84340\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-9-and-3-and-9-is-deleted-from-the-heap.png\" alt=\"swap 9 and 3 and 9 is deleted from the heap\" width=\"388\" height=\"234\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-9-and-3-and-9-is-deleted-from-the-heap.png 388w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-9-and-3-and-9-is-deleted-from-the-heap-300x181.png 300w\" sizes=\"(max-width: 388px) 100vw, 388px\" \/><\/a><\/p>\n<p>At this point, we have only three elements in the heap as shown below.<\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/three-elements-in-the-heap.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84341\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/three-elements-in-the-heap.png\" alt=\"three elements in the heap\" width=\"250\" height=\"189\" \/><\/a><\/p>\n<p>We swap 6 and 3 and delete the element 6 from the heap and add it to the sorted array.<\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-6-and-3.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84342\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-6-and-3.png\" alt=\"swap 6 and 3\" width=\"350\" height=\"115\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-6-and-3.png 350w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swap-6-and-3-300x99.png 300w\" sizes=\"(max-width: 350px) 100vw, 350px\" \/><\/a><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-element-6-from-the-heap.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84343\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-element-6-from-the-heap.png\" alt=\"delete element 6 from the heap\" width=\"352\" height=\"79\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-element-6-from-the-heap.png 352w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-element-6-from-the-heap-300x67.png 300w\" sizes=\"(max-width: 352px) 100vw, 352px\" \/><\/a><\/p>\n<p>Now we construct a heap of the remaining elements and then swap both with each other.<\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/construct-a-heap-of-the-remaining-elements.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84344\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/construct-a-heap-of-the-remaining-elements.png\" alt=\"construct a heap of the remaining elements\" width=\"184\" height=\"190\" \/><\/a><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swapping-4-and-3.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84346\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swapping-4-and-3.png\" alt=\"swapping 4 and 3\" width=\"361\" height=\"136\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swapping-4-and-3.png 361w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/swapping-4-and-3-300x113.png 300w\" sizes=\"(max-width: 361px) 100vw, 361px\" \/><\/a><\/p>\n<p>After swapping 4 and 3, we delete element 4 from the heap and add it to the sorted array. Now we have only one node remaining in the heap as shown below<strong>.<\/strong><\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-element-4-from-the-heap.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84347\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/delete-element-4-from-the-heap.png\" alt=\"delete element 4 from the heap\" width=\"75\" height=\"74\" \/><\/a><\/p>\n<p>So now with only one node remaining, we delete it from the heap and add it to the sorted array.<\/p>\n<p><a href=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Sorted-Array.png\"><img decoding=\"async\" class=\"alignnone size-full wp-image-84348\" src=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Sorted-Array.png\" alt=\"Sorted Array\" width=\"501\" height=\"82\" srcset=\"https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Sorted-Array.png 501w, https:\/\/www.softwaretestinghelp.com\/wp-content\/qa\/uploads\/2019\/06\/Sorted-Array-300x49.png 300w\" sizes=\"(max-width: 501px) 100vw, 501px\" \/><\/a><\/p>\n<p>Thus the above shown is the sorted array that we have obtained as a result of the heap sort.<\/p>\n<p>In the above illustration, we have sorted the array in ascending order. If we have to sort the array in descending order then we need to follow the same steps but with the min-heap.<\/p>\n<p>Heapsort algorithm is identical to selection sort in which we select the smallest element and place it into a sorted array. However, heap sort is faster than selection sort as far as the performance is concerned. We can put it as heapsort is an improved version of the selection sort.<\/p>\n<p>Next, we will implement Heapsort in C++ and Java language.<\/p>\n<p><strong>Recommended Reading =&gt; <a href=\"https:\/\/www.softwaretestinghelp.com\/stack-vs-heap\/\">Stack vs Heap &#8211; Know the Differences<\/a><\/strong><\/p>\n<p>The most important function in both the implementations is the function \u201cheapify\u201d. This function is called by the main heapsort routine to rearrange the subtree once a node is deleted or when max-heap is built.<\/p>\n<p>When we have heapified the tree correctly, only then we will be able to get the correct elements in their proper positions and thus the array will be correctly sorted.<\/p>\n<h3>C++ Example<\/h3>\n<p><strong>Following is the C++ code for heapsort implementation.<\/strong><\/p>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\r\n#include &lt;iostream&gt;\r\nusing namespace std;\r\n \r\n\/\/ function to heapify the tree\r\nvoid heapify(int arr&#x5B;], int n, int root)\r\n{\r\n   int largest = root; \/\/ root is the largest element\r\n   int l = 2*root + 1; \/\/ left = 2*root + 1\r\n   int r = 2*root + 2; \/\/ right = 2*root + 2\r\n \r\n   \/\/ If left child is larger than root\r\n   if (l &lt; n &amp;&amp; arr&#x5B;l] &gt; arr&#x5B;largest])\r\n   largest = l;\r\n \r\n   \/\/ If right child is larger than largest so far\r\n   if (r &lt; n &amp;&amp; arr&#x5B;r] &gt; arr&#x5B;largest])\r\n   largest = r;\r\n \r\n   \/\/ If largest is not root\r\n   if (largest != root)\r\n      {\r\n      \/\/swap root and largest\r\n      swap(arr&#x5B;root], arr&#x5B;largest]);\r\n \r\n      \/\/ Recursively heapify the sub-tree\r\n      heapify(arr, n, largest);\r\n      }\r\n}\r\n \r\n\/\/ implementing heap sort\r\nvoid heapSort(int arr&#x5B;], int n)\r\n{\r\n   \/\/ build heap\r\n   for (int i = n \/ 2 - 1; i &gt;= 0; i--)\r\n   heapify(arr, n, i);\r\n \r\n   \/\/ extracting elements from heap one by one\r\n   for (int i=n-1; i&gt;=0; i--)\r\n   {\r\n      \/\/ Move current root to end\r\n      swap(arr&#x5B;0], arr&#x5B;i]);\r\n \r\n      \/\/ again call max heapify on the reduced heap\r\n      heapify(arr, i, 0);\r\n   }\r\n}\r\n \r\n\/* print contents of array - utility function *\/\r\nvoid displayArray(int arr&#x5B;], int n)\r\n{\r\n   for (int i=0; i&lt;n; ++i)\r\n   cout &lt;&lt; arr&#x5B;i] &lt;&lt; &quot; &quot;;\r\n   cout &lt;&lt; &quot;\\n&quot;;\r\n}\r\n \r\n\/\/ main program\r\nint main()\r\n{\r\n   int heap_arr&#x5B;] = {4,17,3,12,9,6};\r\n   int n = sizeof(heap_arr)\/sizeof(heap_arr&#x5B;0]);\r\n   cout&lt;&lt;&quot;Input array&quot;&lt;&lt;endl;\r\n   displayArray(heap_arr,n);\r\n \r\n   heapSort(heap_arr, n);\r\n \r\n   cout &lt;&lt; &quot;Sorted array&quot;&lt;&lt;endl;\r\n   displayArray(heap_arr, n);\r\n}<\/pre>\n<p><strong>Output:<\/strong><\/p>\n<p>Input\u00a0array<\/p>\n<p>4\u00a017\u00a03\u00a012\u00a09\u00a06<\/p>\n<p>Sorted\u00a0array<\/p>\n<p>3\u00a04\u00a06\u00a09\u00a012\u00a017<\/p>\n<p>Next, we will implement the heapsort in Java language<\/p>\n<h3>Java Example<\/h3>\n<pre class=\"brush: cpp; title: ; notranslate\" title=\"\">\/\/ Java program to implement Heap Sort\r\nclass HeapSort\r\n{\r\n   public void heap_sort(int arr&#x5B;]) {\r\n      int n = arr.length;\r\n   \r\n      \/\/ Build heap (rearrange array)\r\n      for (int i = n \/ 2 - 1; i &gt;= 0; i--)\r\n      heapify(arr, n, i);\r\n \r\n      \/\/ One by one extract an element from heap\r\n      for (int i=n-1; i&gt;=0; i--) {\r\n         \/\/ Move current root to end\r\n         int temp = arr&#x5B;0];\r\n         arr&#x5B;0] = arr&#x5B;i];\r\n         arr&#x5B;i] = temp;\r\n     \r\n         \/\/ call max heapify on the reduced heap\r\n         heapify(arr, i, 0);\r\n         }\r\n       }\r\n \r\n\/\/ heapify the sub-tree\r\nvoid heapify(int arr&#x5B;], int n, int root)\r\n   {\r\n   int largest = root; \/\/ Initialize largest as root\r\n   int l = 2*root + 1; \/\/ left = 2*root + 1\r\n   int r = 2*root + 2; \/\/ right = 2*root + 2\r\n \r\n   \/\/ If left child is larger than root\r\n   if (l &lt; n &amp;&amp; arr&#x5B;l] &gt; arr&#x5B;largest])\r\n   largest = l;\r\n \r\n   \/\/ If right child is larger than largest so far\r\n   if (r &lt; n &amp;&amp; arr&#x5B;r] &gt; arr&#x5B;largest])\r\n   largest = r;\r\n \r\n   \/\/ If largest is not root\r\n   if (largest != root) {\r\n      int swap = arr&#x5B;root];\r\n      arr&#x5B;root] = arr&#x5B;largest];\r\n      arr&#x5B;largest] = swap;\r\n  \r\n      \/\/ Recursively heapify the affected sub-tree\r\n      heapify(arr, n, largest);\r\n   }\r\n}\r\n \r\n\/\/print array contents - utility function\r\nstatic void displayArray(int arr&#x5B;])\r\n   {\r\n   int n = arr.length;\r\n   for (int i=0; i&lt;n; ++i)\r\n   System.out.print(arr&#x5B;i]+&quot; &quot;);\r\n   System.out.println();\r\n   }\r\n}\r\nclass Main{\r\n   \/\/ main program\r\n   public static void main(String args&#x5B;])\r\n   {\r\n      int arr&#x5B;] = {4,17,3,12,9,6};\r\n      int n = arr.length;\r\n \r\n      HeapSort ob = new HeapSort();\r\n      System.out.println(&quot;Input array: &quot;);\r\n      HeapSort.displayArray(arr);\r\n \r\n      ob.heap_sort(arr);\r\n \r\n      System.out.println(&quot;Sorted array:&quot;);\r\n      HeapSort.displayArray(arr);\r\n   }\r\n}<\/pre>\n<p><strong>Output:<\/strong><\/p>\n<p>Input\u00a0array:<\/p>\n<p>4\u00a017\u00a03\u00a012\u00a09\u00a06<\/p>\n<p>Sorted\u00a0array:<\/p>\n<p>3\u00a04\u00a06\u00a09\u00a012\u00a017<\/p>\n<h3>Conclusion<\/h3>\n<p>Heapsort is a comparison based sorting technique using binary heap.<\/p>\n<p>It can be termed as an improvement over selection sort since both these sorting techniques work with similar logic of finding the largest or smallest element in the array repeatedly and then placing it into the sorted array.<\/p>\n<p>Heap sort makes use of max-heap or min-heap to sort the array. The first step in heap sort is to build a min or max heap from the array data and then delete the root element recursively and heapify the heap until there is only one node present in the heap.<\/p>\n<p>Heapsort is an efficient algorithm and it performs faster than selection sort. It may be used to sort an almost sorted array or find k largest or smallest elements in the array.<\/p>\n<p>With this, we have completed our topic on sorting techniques in C++. From our next tutorial onwards, we will start with data structures one by one.<\/p>\n<p>=&gt; <a href=\"https:\/\/www.softwaretestinghelp.com\/cpp-tutorials\/\"><strong>Look For The Entire C++ Training Series Here.<\/strong><\/a><\/p>\n\r\n\t\t\t<div id=\"daexthefup-container\"\r\n\t\t\t\tclass=\"daexthefup-container daexthefup-layout-stacked daexthefup-alignment-center\"\r\n\t\t\t\tdata-post-id=\"84249\">\r\n\r\n\t\t\t\t<div class=\"daexthefup-feedback\">\r\n\t\t\t\t\t<div class=\"daexthefup-text\">\r\n\t\t\t\t\t\t<h3 class=\"daexthefup-title\">Was this helpful?<\/h3>\r\n\t\t\t\t\t<\/div>\r\n\t\t\t\t\t<div class=\"daexthefup-buttons-container\">\r\n\t\t\t\t\t\t<div class=\"daexthefup-buttons\">\r\n\t\t\t\t\t\t\t\r\n\t\t\t<div class=\"daexthefup-yes daexthefup-button daexthefup-button-type-icon\" data-value=\"1\">\r\n\t\t\t\t\r\n                <svg>\r\n                    <defs>\r\n                        <style>.thumb-up-cls-1{fill:#c9c9c9;}.thumb-up-cls-2{fill:#e1e1e1;}.thumb-up-cls-3{fill:#676767;}<\/style>\r\n                    <\/defs>\r\n                    <g id=\"thumb_up\">\r\n                        <path class=\"thumb-up-cls-2 daexthefup-icon-circle\" d=\"m24,3c11.58,0,21,9.42,21,21s-9.42,21-21,21S3,35.58,3,24,12.42,3,24,3m0-1C11.85,2,2,11.85,2,24s9.85,22,22,22,22-9.85,22-22S36.15,2,24,2h0Z\" \/>\r\n                        <g>\r\n                            <rect class=\"thumb-up-cls-3 daexthefup-icon-secondary-color\" x=\"10\" y=\"20\" width=\"6\" height=\"15\" rx=\"1.5\" ry=\"1.5\" \/>\r\n                            <path class=\"thumb-up-cls-1 daexthefup-icon-primary-color\" d=\"m30.57,9.06l-.49-.1c-.81-.17-1.61.35-1.78,1.16l-5.3,11.74c-.17.81,3.16,1.61,3.97,1.78l1.96.41c.81.17,1.61-.35,1.78-1.16l2.18-10.27c.34-1.61-.7-3.21-2.31-3.56Z\" \/>\r\n                            <path class=\"thumb-up-cls-1 daexthefup-icon-primary-color\" d=\"m38.17,20h-18.67c-.83,0-1.5.67-1.5,1.5v12c0,.83.67,1.5,1.5,1.5h16.27c.71,0,1.33-.5,1.47-1.21l2.4-12c.19-.93-.53-1.8-1.47-1.8Z\" \/>\r\n                        <\/g>\r\n                    <\/g>\r\n                <\/svg>\t\t\t<\/div>\r\n\r\n\t\t\t\t\t\t\t\t\t\t\r\n\t\t\t<div class=\"daexthefup-no daexthefup-button daexthefup-button-type-icon\" data-value=\"0\">\r\n\t\t\t\t\r\n                <svg>\r\n                    <defs>\r\n                        <style>.thumb-down-cls-1{fill:#c9c9c9;}.thumb-down-cls-2{fill:#e1e1e1;}.thumb-down-cls-3{fill:#676767;}<\/style>\r\n                    <\/defs>\r\n                    <g id=\"thumb_down\">\r\n                        <path class=\"thumb-down-cls-2 daexthefup-icon-circle\" d=\"m24,3c11.58,0,21,9.42,21,21s-9.42,21-21,21S3,35.58,3,24,12.42,3,24,3m0-1C11.85,2,2,11.85,2,24s9.85,22,22,22,22-9.85,22-22S36.15,2,24,2h0Z\" \/>\r\n                        <g>\r\n                            <rect class=\"thumb-down-cls-3 daexthefup-icon-secondary-color\" x=\"10\" y=\"13\" width=\"6\" height=\"15\" rx=\"1.5\" ry=\"1.5\" \/>\r\n                            <path class=\"thumb-down-cls-1 daexthefup-icon-primary-color\" d=\"m30.57,38.94l-.49.1c-.81.17-1.61-.35-1.78-1.16l-5.3-11.74c-.17-.81,3.16-1.61,3.97-1.78l1.96-.41c.81-.17,1.61.35,1.78,1.16l2.18,10.27c.34,1.61-.7,3.21-2.31,3.56Z\" \/>\r\n                            <path class=\"thumb-down-cls-1 daexthefup-icon-primary-color\" d=\"m38.17,28h-18.67c-.83,0-1.5-.67-1.5-1.5v-12c0-.83.67-1.5,1.5-1.5h16.27c.71,0,1.33.5,1.47,1.21l2.4,12c.19.93-.53,1.8-1.47,1.8Z\" \/>\r\n                        <\/g>\r\n                    <\/g>\r\n                <\/svg>\t\t\t<\/div>\r\n\r\n\t\t\t\t\t\t\t\t\t<\/div>\r\n\t\t\t\t\t<\/div>\r\n\t\t\t\t<\/div>\r\n\r\n\t\t\t\t<div class=\"daexthefup-comment\">\r\n\t\t\t\t\t<div class=\"daexthefup-comment-top-container\">\r\n\t\t\t\t\t\t<label id=\"daexthefup-comment-label\" class=\"daexthefup-comment-label\"><\/label>\r\n\t\t\t\t\t\t\t\t\t\t\t\t\t<div class=\"daexthefup-comment-character-counter-container\">\r\n\t\t\t\t\t\t\t\t<div id=\"daexthefup-comment-character-counter-number\"\r\n\t\t\t\t\t\t\t\t\tclass=\"daexthefup-comment-character-counter-number\"><\/div>\r\n\t\t\t\t\t\t\t\t<div class=\"daexthefup-comment-character-counter-text\"><\/div>\r\n\t\t\t\t\t\t\t<\/div>\r\n\t\t\t\t\t\t\t\t\t\t\t<\/div>\r\n\t\t\t\t\t<textarea id=\"daexthefup-comment-textarea\" class=\"daexthefup-comment-textarea\"\r\n\t\t\t\t\t\t\t\tplaceholder=\"Type your message\"\r\n\t\t\t\t\t\t\t\tmaxlength=\"\r\n\t\t\t\t\t\t\t\t400\t\t\t\t\t\t\t\t\t\"><\/textarea>\r\n\t\t\t\t\t<div class=\"daexthefup-comment-buttons-container\">\r\n\t\t\t\t\t\t<button class=\"daexthefup-comment-submit daexthefup-button\">Submit<\/button>\r\n\t\t\t\t\t\t<button class=\"daexthefup-comment-cancel daexthefup-button\">Cancel<\/button>\r\n\t\t\t\t\t<\/div>\r\n\t\t\t\t<\/div>\r\n\r\n\t\t\t\t<div class=\"daexthefup-successful-submission-text\">Thanks for your feedback!<\/div>\r\n\r\n\t\t\t<\/div>\r\n\r\n\t\t\t","protected":false},"excerpt":{"rendered":"<p>An Introduction To Heap Sort With Examples. Heapsort is one of the most efficient sorting techniques. This technique builds a heap from the given unsorted array and then uses the heap again to sort the array. Heapsort is a sorting technique based on comparison and uses binary heap. =&gt; Read &#8230; <\/p>\n<p class=\"read-more-container\"><a title=\"Heap Sort In C++ With Examples\" class=\"read-more button\" href=\"https:\/\/www.softwaretestinghelp.com\/heap-sort\/#more-84249\" aria-label=\"Read more about Heap Sort In C++ With Examples\">Read more<\/a><\/p>\n","protected":false},"author":9,"featured_media":84510,"parent":0,"menu_order":0,"comment_status":"open","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_helpful_pro_status":1,"footnotes":""},"categories":[403],"tags":[],"class_list":{"0":"post-84249","1":"page","2":"type-page","3":"status-publish","4":"has-post-thumbnail","6":"category-cpp"},"acf":[],"_links":{"self":[{"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/pages\/84249","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/users\/9"}],"replies":[{"embeddable":true,"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/comments?post=84249"}],"version-history":[{"count":0,"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/pages\/84249\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/media\/84510"}],"wp:attachment":[{"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/media?parent=84249"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/categories?post=84249"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.softwaretestinghelp.com\/wp-json\/wp\/v2\/tags?post=84249"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}