data-structures
Binär hög

Introduktion

Exempel

Min-Heap

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

Trädet ovan är en Min-Heap eftersom roten är det minsta bland alla noder som finns i trädet. Samma egenskap följs av alla noder i trädet.

Max-Heap

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

Trädet ovan är en Max-Heap eftersom roten är den maximala bland alla noder som finns i trädet. Samma egenskap följs av alla noder i trädet.

Verksamhet som stöds av Min-Heap

1. getMin () - Det returnerar rotelementet. Eftersom det är det första elementet i en matris kan vi hämta minimumelementet i O(1)

2. extractMin () - Det tar bort minsta element från högen. Sedan efter att elementet har tagits bort måste trädet uppfylla Min-Heap-egenskapen så att en operation ( heapifying ) utförs för att upprätthålla O(logn) tar O(logn)

3. dereaseKey () - Det minskar värdet på nyckeln. Tiden komplexitet för denna operation är O(logn)

4. insert () - Nyckeln sätts alltid in i slutet av trädet. Om den tillagda nyckeln inte följer heapegenskapen än vi behöver percolera upp så att trädet uppfyller O(logn) steg tar tar O(logn) tid.

5. delete () - Detta steg tar O(logn) För att radera en nyckel måste vi först minska nyckelvärdet till ett minimivärde och sedan extrahera detta minimivärde.

Användning av Heap

1. Heap Sort
2. Prioritetskö

Heap används många av grafalgoritmerna som Dijkstra's Shortest Path och Prim's Minimum Spanning Tree .

Implementering i 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;
    }
}