{"id":97789,"date":"2021-07-03T09:00:46","date_gmt":"2021-07-03T03:30:46","guid":{"rendered":"https:\/\/data-flair.training\/blogs\/?p=97789"},"modified":"2021-06-26T22:06:07","modified_gmt":"2021-06-26T16:36:07","slug":"heapsort","status":"publish","type":"post","link":"https:\/\/data-flair.training\/blogs\/heapsort\/","title":{"rendered":"Heapsort in Data Structure"},"content":{"rendered":"<p>There is a long queue at the billing counter of a mall. Some people have put all of their groceries in the cart and some have only 8-10 items. You have only a packet of chips and bread. Suppose you are in the 10th position in the queue, you could have to wait a long time for your billing. But what if the billing counter bills the persons who will require the least amount of time first. You will be billed first followed by some people with a small number of items and people with the largest number of items will be billed last.<\/p>\n<p>This is how a heap sort works. It is the fastest way to find the smallest or largest element in a dataset.<\/p>\n<h3>Heapsort in Data Structure<\/h3>\n<p>Heap sort works by creating a min-heap or max-heap out of the elements provided in a dataset. Ordering of the dataset in which root element represents the minimum or maximum element is represented by min heap and max heap. Heapsort is similar to selection sort, where the smallest element is found and is put at the first position.<\/p>\n<h3>Binary heap<\/h3>\n<p>A binary tree is complete if all the levels are completely filled except possibly the last level and the last level has all keys as left as possible. This is known as a complete binary tree.<\/p>\n<p>A binary heap is a complete binary tree with the following properties :<\/p>\n<ul>\n<li>In a min-heap, the root node must be minimum among all keys present in the binary heap. This is true for all nodes in the binary tree.<\/li>\n<li>In a max heap, the root node must be maximum among all keys present in the binary heap. This is true for all nodes in the binary tree.<\/li>\n<\/ul>\n<p>A binary heap is a complete binary tree. Therefore, it can be easily represented as an array since arrays are space-efficient. If the parent node is stored at index I, the left child is at <strong>2 * I + 1<\/strong>, and the right child is at <strong>2 * I + 2<\/strong>.<\/p>\n<h3>Procedure for Heapsort<\/h3>\n<p>Procedure for sorting an array in ascending order:<\/p>\n<p>1. Create a max heap from an input dataset<\/p>\n<p>2. Replace the largest element at the root with the last item of the heap. Reduce the size of the heap by 1.<\/p>\n<p>3. Heapify the root of the tree.<\/p>\n<p>4. Repeat steps 2 and 3 while the size of the heap is greater than 1<\/p>\n<h3>Heapsort Algorithm<\/h3>\n<p>HEAP_SORT(Array, N)<\/p>\n<p>Step 1: [Building heap H]<\/p>\n<p>for i=0 to N-1<\/p>\n<p>INSERTHEAP(Aeray, N, Array[i])<br \/>\n[END OF for]<\/p>\n<p>Step 2: Repeatedly Delete the root element<br \/>\nwhile N &gt; 0<br \/>\nDeleteHeap(Array,N,value)<br \/>\nN = N+1<\/p>\n<p>[END OF while]<br \/>\nStep 3: stop<\/p>\n<h3>Working of heapsort<\/h3>\n<p>Let us try to sort the following array using the heap sort technique<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images01.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97826\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images01.jpg\" alt=\"Heapsort Example\" width=\"328\" height=\"74\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images01.jpg 328w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images01-320x72.jpg 320w\" sizes=\"auto, (max-width: 328px) 100vw, 328px\" \/><\/a><\/p>\n<p>1: create a tree with the elements of the array<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images02.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97827\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images02.jpg\" alt=\"Heap Sort Iteration 1\" width=\"327\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images02.jpg 327w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images02-320x251.jpg 320w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/a><\/p>\n<p>2: Convert the tree to max heap<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images03.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97828\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images03.jpg\" alt=\"Max Heap\" width=\"327\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images03.jpg 327w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images03-320x251.jpg 320w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/a><\/p>\n<p>3: swap the root with the last element of the heap.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images04.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97829\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images04.jpg\" alt=\"Heapsort\" width=\"327\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images04.jpg 327w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images04-320x251.jpg 320w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/a><\/p>\n<p>4: Heapify and repeat.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images05.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97830\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images05.jpg\" alt=\"Heapify\" width=\"327\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images05.jpg 327w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images05-320x251.jpg 320w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/a><\/p>\n<p>5:<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images06.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97831\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images06.jpg\" alt=\"Heap sort\" width=\"327\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images06.jpg 327w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images06-320x251.jpg 320w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/a><\/p>\n<p>6: Heapify the above heap.<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images07.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97833\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images07.jpg\" alt=\"Heapsort working\" width=\"327\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images07.jpg 327w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images07-320x251.jpg 320w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p>7:<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images08.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97832\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images08.jpg\" alt=\"Heap sort\" width=\"327\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images08.jpg 327w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images08-320x251.jpg 320w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/a><\/p>\n<p>8:<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images09.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97834\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images09.jpg\" alt=\"heapsort\" width=\"327\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images09.jpg 327w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images09-320x251.jpg 320w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/a><\/p>\n<p>9:<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images10.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97835\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images10.jpg\" alt=\"Heapify\" width=\"327\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images10.jpg 327w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images10-320x251.jpg 320w\" sizes=\"auto, (max-width: 327px) 100vw, 327px\" \/><\/a><\/p>\n<p>10:<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images11.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97836\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images11.jpg\" alt=\"Heap sort\" width=\"392\" height=\"257\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images11.jpg 392w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images11-320x210.jpg 320w\" sizes=\"auto, (max-width: 392px) 100vw, 392px\" \/><\/a><\/p>\n<p>11:<\/p>\n<p><a href=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images12.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-97837\" src=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images12.jpg\" alt=\"Heap sort\" width=\"328\" height=\"74\" srcset=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images12.jpg 328w, https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-normal-images12-320x72.jpg 320w\" sizes=\"auto, (max-width: 328px) 100vw, 328px\" \/><\/a><\/p>\n<p>Heap is <strong>not<\/strong> a stable sorting algorithm.<\/p>\n<h3>Implementation of Heapsort in C<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;stdio.h&gt;\r\n\r\n  void swap(int *x, int *y) \r\n  {\r\n    int temp = *x;\r\n    *x = *y;\r\n    *y = temp;\r\n  }\r\n  \r\n  void heapify(int arr[], int size, int i) \r\n  {\r\n    int largest = i;\r\n    int low = 2 * i + 1;\r\n    int high = 2 * i + 2;\r\n  \r\n    if (low &lt; size &amp;&amp; arr[low] &gt; arr[largest])\r\n      largest = low;\r\n  \r\n    if (high &lt; size &amp;&amp; arr[high] &gt; arr[largest])\r\n      largest = high;\r\n  \r\n    if (largest != i) \r\n    {\r\n      swap(&amp;arr[i], &amp;arr[largest]);\r\n      heapify(arr, size, largest);\r\n    }\r\n  }\r\n  \r\n  void heapSort(int arr[], int n) \r\n  {\r\n    for (int i = n \/ 2 - 1; i &gt;= 0; i--)\r\n      heapify(arr, n, i);\r\n      \r\n    for (int i = n - 1; i &gt;= 0; i--) \r\n    {\r\n      swap(&amp;arr[0], &amp;arr[i]);\r\n      heapify(arr, i, 0);\r\n    }\r\n  }\r\n  \r\n  int main() \r\n  {\r\n    int array[] = {54, 12, 9, 35, 26, 40,100,73,81,66};\r\n    int size = sizeof(array) \/ sizeof(array[0]);\r\n  \r\n    heapSort(array, size);\r\n  \r\n    printf(\"Sorted array: \\n\");\r\n    for (int i = 0; i &lt; size; ++i)\r\n      printf(\"%d \", array[i]);\r\n  }\r\n<\/pre>\n<h3>Heapsort Implementation in C++<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;iostream&gt;\r\nusing namespace std;\r\n\r\n  void swap(int *x, int *y) \r\n  {\r\n    int temp = *x;\r\n    *x = *y;\r\n    *y = temp;\r\n  }\r\n  \r\n  void heapify(int arr[], int size, int i) \r\n  {\r\n    int largest = i;\r\n    int low = 2 * i + 1;\r\n    int high = 2 * i + 2;\r\n  \r\n    if (low &lt; size &amp;&amp; arr[low] &gt; arr[largest])\r\n      largest = low;\r\n  \r\n    if (high &lt; size &amp;&amp; arr[high] &gt; arr[largest])\r\n      largest = high;\r\n  \r\n    if (largest != i) \r\n    {\r\n      swap(&amp;arr[i], &amp;arr[largest]);\r\n      heapify(arr, size, largest);\r\n    }\r\n  }\r\n  \r\n  void heapSort(int arr[], int n) \r\n  {\r\n    for (int i = n \/ 2 - 1; i &gt;= 0; i--)\r\n      heapify(arr, n, i);\r\n      \r\n    for (int i = n - 1; i &gt;= 0; i--) \r\n    {\r\n      swap(&amp;arr[0], &amp;arr[i]);\r\n      heapify(arr, i, 0);\r\n    }\r\n  }\r\n  \r\n  int main() \r\n  {\r\n    int array[] = {54, 12, 9, 35, 26, 40,100,73,81,66};\r\n    int size = sizeof(array) \/ sizeof(array[0]);\r\n  \r\n    heapSort(array, size);\r\n  \r\n    cout &lt;&lt; \"Sorted array:\";\r\n    for (int i = 0; i &lt; size; ++i)\r\n      cout &lt;&lt; \" \" &lt;&lt; array[i];\r\n  }\r\n<\/pre>\n<h3>Heapsort Implementation in Java<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">public class HeapSort \r\n{\r\n    public void sort(int array[]) \r\n    {\r\n      int size = array.length;\r\n      \r\n      for (int i = size \/ 2 - 1; i &gt;= 0; i--) \r\n      {\r\n        heapify(array, size, i);\r\n      }\r\n      \r\n      for (int i = size - 1; i &gt;= 0; i--) \r\n      {\r\n        int temp = array[0];\r\n        array[0] = array[i];\r\n        array[i] = temp;\r\n  \r\n        heapify(array, i, 0);\r\n      }\r\n    }\r\n  \r\n    void heapify(int arr[], int n, int i) \r\n    {\r\n      int largest = i;\r\n      int low = 2 * i + 1;\r\n      int high = 2 * i + 2;\r\n  \r\n      if (low &lt; n &amp;&amp; arr[low] &gt; arr[largest])\r\n        largest = low;\r\n  \r\n      if (high &lt; n &amp;&amp; arr[high] &gt; arr[largest])\r\n        largest = high;\r\n        \r\n      if (largest != i) \r\n      {\r\n        int swap = arr[i];\r\n        arr[i] = arr[largest];\r\n        arr[largest] = swap;\r\n  \r\n        heapify(arr, n, largest);\r\n      }\r\n    }\r\n  \r\n  \r\n    public static void main(String args[])\r\n    {\r\n      int arr[] = { 54, 12, 9, 35, 26, 40,100,73,81,66 };\r\n  \r\n      HeapSort hs = new HeapSort();\r\n      hs.sort(arr);\r\n  \r\n      System.out.println(\"Sorted array:\");\r\n      int n = arr.length;\r\n      for (int i = 0; i &lt; n; ++i)\r\n        System.out.print(arr[i] + \" \");\r\n    }\r\n  }\r\n<\/pre>\n<h3>Implementation of Heapsort in Python<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">def heapify(arr, n, i):\r\n    \r\n      largest = i\r\n      low = 2 * i + 1\r\n      high = 2 * i + 2\r\n  \r\n      if low &lt; n and arr[i] &lt; arr[low]:\r\n          largest = low\r\n  \r\n      if high &lt; n and arr[largest] &lt; arr[high]:\r\n          largest = high\r\n  \r\n      if largest != i:\r\n          arr[i], arr[largest] = arr[largest], arr[i]\r\n          heapify(arr, n, largest)\r\n  \r\n  \r\ndef heapSort(arr):\r\n      size = len(arr)\r\n  \r\n      for i in range(size\/\/2, -1, -1):\r\n          heapify(arr, size, i)\r\n  \r\n      for i in range(size-1, 0, -1):\r\n          arr[i], arr[0] = arr[0], arr[i]\r\n          heapify(arr, i, 0)\r\n  \r\n  \r\narr = [54, 12, 9, 35, 26, 40,100,73,81,66]\r\nheapSort(arr)\r\nn = len(arr)\r\nprint(\"Sorted array:\")\r\nfor i in range(n):\r\n    print(\"%d \" % arr[i], end='')\r\n<\/pre>\n<h3>Complexity of Heapsort<\/h3>\n<p><strong>Best case complexity:<\/strong> when the pivot element is the middle element or near to the middle element.<\/p>\n<p><strong>Worst-case complexity:<\/strong> when pivot element is either largest or smallest number.<\/p>\n<p><strong>Average case complexity:<\/strong> when the condition of best and worst-case, both don\u2019t occur.<\/p>\n<table style=\"height: 200px;\" width=\"620\">\n<tbody>\n<tr>\n<td><b>Scenario<\/b><\/td>\n<td><b>Complexity<\/b><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">Worst case<\/span><\/td>\n<td><span style=\"font-weight: 400;\">O(n log n)<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">Average case<\/span><\/td>\n<td><span style=\"font-weight: 400;\">O(n log n)<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">Best case<\/span><\/td>\n<td><span style=\"font-weight: 400;\">O(n log n)<\/span><\/td>\n<\/tr>\n<tr>\n<td><span style=\"font-weight: 400;\">space<\/span><\/td>\n<td><span style=\"font-weight: 400;\">O(1)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<h3>Applications of heapsort<\/h3>\n<p>Although heapsort has limited applications since quicksort and mergesort techniques are much better, it has some eminent applications.<\/p>\n<p>1. Heapsort is used in the Linux kernel because of its O(1) space complexity and O(n log n) time complexity.<\/p>\n<p>2. Heap sort returns the largest or smallest element in the dataset in the fastest time. It is used in places that need minimum or maximum elements without requiring the rest of the dataset to be sorted. For example, priority queues.<\/p>\n<h3>Conclusion<\/h3>\n<p>The heap sort technique is based on the binary tree data structure. We will study binary trees in detail in future articles. Max heap and min heap are created for sorting in ascending or descending order respectively. There are some other sorting techniques also that we have not covered since these are the few often used techniques. With this article, we end our topic for sorting techniques.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>There is a long queue at the billing counter of a mall. Some people have put all of their groceries in the cart and some have only 8-10 items. You have only a packet&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":97825,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[24020],"tags":[24684,24685,24688,24689,24687,24686],"class_list":["post-97789","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure-tutorials","tag-heapsort","tag-heapsort-algorithm","tag-heapsort-applications","tag-heapsort-implementation","tag-heapsort-pseudocode","tag-heapsort-working"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v28.0 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Heapsort in Data Structure - DataFlair<\/title>\n<meta name=\"description\" content=\"Learn about heap sort technique which is based on the binary tree data structure. Learn its algorithm, working, Complexity and Applications.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/data-flair.training\/blogs\/heapsort\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Heapsort in Data Structure - DataFlair\" \/>\n<meta property=\"og:description\" content=\"Learn about heap sort technique which is based on the binary tree data structure. Learn its algorithm, working, Complexity and Applications.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/data-flair.training\/blogs\/heapsort\/\" \/>\n<meta property=\"og:site_name\" content=\"DataFlair\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/DataFlairWS\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-07-03T03:30:46+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-in-DS.jpg\" \/>\n\t<meta property=\"og:image:width\" content=\"1200\" \/>\n\t<meta property=\"og:image:height\" content=\"628\" \/>\n\t<meta property=\"og:image:type\" content=\"image\/jpeg\" \/>\n<meta name=\"author\" content=\"DataFlair Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:site\" content=\"@DataFlairWS\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"DataFlair Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"9 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Heapsort in Data Structure - DataFlair","description":"Learn about heap sort technique which is based on the binary tree data structure. Learn its algorithm, working, Complexity and Applications.","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/data-flair.training\/blogs\/heapsort\/","og_locale":"en_US","og_type":"article","og_title":"Heapsort in Data Structure - DataFlair","og_description":"Learn about heap sort technique which is based on the binary tree data structure. Learn its algorithm, working, Complexity and Applications.","og_url":"https:\/\/data-flair.training\/blogs\/heapsort\/","og_site_name":"DataFlair","article_publisher":"https:\/\/www.facebook.com\/DataFlairWS\/","article_published_time":"2021-07-03T03:30:46+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-in-DS.jpg","type":"image\/jpeg"}],"author":"DataFlair Team","twitter_card":"summary_large_image","twitter_creator":"@DataFlairWS","twitter_site":"@DataFlairWS","twitter_misc":{"Written by":"DataFlair Team","Est. reading time":"9 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/data-flair.training\/blogs\/heapsort\/#article","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/heapsort\/"},"author":{"name":"DataFlair Team","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9"},"headline":"Heapsort in Data Structure","datePublished":"2021-07-03T03:30:46+00:00","mainEntityOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/heapsort\/"},"wordCount":730,"commentCount":0,"publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/heapsort\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-in-DS.jpg","keywords":["Heapsort","Heapsort algorithm","Heapsort Applications","Heapsort Implementation","Heapsort Pseudocode","Heapsort working"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/data-flair.training\/blogs\/heapsort\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/data-flair.training\/blogs\/heapsort\/","url":"https:\/\/data-flair.training\/blogs\/heapsort\/","name":"Heapsort in Data Structure - DataFlair","isPartOf":{"@id":"https:\/\/data-flair.training\/blogs\/#website"},"primaryImageOfPage":{"@id":"https:\/\/data-flair.training\/blogs\/heapsort\/#primaryimage"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/heapsort\/#primaryimage"},"thumbnailUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-in-DS.jpg","datePublished":"2021-07-03T03:30:46+00:00","description":"Learn about heap sort technique which is based on the binary tree data structure. Learn its algorithm, working, Complexity and Applications.","breadcrumb":{"@id":"https:\/\/data-flair.training\/blogs\/heapsort\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/data-flair.training\/blogs\/heapsort\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/heapsort\/#primaryimage","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-in-DS.jpg","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2021\/06\/Heap-sort-in-DS.jpg","width":1200,"height":628,"caption":"Heapsort in DS"},{"@type":"BreadcrumbList","@id":"https:\/\/data-flair.training\/blogs\/heapsort\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Blog Home","item":"https:\/\/data-flair.training\/blogs\/"},{"@type":"ListItem","position":2,"name":"Data Structure Tutorials","item":"https:\/\/data-flair.training\/blogs\/category\/data-structure-tutorials\/"},{"@type":"ListItem","position":3,"name":"Heapsort in Data Structure"}]},{"@type":"WebSite","@id":"https:\/\/data-flair.training\/blogs\/#website","url":"https:\/\/data-flair.training\/blogs\/","name":"DataFlair","description":"Learn Today. Lead Tomorrow.","publisher":{"@id":"https:\/\/data-flair.training\/blogs\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/data-flair.training\/blogs\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/data-flair.training\/blogs\/#organization","name":"DataFlair","url":"https:\/\/data-flair.training\/blogs\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/","url":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","contentUrl":"https:\/\/data-flair.training\/blogs\/wp-content\/uploads\/sites\/2\/2016\/07\/Data-Flair.png","width":106,"height":48,"caption":"DataFlair"},"image":{"@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/DataFlairWS\/","https:\/\/x.com\/DataFlairWS","https:\/\/www.linkedin.com\/company\/dataflair-web-services-pvt-ltd\/","https:\/\/www.youtube.com\/user\/DataFlairWS"]},{"@type":"Person","@id":"https:\/\/data-flair.training\/blogs\/#\/schema\/person\/b49855299264df5e27e3ec6c2cd9fde9","name":"DataFlair Team","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","contentUrl":"https:\/\/secure.gravatar.com\/avatar\/ef46b745ddad2fad690af626c6ef29b91809ad0a9f5ef398d07817d8cad042f5?s=96&d=mm&r=g","caption":"DataFlair Team"},"description":"DataFlair Team is a group of passionate educators and industry experts dedicated to providing high-quality online learning resources on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. With years of experience in the field, the team aims to simplify complex topics and help learners advance their careers. At DataFlair, we believe in empowering students and professionals with the knowledge and skills needed to thrive in today\u2019s fast-paced tech industry. Follow us for Free courses, expert insights, tutorials, and practical tips to boost your learning journey.","url":"https:\/\/data-flair.training\/blogs\/author\/datafbdad\/"}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/97789","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/comments?post=97789"}],"version-history":[{"count":3,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/97789\/revisions"}],"predecessor-version":[{"id":97838,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/posts\/97789\/revisions\/97838"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media\/97825"}],"wp:attachment":[{"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/media?parent=97789"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/categories?post=97789"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/data-flair.training\/blogs\/wp-json\/wp\/v2\/tags?post=97789"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}