data-structures
Binärer Haufen

Einführung

Beispiel

Min-Heap

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

Der obige Baum ist ein Min-Heap, da die Wurzel das Minimum unter allen im Baum vorhandenen Knoten ist. Der gleichen Eigenschaft folgen alle Knoten im Baum.

Max-Heap

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

Der obige Baum ist ein Max-Heap, da die Wurzel das Maximum unter allen im Baum vorhandenen Knoten ist. Der gleichen Eigenschaft folgen alle Knoten im Baum.

Von Min-Heap unterstützte Operationen

1. getMin () - Gibt das Wurzelelement zurück. Da es das erste Element in einem Array ist, können wir das Mindestelement in O(1) abrufen.

2. extractMin () - Es beseitigt die minimale Element aus der heap.Since nachdem das Element Entfernen der Baum muß die Min-Heap - Eigenschaft erfüllen so eine Operation (heapifying) durchgeführt , wird der Baum property.This nimmt aufrechtzuerhalten O(logn)

3. dereaseKey () - Verringert den Wert des Schlüssels. Die Zeitkomplexität für diese Operation ist O(logn)

4. insert () - Der Schlüssel immer am Ende des tree.If der hinzugefügte Schlüssel folgt nicht der Heap - Eigenschaft eingeführt wird , als wir perkolieren up müssen , so dass der Baum genügt der heap property.This Schritt nimmt nimmt O(logn) Zeit.

5. delete () - Dieser Schritt benötigt O(logn) -Zeit. Zum Löschen eines Schlüssels müssen wir den Schlüsselwert zunächst auf einen Mindestwert verringern und dann diesen Mindestwert extrahieren.

Anwendung von Heap

1. Heap Sort
2. Prioritätswarteschlange

Heap wird für viele der Graph-Algorithmen verwendet, beispielsweise für Dijkstra's Shortest Path und Prim's Minimum Spanning Tree .

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