堆排序是一种基于二进制堆数据结构的基于比较的排序技术。它类似于选择排序，我们首先找到最小元素，然后将最小元素放在开头。我们对剩下的元素重复同样的过程。
null
是什么 二进制堆 ? 让我们首先定义一个完整的二叉树。一个完整的二叉树是一个二叉树，在这个二叉树中，除了最后一个之外，每个级别都被完全填充，所有节点都尽可能地左移（源代码） 维基百科 ) A. 二进制堆 是一个完整的二叉树，其中项目以特殊顺序存储，使得父节点中的值大于（或小于）其两个子节点中的值。前者称为最大堆，后者称为最小堆。堆可以用二叉树或数组表示。
为什么要对二进制堆使用基于数组的表示？ 由于二进制堆是一个完整的二叉树，因此可以很容易地将其表示为数组，并且基于数组的表示是节省空间的。如果父节点存储在索引I处，则左子节点可以按2*I+1计算，右子节点可以按2*I+2计算（假设索引从0开始）。
如何“heapify”一棵树？
将二叉树重塑为堆数据结构的过程称为“heapify”。二叉树是一种最多有两个子节点的树数据结构。如果一个节点的子节点是“heapify”，那么只有“heapify”过程可以应用于该节点。堆应该始终是一个完整的二叉树。
从一个完整的二叉树开始，我们可以通过在堆的所有非叶元素上运行一个名为“heapify”的函数，将其修改为最大堆。i、 e.“heapify”使用递归。
“heapify”的算法：
heapify(array) Root = array[0] Largest = largest( array[0] , array [2 * 0 + 1]. array[2 * 0 + 2]) if(Root != Largest) Swap(Root, Largest)
“heapify”的例子：
30(0) / 70(1) 50(2)Child (70(1)) is greater than the parent (30(0))Swap Child (70(1)) with the parent (30(0)) 70(0) / 30(1) 50(2)
按递增顺序排序的堆排序算法： 1. 从输入数据构建一个最大堆。 2. 此时，最大的项存储在堆的根。将其替换为堆的最后一项，然后将堆的大小减少1。最后，修剪树根。 3. 当堆的大小大于1时，重复步骤2。
如何构建堆？ 只有对节点的子节点进行了Heapify，Heapify过程才能应用于该节点。因此，必须按照自底向上的顺序进行heapification。 让我们通过一个例子来理解：
Input data: 4, 10, 3, 5, 1 4(0) / 10(1) 3(2) / 5(3) 1(4)The numbers in bracket represent the indices in the array representation of data.Applying heapify procedure to index 1: 4(0) / 10(1) 3(2) / 5(3) 1(4)Applying heapify procedure to index 0: 10(0) / 5(1) 3(2) / 4(3) 1(4)The heapify procedure calls itself recursively to build heap in top down manner.
C++
// C++ program for implementation of Heap Sort #include <iostream> using namespace std; // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap void heapify( int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { swap(arr[i], arr[largest]); // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } // main function to do heap sort void heapSort( int arr[], int n) { // Build heap (rearrange array) for ( int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for ( int i = n - 1; i > 0; i--) { // Move current root to end swap(arr[0], arr[i]); // call max heapify on the reduced heap heapify(arr, i, 0); } } /* A utility function to print array of size n */ void printArray( int arr[], int n) { for ( int i = 0; i < n; ++i) cout << arr[i] << " " ; cout << "" ; } // Driver code int main() { int arr[] = { 12, 11, 13, 5, 6, 7 }; int n = sizeof (arr) / sizeof (arr[0]); heapSort(arr, n); cout << "Sorted array is " ; printArray(arr, n); } |
JAVA
// Java program for implementation of Heap Sort public class HeapSort { public void sort( int arr[]) { int n = arr.length; // Build heap (rearrange array) for ( int i = n / 2 - 1 ; i >= 0 ; i--) heapify(arr, n, i); // One by one extract an element from heap for ( int i = n - 1 ; i > 0 ; i--) { // Move current root to end int temp = arr[ 0 ]; arr[ 0 ] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapify(arr, i, 0 ); } } // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap void heapify( int arr[], int n, int i) { int largest = i; // Initialize largest as root int l = 2 * i + 1 ; // left = 2*i + 1 int r = 2 * i + 2 ; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } /* A utility function to print array of size n */ static void printArray( int arr[]) { int n = arr.length; for ( int i = 0 ; i < n; ++i) System.out.print(arr[i] + " " ); System.out.println(); } // Driver code public static void main(String args[]) { int arr[] = { 12 , 11 , 13 , 5 , 6 , 7 }; int n = arr.length; HeapSort ob = new HeapSort(); ob.sort(arr); System.out.println( "Sorted array is" ); printArray(arr); } } |
Python3
# Python program for implementation of heap Sort # To heapify subtree rooted at index i. # n is size of heap def heapify(arr, n, i): largest = i # Initialize largest as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # See if left child of root exists and is # greater than root if l < n and arr[largest] < arr[l]: largest = l # See if right child of root exists and is # greater than root if r < n and arr[largest] < arr[r]: largest = r # Change root, if needed if largest ! = i: arr[i], arr[largest] = arr[largest], arr[i] # swap # Heapify the root. heapify(arr, n, largest) # The main function to sort an array of given size def heapSort(arr): n = len (arr) # Build a maxheap. for i in range (n / / 2 - 1 , - 1 , - 1 ): heapify(arr, n, i) # One by one extract elements for i in range (n - 1 , 0 , - 1 ): arr[i], arr[ 0 ] = arr[ 0 ], arr[i] # swap heapify(arr, i, 0 ) # Driver code arr = [ 12 , 11 , 13 , 5 , 6 , 7 ] heapSort(arr) n = len (arr) print ( "Sorted array is" ) for i in range (n): print ( "%d" % arr[i],end = " " ) # This code is contributed by Mohit Kumra |
C#
// C# program for implementation of Heap Sort using System; public class HeapSort { public void sort( int [] arr) { int n = arr.Length; // Build heap (rearrange array) for ( int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for ( int i = n - 1; i > 0; i--) { // Move current root to end int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap void heapify( int [] arr, int n, int i) { int largest = i; // Initialize largest as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { int swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } /* A utility function to print array of size n */ static void printArray( int [] arr) { int n = arr.Length; for ( int i = 0; i < n; ++i) Console.Write(arr[i] + " " ); Console.Read(); } // Driver code public static void Main() { int [] arr = { 12, 11, 13, 5, 6, 7 }; int n = arr.Length; HeapSort ob = new HeapSort(); ob.sort(arr); Console.WriteLine( "Sorted array is" ); printArray(arr); } } // This code is contributed // by Akanksha Rai(Abby_akku) |
PHP
<?php // Php program for implementation of Heap Sort // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(& $arr , $n , $i ) { $largest = $i ; // Initialize largest as root $l = 2* $i + 1; // left = 2*i + 1 $r = 2* $i + 2; // right = 2*i + 2 // If left child is larger than root if ( $l < $n && $arr [ $l ] > $arr [ $largest ]) $largest = $l ; // If right child is larger than largest so far if ( $r < $n && $arr [ $r ] > $arr [ $largest ]) $largest = $r ; // If largest is not root if ( $largest != $i ) { $swap = $arr [ $i ]; $arr [ $i ] = $arr [ $largest ]; $arr [ $largest ] = $swap ; // Recursively heapify the affected sub-tree heapify( $arr , $n , $largest ); } } // main function to do heap sort function heapSort(& $arr , $n ) { // Build heap (rearrange array) for ( $i = $n / 2 - 1; $i >= 0; $i --) heapify( $arr , $n , $i ); // One by one extract an element from heap for ( $i = $n -1; $i > 0; $i --) { // Move current root to end $temp = $arr [0]; $arr [0] = $arr [ $i ]; $arr [ $i ] = $temp ; // call max heapify on the reduced heap heapify( $arr , $i , 0); } } /* A utility function to print array of size n */ function printArray(& $arr , $n ) { for ( $i = 0; $i < $n ; ++ $i ) echo ( $arr [ $i ]. " " ) ; } // Driver program $arr = array (12, 11, 13, 5, 6, 7); $n = sizeof( $arr )/sizeof( $arr [0]); heapSort( $arr , $n ); echo 'Sorted array is ' . "" ; printArray( $arr , $n ); // This code is contributed by Shivi_Aggarwal ?> |
Javascript
<script> // JavaScript program for implementation // of Heap Sort function sort( arr) { var n = arr.length; // Build heap (rearrange array) for ( var i = Math.floor(n / 2) - 1; i >= 0; i--) heapify(arr, n, i); // One by one extract an element from heap for ( var i = n - 1; i > 0; i--) { // Move current root to end var temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; // call max heapify on the reduced heap heapify(arr, i, 0); } } // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap function heapify(arr, n, i) { var largest = i; // Initialize largest as root var l = 2 * i + 1; // left = 2*i + 1 var r = 2 * i + 2; // right = 2*i + 2 // If left child is larger than root if (l < n && arr[l] > arr[largest]) largest = l; // If right child is larger than largest so far if (r < n && arr[r] > arr[largest]) largest = r; // If largest is not root if (largest != i) { var swap = arr[i]; arr[i] = arr[largest]; arr[largest] = swap; // Recursively heapify the affected sub-tree heapify(arr, n, largest); } } /* A utility function to print array of size n */ function printArray(arr) { var n = arr.length; for ( var i = 0; i < n; ++i) document.write(arr[i] + " " ); } var arr = [ 5, 12, 11, 13, 4, 6, 7 ]; var n = arr.length; sort(arr); document.write( "Sorted array is <br>" ); printArray(arr, n); // This code is contributed by SoumikMondal </script> |
输出
Sorted array is 5 6 7 11 12 13
在这里 是以前的C代码供参考。
笔记： 堆排序是一种就地算法。 它的典型实现并不稳定，但可以使其稳定（参见 这 )
时间复杂性： heapify的时间复杂度为O（Logn）。createAndBuildHeap（）的时间复杂度为O（n），堆排序的总体时间复杂度为O（nLogn）。
heapsort的优势——
- 效率—— 执行堆排序所需的时间以对数方式增加，而随着要排序的项目数的增加，其他算法可能会以指数方式增长。这种排序算法非常有效。
- 内存使用– 内存使用是最小的，因为除了保存要排序的项目的初始列表所需的内容外，它不需要额外的内存空间来工作
- 简单—— 它比其他同样有效的排序算法更容易理解，因为它不使用递归等高级计算机科学概念
HeapSort的应用 1. 对接近排序（或K排序）的数组进行排序 2. k数组中的最大（或最小）元素 堆排序算法的用途有限，因为快速排序和合并排序在实践中更好。然而，堆数据结构本身被大量使用。看见 堆数据结构的应用 https://youtu.be/MtQL_ll5KhQ 快照：
堆排序测验
Geeksforgeks/Geeksquick上的其他排序算法： 快速排序 , 选择排序 , 气泡排序 , 插入排序 , 合并排序 , 堆排序 , 快速排序 , 基数排序 , 计数排序 , 斗式分拣 , 贝壳类 , 梳排序 , 鸽子洞排序
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
