data-structures
이진 힙

소개

예

민 - 힙

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

위의 트리는 루트가 트리에있는 모든 노드 중에서 최소이기 때문에 최소 힙 (Min-Heap)입니다. 동일한 특성 뒤에는 트리의 모든 노드가옵니다.

최대 힙

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

위의 트리는 루트가 트리에있는 모든 노드 중에서 최대이기 때문에 Max-Heap입니다. 동일한 특성 뒤에는 트리의 모든 노드가옵니다.

Min-Heap에서 지원되는 작업

1. getMin () - 루트 요소를 반환합니다. 배열의 첫 번째 요소이므로 O(1) 에서 최소 요소를 검색 할 수 있습니다.

2. extractMin () - 힙 에서 최소 요소를 제거합니다. 요소를 제거한 후 트리가 Min-Heap 속성을 충족시켜야 트리 작업을 유지하기위한 작업 ( heapifying )이 수행됩니다.이 작업은 O(logn)

3. dereaseKey () - 키의 값을 감소시킵니다.이 연산의 복잡도는 O(logn)

4. insert () - 키는 항상 트리의 끝에 삽입됩니다. 추가 된 키가 heap 속성을 따르지 않으면 트리가 heap 속성을 만족하도록 필독 할 필요가 없습니다.이 단계는 O(logn) 시각.

5. delete () -이 단계는 O(logn) 시간이 걸립니다. 키를 삭제하려면 먼저 키 값을 최소값으로 줄인 다음이 최소값을 추출해야합니다.

힙 응용 프로그램

1. 힙 정렬
2. 우선 순위 대기열

Heap은 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;
    }
}