Montón de construcción de array

Dada una array de N elementos. La tarea es construir un montón binario a partir de la array dada. El montón puede ser Max Heap o Min Heap.
Ejemplo
 

Input: arr[] = {4, 10, 3, 5, 1}
Output: Corresponding Max-Heap:
       10
     /   \
    5     3
   /  \
  4    1

Input: arr[] = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}
Output: Corresponding Max-Heap:
                 17
              /      \
            15         13
          /    \      /  \
         9      6    5   10
        / \    /  \
       4   8  3    1

Suponga que los elementos de entrada dados son: 4, 10, 3, 5, 1.
El árbol binario completo correspondiente para esta array de elementos [4, 10, 3, 5, 1] ​​será: 
 

       4
     /   \
    10    3
   /  \
  5    1

Note:
Root is at index 0 in array.
Left child of i-th node is at (2*i + 1)th index.
Right child of i-th node is at (2*i + 2)th index.
Parent of i-th node is at (i-1)/2 index.

Complete Interview Preparation - GFG

Enfoque simple : supongamos que necesitamos construir un Max-Heap a partir de los elementos de la array mencionados anteriormente. Se puede ver claramente que el árbol binario completo anterior formado no sigue la propiedad Heap. Entonces, la idea es acumular el árbol binario completo formado a partir de la array en orden de nivel inverso siguiendo un enfoque de arriba hacia abajo.
Eso es primero heapify, el último Node en el orden de nivel transversal del árbol, luego heapify el penúltimo Node y así sucesivamente. 
Complejidad de tiempo: Heapify un solo Node toma O (log N) complejidad de tiempo donde N es el número total de Nodes. Por lo tanto, construir todo el Heap requerirá N operaciones de heapify y la complejidad de tiempo total será O(N*logN) .
En realidad, construir un montón lleva O(n) tiempo dependiendo de la implementación que se puede veraquí _
Enfoque optimizado : el enfoque anterior se puede optimizar observando el hecho de que los Nodes hoja no necesitan acumularse ya que siguen la propiedad del montón. Además, la representación de array del árbol binario completo contiene el recorrido de orden de nivel del árbol.
Entonces, la idea es encontrar la posición del último Node no hoja y realizar la operación heapify de cada Node no hoja en orden de nivel inverso. 
 

Last non-leaf node = parent of last-node.
or, Last non-leaf node = parent of node at (n-1)th index.
or, Last non-leaf node = Node at index ((n-1) - 1)/2.
                       = (n/2) - 1.

Ilustración
 

Array = {1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17}

Corresponding Complete Binary Tree is:
                 1
              /     \
            3         5
         /    \     /  \
        4      6   13  10
       / \    / \
      9   8  15 17

The task to build a Max-Heap from above array.

Total Nodes = 11.
Last Non-leaf node index = (11/2) - 1 = 4.
Therefore, last non-leaf node = 6.

To build the heap, heapify only the nodes:
[1, 3, 5, 4, 6] in reverse order.

Heapify 6: Swap 6 and 17.
                 1
              /     \
            3         5
         /    \      /  \
        4      17   13  10
       / \    /  \
      9   8  15   6

Heapify 4: Swap 4 and 9.
                 1
              /     \
            3         5
         /    \      /  \
        9      17   13  10
       / \    /  \
      4   8  15   6

Heapify 5: Swap 13 and 5.
                 1
              /     \
            3         13
         /    \      /  \
        9      17   5   10
       / \    /  \
      4   8  15   6

Heapify 3: First Swap 3 and 17, again swap 3 and 15.
                 1
              /     \
            17         13
          /    \      /  \
         9      15   5   10
        / \    /  \
       4   8  3   6

Heapify 1: First Swap 1 and 17, again swap 1 and 15, 
           finally swap 1 and 6.
                 17
              /      \
            15         13
          /    \      /  \
         9      6    5   10
        / \    /  \
       4   8  3    1

Implementación
 

C++

// C++ program for building Heap from Array
  
#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);
    }
}
  
// Function to build a Max-Heap from the given array
void buildHeap(int arr[], int n)
{
    // Index of last non-leaf node
    int startIdx = (n / 2) - 1;
  
    // Perform reverse level order traversal
    // from last non-leaf node and heapify
    // each node
    for (int i = startIdx; i >= 0; i--) {
        heapify(arr, n, i);
    }
}
  
// A utility function to print the array
// representation of Heap
void printHeap(int arr[], int n)
{
    cout << "Array representation of Heap is:\n";
  
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "\n";
}
  
// Driver Code
int main()
{
    // Binary Tree Representation
    // of input array
    //             1
    //           /    \
    //         3        5
    //       /  \     /  \
    //     4      6  13  10
    //    / \    / \
    //   9   8  15 17
    int arr[] = { 1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17 };
  
    int n = sizeof(arr) / sizeof(arr[0]);
  
    buildHeap(arr, n);
  
    printHeap(arr, n);
    // Final Heap:
    //              17
    //            /    \
    //          15      13
    //         /  \     / \
    //        9     6  5   10
    //       / \   / \
    //      4   8 3   1
  
    return 0;
}

Java

// Java program for building Heap from Array
  
public class BuildHeap {
  
    // To heapify a subtree rooted with node i which is
    // an index in arr[].Nn is size of heap
    static 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);
        }
    }
  
    // Function to build a Max-Heap from the Array
    static void buildHeap(int arr[], int n)
    {
        // Index of last non-leaf node
        int startIdx = (n / 2) - 1;
  
        // Perform reverse level order traversal
        // from last non-leaf node and heapify
        // each node
        for (int i = startIdx; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }
  
    // A utility function to print the array
    // representation of Heap
    static void printHeap(int arr[], int n)
    {
        System.out.println(
            "Array representation of Heap is:");
  
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
  
        System.out.println();
    }
  
    // Driver Code
    public static void main(String args[])
    {
        // Binary Tree Representation
        // of input array
        //            1
        //         /      \
        //       3        5
        //     /   \       / \
        //  4       6  13 10
        // / \    /  \
        // 9  8  15   17
        int arr[] = { 1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17 };
  
        int n = arr.length;
  
        buildHeap(arr, n);
  
        printHeap(arr, n);
    }
}

Python3

# Python3 program for building Heap from Array
  
# To heapify a subtree rooted with node i
# which is an index in arr[]. 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
  
    # If left child is larger than root
    if l < n and arr[l] > arr[largest]:
        largest = l
  
    # If right child is larger than largest so far
    if r < n and arr[r] > arr[largest]:
        largest = r
  
    # If largest is not root
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
  
        # Recursively heapify the affected sub-tree
        heapify(arr, n, largest)
  
# Function to build a Max-Heap from the given array
  
  
def buildHeap(arr, n):
  
    # Index of last non-leaf node
    startIdx = n // 2 - 1
  
    # Perform reverse level order traversal
    # from last non-leaf node and heapify
    # each node
    for i in range(startIdx, -1, -1):
        heapify(arr, n, i)
  
# A utility function to print the array
# representation of Heap
  
  
def printHeap(arr, n):
    print("Array representation of Heap is:")
  
    for i in range(n):
        print(arr[i], end=" ")
    print()
  
  
# Driver Code
if __name__ == '__main__':
  
    # Binary Tree Representation
    # of input array
    #             1
    #           /    \
    #         3        5
    #       /  \     /  \
    #     4      6  13  10
    #    / \    / \
    #   9   8  15 17
    arr = [1, 3, 5, 4, 6, 13,
           10, 9, 8, 15, 17]
  
    n = len(arr)
  
    buildHeap(arr, n)
  
    printHeap(arr, n)
  
    # Final Heap:
    #             17
    #           /    \
    #         15      13
    #        /  \     / \
    #       9     6  5   10
    #      / \   / \
    #     4   8 3   1
  
# This code is contributed by Princi Singh

C#

// C# program for building Heap from Array
using System;
  
public class BuildHeap {
  
    // To heapify a subtree rooted with node i which is
    // an index in arr[].Nn is size of heap
    static 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);
        }
    }
  
    // Function to build a Max-Heap from the Array
    static void buildHeap(int[] arr, int n)
    {
        // Index of last non-leaf node
        int startIdx = (n / 2) - 1;
  
        // Perform reverse level order traversal
        // from last non-leaf node and heapify
        // each node
        for (int i = startIdx; i >= 0; i--) {
            heapify(arr, n, i);
        }
    }
  
    // A utility function to print the array
    // representation of Heap
    static void printHeap(int[] arr, int n)
    {
        Console.WriteLine(
            "Array representation of Heap is:");
  
        for (int i = 0; i < n; ++i)
            Console.Write(arr[i] + " ");
  
        Console.WriteLine();
    }
  
    // Driver Code
    public static void Main()
    {
        // Binary Tree Representation
        // of input array
        //            1
        //         /      \
        //       3        5
        //      /  \       / \
        //   4       6  13 10
        //  / \   / \
        // 9   8 15  17
        int[] arr = { 1, 3, 5, 4, 6, 13, 10, 9, 8, 15, 17 };
  
        int n = arr.Length;
  
        buildHeap(arr, n);
  
        printHeap(arr, n);
    }
}
  
// This code is contributed by Ryuga
Producción: 

Array representation of Heap is:
17 15 13 9 6 5 10 4 8 3 1

 

Publicación traducida automáticamente

Artículo escrito por harsh.agarwal0 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *