data-structures
Tas binaire

Introduction

Exemple

Min-Heap

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

L'arbre ci-dessus est un Min-Heap puisque la racine est le minimum parmi tous les nœuds présents dans l'arbre. La même propriété est suivie par tous les nœuds de l'arborescence.

Max-Heap

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

L'arbre ci-dessus est un Max-Heap puisque la racine est le maximum parmi tous les nœuds présents dans l'arbre. La même propriété est suivie par tous les nœuds de l'arbre.

Opérations prises en charge par Min-Heap

1. getMin () - Renvoie l'élément racine. Étant donné que c'est le premier élément d'un tableau, nous pouvons récupérer l'élément minimum dans O(1)

2. extractMin () - Supprime l'élément minimum du segment de mémoire. Après avoir supprimé l'élément, l'arborescence doit satisfaire à la propriété Min-Heap afin qu'une opération ( heapifying ) soit effectuée pour conserver la propriété de l' O(logn)

3. dereaseKey () - Diminue la valeur de la clé.La complexité du temps pour cette opération est O(logn)

4. insert () - La clé est toujours insérée à la fin de l'arborescence.Si la clé ajoutée ne suit pas la propriété heap que nous devons percoler pour que l'arborescence satisfasse la propriété O(logn) étape nécessite O(logn) temps.

5. delete () - Cette étape prend le temps O(logn) Pour supprimer une clé, nous devons d'abord réduire la valeur de la clé à une valeur minimale, puis extraire cette valeur minimale.

Application du tas

1. Tri du tas
2. File d'attente de priorité

Heap utilise de nombreux algorithmes graphiques tels Dijkstra's Shortest Path et Prim's Minimum Spanning Tree .

Implémentation 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;
    }
}