힙 (Heap)

코드 예시

다음은 배열 기반 최소 힙의 삽입과 상향 조정을 구현한 자바(Java) 예시다.

class MinHeap {
    int[] data = new int[64];
    int size = 0;

    void push(int x) {
        data[size] = x;
        int i = size++;
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (data[parent] <= data[i]) break;
            int tmp = data[parent];
            data[parent] = data[i];
            data[i] = tmp;
            i = parent;
        }
    }

    int peek() { return data[0]; } // 최솟값, O(1)
}

실무에서는 직접 구현하기보다 자바의 PriorityQueue(기본 최소 힙), 파이썬(Python)의 heapq 모듈처럼 언어가 제공하는 구현을 쓴다.

활용과 비교

힙의 대표 활용은 우선순위 큐다. 운영체제의 작업 스케줄러, 이벤트 시뮬레이션, 다익스트라 알고리즘에서 다음에 처리할 최소 비용 정점을 고르는 데 쓰인다. 상위 K개 추출 문제에서는 크기 K짜리 최소 힙을 유지하면 전체 정렬 O(n log n) 대신 O(n log K)로 해결된다. 두 힙을 함께 쓰면 스트림 데이터의 중앙값을 실시간으로 추적할 수도 있다.

정렬된 배열과 비교하면 선택 기준이 분명해진다. 정렬된 배열은 조회는 빠르지만 삽입이 O(n)이고, 힙은 삽입과 최솟값 삭제가 모두 O(log n)이다. 즉 데이터가 계속 흘러 들어오면서 "가장 우선순위 높은 것"만 반복해서 꺼내야 하는 상황이 힙의 자리다. 반면 전체 정렬 순회나 임의 검색이 필요하면 힙은 적합하지 않다. 힙 정렬은 최대 힙을 구성한 뒤 루트를 배열 끝과 교환하며 줄여 가는 방식으로 O(n log n)을 보장하고 추가 메모리가 필요 없지만, 캐시 효율이 낮아 실무 기본 정렬로는 퀵 정렬 계열이나 팀 정렬(Timsort)이 선호된다.

면접에서 이렇게 물어본다

• 힙과 이진 탐색 트리의 규칙 차이를 설명하고, 힙에서 임의 값 탐색이 느린 이유를 말해 보라.
• 힙을 배열로 표현할 때 부모와 자식의 인덱스 관계를 설명해 보라.
• 힙의 삽입과 삭제 과정을 상향 조정과 하향 조정으로 설명해 보라.
• 배열 전체를 힙으로 만드는 heapify가 O(n)인 이유를 설명해 보라.
• 데이터 스트림에서 상위 K개를 유지하는 방법을 힙으로 설계해 보라.