Heap Sort para orden decreciente usando min heap

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++ 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 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 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# 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.

<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