Montón K-ario

Requisito previo: almacenamiento dinámico binario 

Los montones K-arios son una generalización del montón binario (K = 2) en el que cada Node tiene K hijos en lugar de 2. Al igual que el montón binario, sigue dos propiedades:

1. Árbol binario casi completo, con todos los niveles con un número máximo de Nodes excepto el último, que se completa de izquierda a derecha.
2. Al igual que Binary Heap, se puede dividir en dos categorías: 
   1. Max k-ary heap (la clave en la raíz es mayor que todos los descendientes y lo mismo es recursivamente cierto para todos los Nodes). 
   2. Min k-ary heap (la clave en la raíz es menor que todos los descendientes y lo mismo es recursivamente cierto para todos los Nodes)

Ejemplos: 

3-ary max heap - root node is maximum
                 of all nodes
         10
     /    |   \
   7      9     8
 / | \   /
4  6  5 7


3-ary min heap -root node is minimum 
                of all nodes
         10
      /   |  \
    12    11  13
  / | \
14 15 18 

La altura de un árbol k-ario completo con n-Nodes está dada por log _k n.

Aplicaciones de K-ary Heap : 

• El montón K-ario cuando se usa en la implementación de la cola de prioridad permite una operación de tecla de disminución más rápida en comparación con el montón binario ( O (log ₂ n)) para el montón binario frente a O (log _k n) para el montón K-ario). Sin embargo, hace que la complejidad de la operación extractMin() aumente a O(k log _k n) en comparación con la complejidad de O(log ₂ n) cuando se utilizan montones binarios para la cola de prioridad. Esto permite que el almacenamiento dinámico K-ary sea más eficiente en algoritmos donde las operaciones de prioridad decreciente son más comunes que la operación extractMin(). Ejemplo: el algoritmo de Dijkstra para la ruta más corta de fuente única y el algoritmo de Prim para el árbol de expansión mínimo
• El montón K-ary tiene un mejor comportamiento de caché de memoria que un montón binario, lo que les permite ejecutarse más rápido en la práctica, aunque tiene un tiempo de ejecución más grande en el peor de los casos de la operación extractMin() y delete() (ambas son O(k log _k n) ).

Implementación:

Suponiendo una indexación basada en 0 de la array, una array representa un montón K-ary tal que para cualquier Node que consideremos: 

• El padre del Node en el índice i (excepto el Node raíz) se encuentra en el índice (i-1)/k
• Los hijos del Node en el índice i están en los índices (k*i)+1, (k*i)+2 …. (k*i)+k
• El último Node que no es hoja de un montón de tamaño n se encuentra en el índice (n-2)/k

buildHeap() : construye un montón a partir de una array de entrada. 

Esta función ejecuta un ciclo que comienza desde el último Node que no es hoja hasta el Node raíz, llamando a una función restoreDown (también conocida como maHeapify) para cada índice que restaura el índice pasado en la posición correcta del montón cambiando el Node hacia abajo en el montón K-ary construyéndolo de abajo hacia arriba. 

¿Por qué comenzamos el bucle desde el último Node que no es hoja?  
Porque todos los Nodes posteriores son Nodes de hoja que satisfarán trivialmente la propiedad del montón, ya que no tienen hijos y, por lo tanto, ya son raíces de un montón K-ary max.

restoreDown() (o maxHeapify) : se utiliza para mantener la propiedad del montón. 

Ejecuta un bucle en el que encuentra el máximo de todos los hijos del Node, lo compara con su propio valor y cambia si el máximo (valor de todos los hijos) > (valor en el Node). Repite este paso hasta que el Node se restablece en su posición original en el montón.

extractMax() : Extrayendo el Node raíz. 

Un montón k-ary max almacena el elemento más grande en su raíz. Devuelve el Node raíz, copia el último Node en el primero, llama a restaurar en el primer Node, manteniendo así la propiedad del montón.

insert() : Insertar un Node en el montón 

Esto se puede lograr insertando el Node en la última posición y llamando a restoreUp() en el índice dado para restaurar el Node en su posición adecuada en el montón. restoreUp() compara iterativamente un Node determinado con su padre, ya que en un montón máximo, el padre siempre es mayor o igual que sus Nodes secundarios, el Node se intercambia con su padre solo cuando su clave es mayor que el padre.

Combinando lo anterior, a continuación se muestra la implementación en C++ del montón K-ary.

// C++ program to demonstrate all operations of
// k-ary Heap
#include<bits/stdc++.h>
 
using namespace std;
 
// function to heapify (or restore the max- heap
// property). This is used to build a k-ary heap
// and in extractMin()
// att[] -- Array that stores heap
// len -- Size of array
// index -- index of element to be restored
//         (or heapified)
void restoreDown(int arr[], int len, int index,
                                        int k)
{
    // child array to store indexes of all
    // the children of given node
    int child[k+1];
 
    while (1)
    {
        // child[i]=-1 if the node is a leaf
        // children (no children)
        for (int i=1; i<=k; i++)
            child[i] = ((k*index + i) < len) ?
                    (k*index + i) : -1;
 
        // max_child stores the maximum child and
        // max_child_index holds its index
        int max_child = -1, max_child_index ;
 
        // loop to find the maximum of all
        // the children of a given node
        for (int i=1; i<=k; i++)
        {
            if (child[i] != -1 &&
                arr[child[i]] > max_child)
            {
                max_child_index = child[i];
                max_child = arr[child[i]];
            }
        }
 
        // leaf node
        if (max_child == -1)
            break;
 
        // swap only if the key of max_child_index
        // is greater than the key of node
        if (arr[index] < arr[max_child_index])
            swap(arr[index], arr[max_child_index]);
 
        index = max_child_index;
    }
}
 
// Restores a given node up in the heap. This is used
// in decreaseKey() and insert()
void restoreUp(int arr[], int index, int k)
{
    // parent stores the index of the parent variable
    // of the node
    int parent = (index-1)/k;
 
    // Loop should only run till root node in case the
    // element inserted is the maximum restore up will
    // send it to the root node
    while (parent>=0)
    {
        if (arr[index] > arr[parent])
        {
            swap(arr[index], arr[parent]);
            index = parent;
            parent = (index -1)/k;
        }
 
        // node has been restored at the correct position
        else
            break;
    }
}
 
// Function to build a heap of arr[0..n-1] and value of k.
void buildHeap(int arr[], int n, int k)
{
    // Heapify all internal nodes starting from last
    // non-leaf node all the way upto the root node
    // and calling restore down on each
    for (int i= (n-1)/k; i>=0; i--)
        restoreDown(arr, n, i, k);
}
 
// Function to insert a value in a heap. Parameters are
// the array, size of heap, value k and the element to
// be inserted
void insert(int arr[], int* n, int k, int elem)
{
    // Put the new element in the last position
    arr[*n] = elem;
 
    // Increase heap size by 1
    *n = *n+1;
 
    // Call restoreUp on the last index
    restoreUp(arr, *n-1, k);
}
 
// Function that returns the key of root node of
// the heap and then restores the heap property
// of the remaining nodes
int extractMax(int arr[], int* n, int k)
{
    // Stores the key of root node to be returned
    int max = arr[0];
 
    // Copy the last node's key to the root node
    arr[0] = arr[*n-1];
 
    // Decrease heap size by 1
    *n = *n-1;
 
    // Call restoreDown on the root node to restore
    // it to the correct position in the heap
    restoreDown(arr, *n, 0, k);
 
    return max;
}
 
// Driver program
int main()
{
    const int capacity = 100;
    int arr[capacity] = {4, 5, 6, 7, 8, 9, 10};
    int n = 7;
    int k = 3;
 
    buildHeap(arr, n, k);
 
    printf("Built Heap : \n");
    for (int i=0; i<n; i++)
        printf("%d ", arr[i]);
 
    int element = 3;
    insert(arr, &n, k, element);
 
    printf("\n\nHeap after insertion of %d: \n",
            element);
    for (int i=0; i<n; i++)
        printf("%d ", arr[i]);
 
    printf("\n\nExtracted max is %d",
                extractMax(arr, &n, k));
 
    printf("\n\nHeap after extract max: \n");
    for (int i=0; i<n; i++)
        printf("%d ", arr[i]);
 
    return 0;
}

Built Heap : 
10 9 6 7 8 4 5 

Heap after insertion of 3: 
10 9 6 7 8 4 5 3 

Extracted max is 10

Heap after extract max: 
9 8 6 7 3 4 5 

Análisis de la complejidad del tiempo 

• Para un montón k-ario, con n Nodes, la altura máxima del montón dado será log _k n. Entonces, restoreUp() se ejecuta por un máximo de log _k n veces (ya que en cada iteración, el Node se desplaza un nivel hacia arriba en el caso de restoreUp() o un nivel hacia abajo en el caso de restoreDown).
• restoreDown() se llama a sí mismo recursivamente para k niños. Entonces, la complejidad temporal de estas funciones es O(k log _k n).
• Las operaciones de inserción y disminución de tecla() llaman a restoreUp() una vez. Entonces la complejidad es O(log _k n).
• Dado que extractMax() llama a restoreDown() una vez, su complejidad es O(k log _k n)
• La complejidad temporal del almacenamiento dinámico de compilación es O(n) (el análisis es similar al almacenamiento dinámico binario)