data-structures
Heap binario

introduzione

Esempio

Min-Heap

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

L'albero sopra riportato è un Min-Heap poiché la radice è il minimo tra tutti i nodi presenti nell'albero. La stessa proprietà è seguita da tutti i nodi dell'albero.

Max-Heap

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

L'albero sopra riportato è un Max-Heap poiché la radice è il massimo tra tutti i nodi presenti nell'albero. La stessa proprietà è seguita da tutti i nodi dell'albero.

Operazioni supportate da Min-Heap

1. getMin () - Restituisce l'elemento root. Dal momento che è il primo elemento di un array, possiamo recuperare l'elemento minimo in O(1)

2. extractMin () - Rimuove l'elemento minimo dall'heap. Dopo aver rimosso l'elemento l'albero deve soddisfare la proprietà Min-Heap in modo che venga eseguita un'operazione ( heapifying ) per mantenere la proprietà tree.Questo richiede O(logn)

3. dereaseKey () - Riduce il valore della chiave. La complessità temporale per questa operazione è O(logn)

4. insert () - La chiave viene sempre inserita alla fine dell'albero. Se la chiave aggiunta non segue la proprietà heap di quella che dobbiamo percolare in modo che l'albero soddisfi la proprietà heap. Questo passaggio richiede O(logn) tempo.

5. delete () - Questa procedura richiede O(logn) logn O(logn) time. Per eliminare una chiave, dobbiamo prima ridurre il valore della chiave a un valore minimo e quindi estrarre questo valore minimo.

Applicazione di Heap

1. Ordinamento heap
2. Coda prioritaria

L'heap viene utilizzato per molti algoritmi grafici come Dijkstra's Shortest Path e Prim's Minimum Spanning Tree .

Implementazione in 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;
    }
}