给定一个元素数组，使用最小堆按降序对数组排序。 例如：
null
Input : arr[] = {5, 3, 10, 1}Output : arr[] = {10, 5, 3, 1}Input : arr[] = {1, 50, 100, 25}Output : arr[] = {100, 50, 25, 1}
先决条件： 堆排序 使用 小顶堆 . 算法： 1. 从输入数据构建一个最小堆。 2. 此时，最小的项存储在堆的根。将其替换为堆的最后一项，然后将堆的大小减少1。最后，修剪树根。 3. 当堆的大小大于1时，重复上述步骤。 注： 堆排序使用最小堆排序按降序排列，而最大堆排序按升序排列
C++
// C++ program for implementation of Heap Sort #include <bits/stdc++.h> 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 smallest = i; // Initialize smalles as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // If left child is smaller than root if (l < n && arr[l] < arr[smallest]) smallest = l; // If right child is smaller than smallest so far if (r < n && arr[r] < arr[smallest]) smallest = r; // If smallest is not root if (smallest != i) { swap(arr[i], arr[smallest]); // Recursively heapify the affected sub-tree heapify(arr, n, smallest); } } // 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 program int main() { int arr[] = { 4, 6, 3, 2, 9 }; 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 import java.io.*; class GFG { // To heapify a subtree rooted with node i which is // an index in arr[]. n is size of heap static void heapify( int arr[], int n, int i) { int smallest = i; // Initialize smalles as root int l = 2 * i + 1 ; // left = 2*i + 1 int r = 2 * i + 2 ; // right = 2*i + 2 // If left child is smaller than root if (l < n && arr[l] < arr[smallest]) smallest = l; // If right child is smaller than smallest so far if (r < n && arr[r] < arr[smallest]) smallest = r; // If smallest is not root if (smallest != i) { int temp = arr[i]; arr[i] = arr[smallest]; arr[smallest] = temp; // Recursively heapify the affected sub-tree heapify(arr, n, smallest); } } // main function to do heap sort static 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 int 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 */ static void printArray( int arr[], int n) { for ( int i = 0 ; i < n; ++i) System.out.print(arr[i] + " " ); System.out.println(); } // Driver program public static void main(String[] args) { int arr[] = { 4 , 6 , 3 , 2 , 9 }; int n = arr.length; heapSort(arr, n); System.out.println( "Sorted array is " ); printArray(arr, n); } } // This code is contributed by vt_m. |
Python3
# Python3 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 def heapify(arr, n, i): smallest = i # Initialize smalles as root l = 2 * i + 1 # left = 2*i + 1 r = 2 * i + 2 # right = 2*i + 2 # If left child is smaller than root if l < n and arr[l] < arr[smallest]: smallest = l # If right child is smaller than # smallest so far if r < n and arr[r] < arr[smallest]: smallest = r # If smallest is not root if smallest ! = i: (arr[i], arr[smallest]) = (arr[smallest], arr[i]) # Recursively heapify the affected # sub-tree heapify(arr, n, smallest) # main function to do heap sort def heapSort(arr, n): # Build heap (rearrange array) for i in range ( int (n / 2 ) - 1 , - 1 , - 1 ): heapify(arr, n, i) # One by one extract an element # from heap for i in range (n - 1 , - 1 , - 1 ): # Move current root to end # arr[ 0 ], arr[i] = arr[i], arr[ 0 ] # call max heapify on the reduced heap heapify(arr, i, 0 ) # A utility function to print # array of size n def printArray(arr, n): for i in range (n): print (arr[i], end = " " ) print () # Driver Code if __name__ = = '__main__' : arr = [ 4 , 6 , 3 , 2 , 9 ] n = len (arr) heapSort(arr, n) print ( "Sorted array is " ) printArray(arr, n) # This code is contributed by PranchalK |
C#
// C# program for implementation of Heap Sort using System; class GFG { // To heapify a subtree rooted with // node i which is an index in arr[], // n is size of heap static void heapify( int [] arr, int n, int i) { int smallest = i; // Initialize smalles as root int l = 2 * i + 1; // left = 2*i + 1 int r = 2 * i + 2; // right = 2*i + 2 // If left child is smaller than root if (l < n && arr[l] < arr[smallest]) smallest = l; // If right child is smaller than smallest so far if (r < n && arr[r] < arr[smallest]) smallest = r; // If smallest is not root if (smallest != i) { int temp = arr[i]; arr[i] = arr[smallest]; arr[smallest] = temp; // Recursively heapify the affected sub-tree heapify(arr, n, smallest); } } // main function to do heap sort static 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 int 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 */ static void printArray( int [] arr, int n) { for ( int i = 0; i < n; ++i) Console.Write(arr[i] + " " ); Console.WriteLine(); } // Driver program public static void Main() { int [] arr = { 4, 6, 3, 2, 9 }; int n = arr.Length; heapSort(arr, n); Console.WriteLine( "Sorted array is " ); printArray(arr, n); } } // This code is contributed by vt_m. |
Javascript
<script> // Javascript 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) { var smallest = i; // Initialize smalles as root var l = 2 * i + 1; // left = 2*i + 1 var r = 2 * i + 2; // right = 2*i + 2 // If left child is smaller than root if (l < n && arr[l] < arr[smallest]) smallest = l; // If right child is smaller than smallest so far if (r < n && arr[r] < arr[smallest]) smallest = r; // If smallest is not root if (smallest != i) { [arr[i], arr[smallest]] = [arr[smallest], arr[i]] // Recursively heapify the affected sub-tree heapify(arr, n, smallest); } } // main function to do heap sort function heapSort(arr, n) { // Build heap (rearrange array) for ( var i = parseInt(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 [arr[0], arr[i]] = [arr[i], arr[0]] // 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 ( var i = 0; i < n; ++i) document.write( arr[i] + " " ); document.write( "<br>" ); } // Driver program var arr = [4, 6, 3, 2, 9]; var n = arr.length; heapSort(arr, n); document.write( "Sorted array is <br>" ); printArray(arr, n); </script> |
输出：
Sorted array is 9 6 4 3 2
时间复杂性： 需要 O（logn） 对于 希皮菲 和 O（n） 对于 构建堆 。因此 堆排序 使用 小顶堆 或 最大堆 是 O（nlogn）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
