data-structures
Montón binario

Introducción

Ejemplo

Min-montón

        1
      /   \
     2     3
    / \   / \
   4   5 6   7

El árbol anterior es un Min-Heap ya que la raíz es el mínimo entre todos los nodos presentes en el árbol. La misma propiedad es seguida por todos los nodos en el árbol.

Max-Heap

        7
      /   \
     6     5
    / \   / \
   4   3 2   1

El árbol anterior es un Max-Heap ya que la raíz es el máximo entre todos los nodos presentes en el árbol. La misma propiedad es seguida por todos los nodos en el árbol.

Operaciones soportadas por Min-Heap

1. getMin () : devuelve el elemento raíz. Ya que es el primer elemento de una matriz, podemos recuperar el elemento mínimo en O(1)

2. extractMin () : elimina el elemento mínimo del montón. Una vez que elimina el elemento, el árbol debe satisfacer la propiedad Min-Heap para que se realice una operación ( heapifying ) para mantener la propiedad del árbol O(logn) toma O(logn)

3. dereaseKey () - Disminuye el valor de la clave. La complejidad del tiempo para esta operación es O(logn)

4. Insertar () : la clave siempre se inserta al final del árbol. Si la clave agregada no sigue la propiedad del montón, entonces debemos filtrarla para que el árbol satisfaga la propiedad del montón. Este paso toma O(logn) hora.

5. delete () : este paso lleva tiempo O(logn) Para eliminar una clave, primero debemos reducir el valor de la clave a un valor mínimo y luego extraer este valor mínimo.

Aplicación de Heap

1. Heap Sort
2. Cola de prioridad

Heap utiliza muchos de los algoritmos de gráficos como Dijkstra's Shortest Path y Prim's Minimum Spanning Tree .

Implementación en Java

public class MinHeap {
    
    int hArr[];
    int capacity;
    int heapSize;
    
    public MinHeap(int capacity){
        this.heapSize = 0;
        this.capacity = capacity;
        hArr = new int[capacity];
    }
    
    public int getparent(int i){
        return (i-1)/2;
    }
    
    public int getLeftChild(int i){
        return 2*i+1;
    }
    
    public int getRightChild(int i){
        return 2*i+2;
    }
    
    public void insertKey(int k){
        if(heapSize==capacity)
            return;
        
        heapSize++;
        int i = heapSize-1;
        hArr[i] = k;
        
        while(i!=0 && hArr[getparent(i)]>hArr[i]){
            swap(hArr[i],hArr[getparent(i)]);
            i = getparent(i);
        }
    }
    
    public int extractMin(){
        if(heapSize==0)
            return Integer.MAX_VALUE;
        
        if(heapSize==1){
            heapSize--;
            return hArr[0];
        }
        
        int root = hArr[0];
        hArr[0] = hArr[heapSize-1];
        heapSize--;
        MinHeapify(0);
        
        return root;
    }
    
    public void decreaseKey(int i , int newVal){
        hArr[i] = newVal;
        while(i!=0 && hArr[getparent(i)]>hArr[i]){
            swap(hArr[i],hArr[getparent(i)]);
            i = getparent(i);
        }
    }
    
    public void deleteKey(int i){
        decreaseKey(i, Integer.MIN_VALUE);
        extractMin();
    }
    
    public void MinHeapify(int i){
        int l = getLeftChild(i);
        int r = getRightChild(i);
        int smallest = i;
        if(l<heapSize && hArr[l] < hArr[i])
            smallest = l;
        if(l<heapSize && hArr[r] < hArr[smallest])
            smallest = r;
        
        if(smallest!=i){
            swap(hArr[i], hArr[smallest]);
            MinHeapify(smallest);
        }
    }
    
    public void swap(int x, int y){
        int temp = hArr[x];
        hArr[x] = hArr[y];
        hArr[y] = temp;
    }
}