data-structures
Двоичная куча

Вступление

пример

Min-Heap

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

Вышеупомянутое дерево представляет собой Min-Heap, так как корень является минимальным среди всех узлов, присутствующих в дереве. За этим же свойством следуют все узлы в дереве.

Max-Heap

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

Вышеупомянутое дерево является Max-Heap, так как корень является максимальным среди всех узлов, присутствующих в дереве. За этим же свойством следуют все узлы в дереве.

Операции, поддерживаемые Min-Heap

1. getMin () - возвращает корневой элемент. Поскольку он является первым элементом в массиве, мы можем получить минимальный элемент в O(1)

2. extractMin () - он удаляет минимальный элемент из кучи. Так как после удаления элемента дерево должно удовлетворять свойству Min-Heap, поэтому выполняется операция ( heapifying ) для сохранения свойства tree.This берет O(logn)

3. dereaseKey () - Уменьшает значение ключа. Временная сложность для этой операции - O(logn)

4. insert () - Ключ всегда вставлен в конец дерева. Если добавленный ключ не соответствует свойству кучи, нам нужно просачиваться так, чтобы дерево удовлетворяло свойству кучи. Этот шаг принимает значение O(logn) время.

5. delete () - для этого этапа требуется время O(logn) logn O(logn) Для удаления ключа сначала необходимо уменьшить значение ключа до минимального значения, а затем извлечь это минимальное значение.

Применение кучи

1. Куча сортировки
2. Очередь приоритетов

В куче используется множество алгоритмов графа, таких как Dijkstra's Shortest Path и Prim's Minimum Spanning Tree .

Реализация на 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;
    }
}