[자료구조] 이진 힙(Binary Heap)

  이진 힙(Binary Heap)이란 완전 이진 트리로서 부모의 우선순위가 자식의 우선순위보다 높은 자료구조입니다. 다른 트리 자료구조와 다르게 중복 값을 허용합니다. 각 노드에 대해 부모의 우선순위가 자식의 우선순위보다 높은 것을 힙 속성(Heap Property)이라 합니다. 이진 힙에는 키가 작을수록 높은 우선순위를 가지는 최소 힙(Minimum Heap)과 클수록 더 높은 우선순위를 가지는 최대 힙(Maximum Heap)이 있습니다. 최솟값 또는 최댓값을 빠르게 찾아내는 데 유용합니다. 그러나 형제 노드 간 우선순위 보장이 없으므로 반 정렬 상태입니다.

 

  최소 힙 삽입과 삭제 구현 코드

import java.util.ArrayList;

class MinHeap {
    ArrayList<Integer> heap;
    public MinHeap() {
        this.heap = new ArrayList<>();
        this.heap.add(0);
    }
    public void insert(int data) {
        heap.add(data);
        int cur = heap.size() - 1;
        while (cur > 1 && heap.get(cur / 2) > heap.get(cur)) {
            int parentVal = heap.get(cur / 2);
            heap.set(cur / 2, data);
            heap.set(cur, parentVal);
            cur /= 2;
        }
    }
    public Integer delete() {
        if (heap.size() == 1) {
            System.out.println("Heap is empty");
            return null;
        }
        int target = heap.get(1);
        heap.set(1, heap.get(heap.size() - 1));
        heap.remove(heap.size() - 1);
        int cur = 1;
        while (true) {
            int leftIndex = cur * 2;
            int rightIndex = cur * 2 + 1;
            int targetIndex = -1;
            if (rightIndex < heap.size()) {
                targetIndex = heap.get(leftIndex) < heap.get(rightIndex) ? leftIndex : rightIndex;
            } else if (leftIndex < heap.size()) {
                targetIndex = cur * 2;
            } else {
                break;
            }
            if (heap.get(cur) < heap.get(targetIndex)) {
                break;
            } else {
                int parentVal = heap.get(cur);
                heap.set(cur, heap.get(targetIndex));
                heap.set(targetIndex, parentVal);
                cur = targetIndex;
            }
        }
        return target;
    }
}

  삽입 연산은 힙의 마지막 노드의 바로 다음 빈 원소에 새로운 키를 저장한 후, 루트 방향으로 올라가면서 부모의 키와 비교하여 힙 속성을 만족할 때까지 노드를 교환하는 연산입니다.

  삭제 연산은 최상위 노드를 반환하고 삭제합니다. 마지막 위치의 노드를 최상위 노드로 위치시킨 뒤, 자식 노드끼리의 값과 비교 후 부모의 키와 비교하여 힙 속성을 만족할 때까지 노드를 교환합니다.

  이진 힙에서의 삽입과 삭제 등의 연산을 위한 upheap은 삽입된 노드나 키가 감소된 노드로부터 최대 루트까지 올라가며 부모와 자식을 교환합니다. 또한 최솟값 삭제 연산에서는 힙의 마지막 노드를 루트로 이동한 후 downheap을 최하위층의 노드까지 교환해야 하는 경우가 발생합니다. 따라서 각 연산의 수행 시간은 힙의 높이에 비례합니다. 그러나 힙은 완전 이진 트리이므로 힙에 n개의 노드가 있으면 높이는 O(log₂N)입니다. 따라서 각 연산의 수행 시간은 O(logN)입니다.

  이진 힙은 우선순위를 가진 데이터를 처리하는 자료구조로서, 관공서, 은행, 병원, 우체국 등에서 이루어지는 업무와 관련된 이벤트 처리, 컴퓨터 운영체제의 프로세스 처리 등에 적합한 자료구조입니다.

 

  ※ "자바와 함께하는 자료구조의 이해"라는 책을 참고하여 쓴 게시글입니다. 책에는 없는 내용을 추가하여 작성된 부분이 있습니다. 문제가 되거나 부정확한 부분이 있다면 알려주시면 감사하겠습니다.

  ※ 책은 게시글보다 정확한 내용을 담고 있으며 코드, 그림, 예제를 이용하여 개념을 자세히 설명합니다.