힙

힙

힙은 중복된 키 값을 가질 수 있는 완전 이진 트리의 한 종류로, 원소들 중 가장 큰 값이나 가장 작은 값을 $O(logN)$에 찾기 위해 사용된다. 모든 노드에 대해 부모의 키 값 $\geq$ 자식의 키 값을 만족하는 힙을 최대 힙, 자식의 키 값 $\geq$ 부모의 키 값을 만족하는 힙을 최소 힙이라고 한다. 최대 힙에서의 최댓값과 최소 힙에서의 최솟값은 각각 힙의 루트 노드이다. 일반적으로 힙이라고 하면 최대 힙을 의미한다.

---

힙 ADT

데이터
int key

메소드	내용
initHeap()	힙을 초기화한다.
insertHeap(int key)	힙에 키를 삽입한다.
deleteHeap(int key)	힙에서 값이 가장 큰 키를 삭제하고 반환한다.
size()	힙에 크기를 반환한다.
isEmpty()	힙이 비어있는지 검사한다.

---

힙의 삽입 연산

힙에 키 값을 삽입할 때의 연산이다. 힙이 완전 이진 트리의 형태를 유지해야 하므로 우선 키 값을 힙의 마지막 위치에 삽입한다. 위 트리는 17을 새로 삽입한 트리이다.

이제 힙의 성질을 만족해야 하므로 부모 노드와 비교하면서 부모의 키 값 $\geq$ 자식의 키 값을 만족할때까지 부모 노드와 위치를 바꿔주면 된다. 17 $\geq$ 16이므로 서로 위치를 바꾸고, 20 $\geq$ 17이므로 이동을 멈춘다.

---

힙의 삭제 연산

힙의 삭제 연산은 힙에서 최댓값을 반환하고 삭제하는 것을 의미한다. 위의 경우 20이 최댓값이므로 20을 반환하고 삭제한다.

역시 완전 이진 트리의 형태를 유지하기 위해서 힙의 맨 마지막 노드를 루트 노드로 이동시켜준다.

그 후 왼쪽 자식 노드와 오른쪽 자식 노드중 값이 큰 노드와 부모의 키 값 $\geq$ 자식의 키 값을 만족할때까지 위치를 바꿔주면 된다. 위의 경우 18 $\geq$ 17이므로 18과 16을 바꾸고, 16의 두 자식 노드인 15와 14 모두 16보다 작으므로 이동을 멈춘다.

---

힙 구현 코드

class Heap {
    private int[] heap;
    private int heapSize;
    private int maxHeapSize;

    public void initHeap() {
        heap = new int[100];
        maxHeapSize = 100;
        heapSize = 0;
    }

    private void grow() {
        maxHeapSize += 100;
        int[] newHeap = Arrays.copyOfRange(heap, 0, maxHeapSize);
        heap = newHeap;
    }

    private void swap(int a, int b) {
        int tmp = heap[a];
        heap[a] = heap[b];
        heap[b] = tmp;
    }

    public void insertHeap(int key) {
        if(heapSize + 1 > maxHeapSize - 1) {
            grow();
        }

        heap[++heapSize] = key;

        int idx = heapSize;

        while(idx > 1) {
            if(heap[idx / 2] < key) {
                swap(idx / 2, idx);
                idx /= 2;
            }
            else {
                break;
            }
        }
    }

    public int deleteHeap() {
        if(heapSize == 0) {
            throw new ArrayIndexOutOfBoundsException();
        }

        int idx = 1;
        int ret = heap[idx];
        heap[idx] = heap[heapSize--];

        while(true) {
            int changeIdx = idx * 2;

            if(idx * 2 + 1 <= heapSize) {
                if(heap[idx * 2] < heap[idx * 2 + 1]) {
                    changeIdx = idx * 2 + 1;
                }
            }

            if(heap[changeIdx] > heap[idx]) {
                swap(changeIdx, idx);
                idx = changeIdx;
            }
            else {
                   break;
            }
        }

        return ret;
    }

    public int size() {
        return heapSize;
    }

    public boolean isEmpty() {
        if(heapSize == 0) {
            return true;
        }
        else {
            return false;
        }
    }
}

---

우선순위 큐

힙을 이용하여 구현한 자료구조 중 우선순위 큐라는 것이 있다. 일반적으로 큐는 FIFO 형식의 자료구조이다. 하지만 우선순위 큐는 먼저 들어온 데이터가 먼저 나가는 것이 아니라, 우선순위가 높은 데이터가 먼저 나간다. 최대 힙에서는 최댓값이, 최소 힙에서는 최솟값이 먼저 나간다.
삽입과 삭제 모두 $O(logN)$의 시간복잡도를 가진다.

Priority Queue