{"id":83081,"date":"2021-07-31T09:00:16","date_gmt":"2021-07-31T03:30:16","guid":{"rendered":"https:\/\/techvidvan.com\/tutorials\/?p=83081"},"modified":"2021-07-31T09:00:16","modified_gmt":"2021-07-31T03:30:16","slug":"heap-sort","status":"publish","type":"post","link":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/","title":{"rendered":"Heap Sort &#8211; Algorithm, Working and Implementation"},"content":{"rendered":"<p>Heap sort is a sorting technique based upon heap data structure. It makes use of a binary heap for sorting the elements. Heapsort is a comparison-based sorting algorithm. It is an inplace sorting technique. Heapsort is not a stable algorithm.<\/p>\n<p>To implement heapsort, we make use of either min-heap or max-heap. We create a min-heap or a max-heap out of the given array elements and the root node is either the minimum or the maximum element respectively. In every iteration, we delete the root node and store it in the sorted array. Thus, the heapsort algorithm is somewhat similar to the selection sort. In selection sort as well, we used to select the minimum element and insert it into the sorted array.<\/p>\n<p>Heapsort involves mainly two steps to be performed:<\/p>\n<p>1. Building a max-heap or min-heap using the elements of the given array.<br \/>\n2. Deleting the root node of the heap formed in every iteration.<\/p>\n<h3>What is a Binary Heap?<\/h3>\n<p>A binary heap is a complete binary tree. This means that every node can have at most two elements and the elements are filled in the nodes from left to right. In a complete binary tree, we cannot move to the next node for inserting elements until the previous node is full in its capacity.<\/p>\n<p>A binary heap can be of two types:<\/p>\n<p><strong>1. Min-heap:<\/strong> In a min-heap, the value of the parent node is smaller than both of its children nodes.<\/p>\n<p><strong>2. Max-heap:<\/strong> In a max-heap, the value of the parent node is greater than both of its children nodes.<\/p>\n<p>The following diagram shows a min-heap and a max-heap respectively.<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images01.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83242\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images01.jpg\" alt=\"Max Min Heap\" width=\"872\" height=\"402\" \/><\/a><\/p>\n<h3>Why Array-based Representation for Binary Heap:<\/h3>\n<p>Array-based representation is the best for binary heap because of the following factors:<\/p>\n<ul>\n<li>Array-based representation is space-efficient.<\/li>\n<li>Heap is a complete binary tree. Hence, it is easier to represent it in the form of an array.<\/li>\n<li>If we know the index\/position of the parent node, we can easily find the position of its left and right child. If the array starts from index 0 and the parent node is at an index \u2018i\u2019, then its left child will be at the position 2*i + 1. Its right child will be at the position 2*i + 2.<\/li>\n<\/ul>\n<h3>Relationship between Array indices and Tree elements:<\/h3>\n<p>In a complete binary tree, we can easily access the left and the right child of a particular parent node using a fixed set of formulae. If the index starts from 0 and the parent node is at an index \u2018i\u2019, then its left child will be at the position <strong>2*i + 1<\/strong>. Its right child will be at the position <strong>2*i + 2<\/strong>. We can also find the parent of any node if we know the index of the child. If the index of a child node is \u2018i\u2019, then its parent will be at the index<strong> (i-1)\/2<\/strong>.<\/p>\n<p>&nbsp;<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images02-1.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83244\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images02-1.jpg\" alt=\"Heap sort in D\" width=\"872\" height=\"268\" \/><\/a><\/p>\n<p><strong>Example:<\/strong><br \/>\nLet us try to find out the left and the right child of 10. 10 is at position 2 in the heap.<br \/>\nThe left child of 10 = Index(2*i + 1) = Index(2*2+1) = Index(5) = 3<br \/>\nThe right child of 10 = Index(2*i +2) = Index(2*2+2) = Index(6) = 21<\/p>\n<p>Similarly, let\u2019s try to find the parent of 3 whose index is <strong>5<\/strong> in the array.<br \/>\nThe parent of 3 = Index((i-1)\/2) = Index((5-1)\/2) = Index(2) = 10<\/p>\n<h3>Heapify:<\/h3>\n<p>The procedure to convert a simple binary heap into a min-heap or a max-heap is defined as the <strong>Heapify<\/strong> process.<\/p>\n<h3>Procedure for Heapify:<\/h3>\n<p>The function to perform the heapify operation for a max-heap is as follows:<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">Heapify(array[], n, i):\n    largest = i;\n    left = 2 * i + 1;\n    right = 2 * i + 2;\n    if (left &lt; n) and (array[left] &gt; array[largest]):\n            largest = left;\n    if (right &lt; n) and (array[right] &gt; array[largest]):\n        largest = right;\n\n    if (largest != i):\n        swap(array[i], array[largest]);\n        Heapify(array, n, largest);\n    END if\nEND Heapify\n<\/pre>\n<h3>Working of Heap Sort:<\/h3>\n<p>Consider an array having elements: 16, 10, 15, 9, 5, 12, 14.<br \/>\nSuppose that they are arranged in a tree following the max-heap property as shown:<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images02.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83243\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images02.jpg\" alt=\"Heap sort in DS\" width=\"436\" height=\"268\" \/><\/a><\/p>\n<p>In a max-heap, the root node contains the largest element. In every step, we will pick up the element at the root node, i.e. the largest element and place it at the end of the array.<\/p>\n<p>This mainly involves three steps followed repeatedly to sort the array.<\/p>\n<p>1. Take the root node element and replace it with the last element of the heap.<\/p>\n<p>2. Remove the largest element from the heap. Decrement the size of the heap by one.<\/p>\n<p>3. Apply the heapify algorithm to make it a max-heap again.<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images03.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83245\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images03.jpg\" alt=\"Heapify Algorithm\" width=\"900\" height=\"382\" \/><\/a><\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images04.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83246\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images04.jpg\" alt=\"Heapify\" width=\"900\" height=\"344\" \/><\/a><\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images05.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83247\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images05.jpg\" alt=\"Heapify Working\" width=\"900\" height=\"344\" \/><\/a><\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images06.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83248\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images06.jpg\" alt=\"Heapify Algorithm\" width=\"900\" height=\"344\" \/><\/a><\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images07.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83249\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images07.jpg\" alt=\"Heapsort working\" width=\"1200\" height=\"477\" \/><\/a><\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images08.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83250\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images08.jpg\" alt=\"Heapsort implementation\" width=\"900\" height=\"344\" \/><\/a><\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images09.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83251\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images09.jpg\" alt=\"Heapify in DS\" width=\"900\" height=\"263\" \/><\/a><\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images10.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83252\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images10.jpg\" alt=\"Heapsort in Data Structure\" width=\"900\" height=\"263\" \/><\/a><\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images11.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83253\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images11.jpg\" alt=\"Heapsort working\" width=\"1200\" height=\"261\" \/><\/a><\/p>\n<p>Thus, the final sorted array comes out to be:<\/p>\n<p><a href=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images12.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\"aligncenter size-full wp-image-83254\" src=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/sites\/2\/2021\/07\/TV-Heap-sort-in-DS-normal-images12.jpg\" alt=\"heapsort output\" width=\"600\" height=\"142\" \/><\/a><\/p>\n<h3>Heapsort Procedure:<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">procedure Heap_sort(A, n):\n    Build_heap(A, n)\n    for (i=n; i&gt;=2; i--):\n        swap(A[i], A[1])\n        n = n - 1\n        Heapify(A, 1, n)\n    END for loop\nEND Heap_sort\n<\/pre>\n<h3>Implementation of Heapsort in C:<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;stdio.h&gt;\n\nvoid swap(int *num1, int *num2) {\n    int temp = *num1;\n    *num1 = *num2;\n    *num2 = temp;\n  }\n\nvoid Heapify(int array[], int n, int i)\n{\n  int max = i; \n  int Left = 2 * i + 1;\n  int right = 2 * i + 2; \n  if (Left &lt; n &amp;&amp; array[Left] &gt; array[max])\n    max = Left;\n  if (right &lt; n &amp;&amp; array[right] &gt; array[max])\n    max = right;\n  if (max != i)\n  {\n    swap(&amp;array[i], &amp;array[max]);\n    Heapify(array, n, max);\n  }\n}\n\nvoid Heap_sort(int Arr[], int n)\n{\n  for (int i = n \/ 2 - 1; i &gt;= 0; i--)\n    Heapify(Arr, n, i);\n  for (int i = n - 1; i &gt; 0; i--)\n  {\n    swap(&amp;Arr[0], &amp;Arr[i]);\n    Heapify(Arr, i, 0);\n  }\n}\n\nvoid Dispay_array(int arr[], int n)\n{\n  for (int i = 0; i &lt; n; ++i)\n    printf(\"%d\" , arr[i]);\n  printf(\"\\n\");\n}\n\nint main()\n{\n  int array[] = {24, 12, 1, 20, 16, 8, 30};\n  int n = sizeof(array) \/ sizeof(array[0]);\n\n  Heap_sort(array, n);\n\n  printf(\"Sorted array is: \\n\");\n  Dispay_array(array, n);\n}\n<\/pre>\n<h3>Heap sort Implementation in C++<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">#include &lt;bits\/stdc++.h&gt;\nusing namespace std;\nvoid swap(int *num1, int *num2) {\n    int temp = *num1;\n    *num1 = *num2;\n    *num2 = temp;\n  }\n\nvoid Heapify(int array[], int n, int i)\n{\n  int max = i; \n  int Left = 2 * i + 1;\n  int Right = 2 * i + 2; \n  if (Left &lt; n &amp;&amp; array[Left] &gt; array[max])\n    max = Left;\n  if (Right &lt; n &amp;&amp; array[Right] &gt; array[max])\n    max = Right;\n  if (max != i)\n  {\n    swap(array[i], array[max]);\n    Heapify(array, n, max);\n  }\n}\n\nvoid Heap_sort(int Arr[], int n)\n{\n  for (int i = n \/ 2 - 1; i &gt;= 0; i--)\n    Heapify(Arr, n, i);\n  for (int i = n - 1; i &gt; 0; i--)\n  {\n    swap(Arr[0], Arr[i]);\n    Heapify(Arr, i, 0);\n  }\n}\n\nvoid Dispay_array(int arr[], int n)\n{\n  for (int i = 0; i &lt; n; ++i)\n    cout &lt;&lt; arr[i] &lt;&lt; \" \";\n  cout &lt;&lt; \"\\n\";\n}\n\nint main()\n{\n  int array[] = {24, 12, 1, 20, 16, 8, 30};\n  int n = sizeof(array) \/ sizeof(array[0]);\n\n  Heap_sort(array, n);\n\n  cout &lt;&lt; \"Sorted array is: \\n\";\n  Dispay_array(array, n);\n}\n<\/pre>\n<h3>Implementation of Heap Sort in Java:<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">public class Heap_sorting {\n  public void H_sort(int Arr[])\n  {\n    int n = Arr.length;\n    for (int i = n \/ 2 - 1; i &gt;= 0; i--)\n      Heapify(Arr, n, i);\n\n    for (int i = n - 1; i &gt; 0; i--)\n    {\n      int temp = Arr[0];\n      Arr[0] = Arr[i];\n      Arr[i] = temp;\n      Heapify(Arr, i, 0);\n    }\n  }\n  \n  void Heapify(int arr[], int n, int i)\n  {\n    int max = i; \n    int Left = 2 * i + 1; \n    int Right = 2 * i + 2; \n    if (Left &lt; n &amp;&amp; Arr[l] &gt; Arr[max])\n      max = l;\n    if (Right &lt; n &amp;&amp; Arr[Right] &gt; Arr[max])\n      max = Right;\n    if (max != i) {\n      int swap = Arr[i];\n      Arr[i] = Arr[max];\n      Arr[max] = swap;\n      Heapify(Arr, n, max);\n    }\n  }\n\n  static void Display_array(int arr[])\n  {\n    int n = arr.length;\n    for (int i = 0; i &lt; n; ++i)\n      System.out.print(arr[i] + \" \");\n    System.out.println();\n  }\n\n  public static void main(String args[])\n  {\n    int arr[] = {24, 12, 1, 20, 16, 8, 30};\n    int n = arr.length;\n\n    Heap_sorting ob = new Heap_sorting();\n    ob.H_sort(arr);\n    System.out.println(\"Sorted array is\");\n    Display_array(arr);\n  }\n}\n<\/pre>\n<h3>Heapsort Implementation in Python:<\/h3>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"generic\">def Heapify(Arr, n, i):\n  max = i \n  Left = 2 * i + 1\t \n    Right = 2 * i + 2\t \n  if Left &lt; n and Arr[max] &lt; Arr[l]:\n    max = Left\n  if Right &lt; n and Arr[max] &lt; Arr[r]:\n    max = Right\n  if max != i:\n    Arr[i], Arr[max] = Arr[max], Arr[i] \n    Heapify(Arr, n, max)\n\ndef Heap_sort(Arr):\n  n = len(Arr)\n  for i in range(n\/\/2 - 1, -1, -1):\n    Heapify(Arr, n, i)\n  for i in range(n-1, 0, -1):\n    Arr[i], Arr[0] = Arr[0], Arr[i] \n    Heapify(Arr, i, 0)\n\nlist = [24, 12, 1, 20, 16, 8, 30]\nHeap_sort(list)\nn = len(list)\nprint(\"Sorted array is: \")\nfor i in range(n):\n  print(\"%d\" % list[i])\n<\/pre>\n<h3>Complexity of Heapsort:<\/h3>\n<p>The heapify process takes log n time and the swapping takes O(n) time. Thus the overall time complexity of heapsort is O(n logn).<\/p>\n<table>\n<tbody>\n<tr>\n<td><span style=\"font-weight: 400\">Scenario\u00a0<\/span><\/td>\n<td><span style=\"font-weight: 400\">Time complexity<\/span><\/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 logn)<\/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 logn)<\/span><\/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 logn)<\/span><\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n<p>The space complexity of heapsort is of order O(1) but the overhead due to recursion is very large.<\/p>\n<h3>Applications of Heapsort:<\/h3>\n<ul>\n<li>This is used to find the kth largest element or kth smallest element from a given list.<\/li>\n<li>It is used to find the k largest elements in a list\/array.<\/li>\n<li>It is used to find the k smallest elements in an array or a list.<\/li>\n<li>Heapsort is used in embedded systems. It is also used in places where security is the main concern.<\/li>\n<\/ul>\n<h3>Conclusion:<\/h3>\n<p>This article covers everything that you need to know about the heap sort algorithm. In this article, we have taken a look into the heap data structure, the heapify algorithm and heapsort. We have seen the working and implementation of the heapsort algorithm as well.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Heap sort is a sorting technique based upon heap data structure. It makes use of a binary heap for sorting the elements. Heapsort is a comparison-based sorting algorithm. It is an inplace sorting technique.&#46;&#46;&#46;<\/p>\n","protected":false},"author":1,"featured_media":83241,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3555],"tags":[3904,3905,3906,3907,3908],"class_list":["post-83081","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structure","tag-heap-sort","tag-heap-sort-algorithm","tag-heap-sort-complexity","tag-heap-sort-procdeure","tag-heap-sort-working"],"yoast_head":"<!-- This site is optimized with the Yoast SEO plugin v27.7 - https:\/\/yoast.com\/product\/yoast-seo-wordpress\/ -->\n<title>Heap Sort - Algorithm, Working and Implementation - TechVidvan<\/title>\n<meta name=\"description\" content=\"Learn about heap sort, its algorithm and working. Learn the heap data structure, heapify algorithm and implementation.\" \/>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/techvidvan.com\/tutorials\/heap-sort\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"Heap Sort - Algorithm, Working and Implementation - TechVidvan\" \/>\n<meta property=\"og:description\" content=\"Learn about heap sort, its algorithm and working. Learn the heap data structure, heapify algorithm and implementation.\" \/>\n<meta property=\"og:url\" content=\"https:\/\/techvidvan.com\/tutorials\/heap-sort\/\" \/>\n<meta property=\"og:site_name\" content=\"TechVidvan\" \/>\n<meta property=\"article:publisher\" content=\"https:\/\/www.facebook.com\/TechVidvan\/\" \/>\n<meta property=\"article:published_time\" content=\"2021-07-31T03:30:16+00:00\" \/>\n<meta property=\"og:image\" content=\"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-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=\"TechVidvan Team\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:creator\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:site\" content=\"@vidvantech\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"TechVidvan Team\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"10 minutes\" \/>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"Heap Sort - Algorithm, Working and Implementation - TechVidvan","description":"Learn about heap sort, its algorithm and working. Learn the heap data structure, heapify algorithm and implementation.","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:\/\/techvidvan.com\/tutorials\/heap-sort\/","og_locale":"en_US","og_type":"article","og_title":"Heap Sort - Algorithm, Working and Implementation - TechVidvan","og_description":"Learn about heap sort, its algorithm and working. Learn the heap data structure, heapify algorithm and implementation.","og_url":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/","og_site_name":"TechVidvan","article_publisher":"https:\/\/www.facebook.com\/TechVidvan\/","article_published_time":"2021-07-31T03:30:16+00:00","og_image":[{"width":1200,"height":628,"url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Heap-sort-in-DS.jpg","type":"image\/jpeg"}],"author":"TechVidvan Team","twitter_card":"summary_large_image","twitter_creator":"@vidvantech","twitter_site":"@vidvantech","twitter_misc":{"Written by":"TechVidvan Team","Est. reading time":"10 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/#article","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/"},"author":{"name":"TechVidvan Team","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22"},"headline":"Heap Sort &#8211; Algorithm, Working and Implementation","datePublished":"2021-07-31T03:30:16+00:00","mainEntityOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/"},"wordCount":888,"commentCount":0,"publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Heap-sort-in-DS.jpg","keywords":["Heap Sort","Heap Sort Algorithm","Heap Sort Complexity","Heap Sort Procdeure","Heap Sort Working"],"articleSection":["Data Structure Tutorials"],"inLanguage":"en-US","potentialAction":[{"@type":"CommentAction","name":"Comment","target":["https:\/\/techvidvan.com\/tutorials\/heap-sort\/#respond"]}]},{"@type":"WebPage","@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/","url":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/","name":"Heap Sort - Algorithm, Working and Implementation - TechVidvan","isPartOf":{"@id":"https:\/\/techvidvan.com\/tutorials\/#website"},"primaryImageOfPage":{"@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/#primaryimage"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/#primaryimage"},"thumbnailUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Heap-sort-in-DS.jpg","datePublished":"2021-07-31T03:30:16+00:00","description":"Learn about heap sort, its algorithm and working. Learn the heap data structure, heapify algorithm and implementation.","breadcrumb":{"@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/techvidvan.com\/tutorials\/heap-sort\/"]}]},{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/#primaryimage","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Heap-sort-in-DS.jpg","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2021\/07\/TV-Heap-sort-in-DS.jpg","width":1200,"height":628,"caption":"Heap sort in DS"},{"@type":"BreadcrumbList","@id":"https:\/\/techvidvan.com\/tutorials\/heap-sort\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/techvidvan.com\/tutorials\/"},{"@type":"ListItem","position":2,"name":"Heap Sort &#8211; Algorithm, Working and Implementation"}]},{"@type":"WebSite","@id":"https:\/\/techvidvan.com\/tutorials\/#website","url":"https:\/\/techvidvan.com\/tutorials\/","name":"TechVidvan Blogs","description":"","publisher":{"@id":"https:\/\/techvidvan.com\/tutorials\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/techvidvan.com\/tutorials\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/techvidvan.com\/tutorials\/#organization","name":"TechVidvan","url":"https:\/\/techvidvan.com\/tutorials\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/","url":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","contentUrl":"https:\/\/techvidvan.com\/tutorials\/wp-content\/uploads\/2024\/03\/techvidvan-logo-200x50-1.webp","width":200,"height":50,"caption":"TechVidvan"},"image":{"@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/logo\/image\/"},"sameAs":["https:\/\/www.facebook.com\/TechVidvan\/","https:\/\/x.com\/vidvantech"]},{"@type":"Person","@id":"https:\/\/techvidvan.com\/tutorials\/#\/schema\/person\/e9c26e74dd3d87421f7ada9433b8cd22","name":"TechVidvan Team","description":"The TechVidvan Team delivers practical, beginner-friendly tutorials on programming, Java, Python, C++, DSA, AI, ML, data Science, Android, Flutter, MERN, Web Development, and technology. Our experts are here to help you upskill and excel in today\u2019s tech industry."}]}},"amp_enabled":true,"_links":{"self":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83081","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/comments?post=83081"}],"version-history":[{"count":0,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/posts\/83081\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media\/83241"}],"wp:attachment":[{"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/media?parent=83081"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/categories?post=83081"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/techvidvan.com\/tutorials\/wp-json\/wp\/v2\/tags?post=83081"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}