Dada una array de elementos, ordene la array en orden decreciente usando el montón mínimo.
Ejemplos:
Input : arr[] = {5, 3, 10, 1} Output : arr[] = {10, 5, 3, 1} Input : arr[] = {1, 50, 100, 25} Output : arr[] = {100, 50, 25, 1}
Requisito previo: Clasificación de almacenamiento dinámico utilizando almacenamiento dinámico mínimo .
Algoritmo:
1. Cree un montón mínimo a partir de los datos de entrada.
2. En este punto, el elemento más pequeño se almacena en la raíz del montón. Reemplácelo con el último elemento del montón y luego reduzca el tamaño del montón en 1. Finalmente, apile la raíz del árbol.
3. Repita los pasos anteriores mientras el tamaño del montón sea mayor que 1.
Nota: Ordenar montón usando ordenaciones de montón mínimo en orden descendente mientras que el montón máximo ordena en orden ascendente
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 smallest 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 min 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 << "\n"; } // 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 \n"; 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 smallest 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 min 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 smallest 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 min 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 smallest 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 min 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 smallest 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 min 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
Complejidad de tiempo: se necesita O (logn) para heapify y O (n) para construir un montón . Por lo tanto, la complejidad de tiempo general de la clasificación del montón usando el montón mínimo o el montón máximo es O (nlogn)
Complejidad del espacio: O(n) para la pila de llamadas
Publicación traducida automáticamente
Artículo escrito por Shashank_Pathak y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA