Technical Interview Master Plan [7] - Heap은 아는데 왜 K번째 문제에서 자꾸 막히는가

Heap 에 대해 알아보도록 합니다.

Introduction to Heaps

힙(heap)은 우선순위(priority)를 기준으로 원소들을 정리하는 자료구조이며, 가장 우선순위가 높은 원소가 항상 힙의 맨 위(top)에 위치하도록 보장한다. 이 덕분에 언제든지 가장 우선순위가 높은 원소에 효율적으로 접근할 수 있다. 힙에는 두 가지 주요 유형이 있다.

• Min-heap

  • 가장 작은 원소가 힙의 맨 위에 오도록 하여, 가장 작은 원소를 우선시한다.

• Max-heap

  • 가장 큰 원소가 힙의 맨 위에 오도록 하여, 가장 큰 원소를 우선시한다.

텍스트 다이어그램으로 보면 다음과 같다.

Min-heap의 예시

      2
     / \
    4   12
   / \
  7   5

이 구조에서는 맨 위에 있는 값 2가 가장 작은 값이다.

Max-heap의 예시

      12
     /  \
    7    5
   / \
  2   4

이 구조에서는 맨 위에 있는 값 12가 가장 큰 값이다.

효율적인 우선순위 처리가 가능한 이유는 힙의 구조 자체에 있다. 힙은 본질적으로 하나의 이진 트리(binary tree)이다. 예를 들어 min-heap의 경우, 각 노드의 값은 그 자식 노드들의 값보다 작거나 같아야 한다. 이 성질 때문에 이 트리의 루트(root), 즉 힙의 맨 위는 항상 가장 작은 원소가 된다.

      2
     / \
    4   12
   / \
  7   5

여기서 루트 2는 전체 원소 중 가장 작은 값이다.

Heap Operations Time Complexity