data-structures
Binaire Hoop

Invoering

Voorbeeld

Min-Hoop

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

De bovenstaande boom is een Min-Heap, omdat de wortel het minimum is van alle knooppunten in de boom. Dezelfde eigenschap wordt gevolgd door alle knooppunten in de boom.

Max-Heap

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

De bovenstaande boom is een Max-Heap, omdat de wortel het maximum is van alle knooppunten in de boom. Dezelfde eigenschap wordt gevolgd door alle knooppunten in de boom.

Operaties ondersteund door Min-Heap

1. getMin () - Het retourneert het root-element. Aangezien het het eerste element in een array is, kunnen we het minimale element in O(1) ophalen

2. extractMin () - Het verwijdert het minimale element uit de heap. Nadat het element is verwijderd, moet de boom voldoen aan de eigenschap Min-Heap, zodat een bewerking ( heapifying ) wordt uitgevoerd om de eigenschap tree te behouden. Dit duurt O(logn)

3. dereaseKey () - Het verlaagt de waarde van de sleutel. Tijdcomplexiteit voor deze bewerking is O(logn)

4. insert () - De sleutel wordt altijd ingevoegd aan het einde van de boom. Als de toegevoegde sleutel niet de heap-eigenschap volgt, moeten we omhoog percoleren zodat de boom voldoet aan de heap-eigenschap. Deze stap neemt O(logn) tijd.

5. delete () - Deze stap kost O(logn) Voor het verwijderen van een sleutel moeten we eerst de sleutelwaarde verlagen tot een minimumwaarde en vervolgens deze minimumwaarde extraheren.

Toepassing van Heap

1. Heap Sort
2. Prioriteits-rij

Heap wordt gebruikt in veel van de grafische algoritmen, zoals Dijkstra's Shortest Path en Prim's Minimum Spanning Tree .

Implementatie 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;
    }
}