Heap

힙(Heap)이란?

가장 큰 값 혹은 가장 작은 값을 빠르게 꺼내기 위한 자료구조이다(메모리의 Heap 아님). 대부분 완전 이진트리를 사용하며 배열 하나로 구현한다. 목적에 맞게 다음과 같은 두 가지의 구현이 있다.

 

최소 힙: 가장 작은 값이 항상 루트 노드에 있으며 모든 노드에서 부모는 자식보다 작거나 같다.

최소 힙

최대 힙: 가장 큰 값이 항상 루트 노드에 있으며 모든 노드에서 부모는 자식보다 크거나 같다.

최대 힙

이런 특징들로 우선순위 큐를 구현하는데 가장 많이 사용된다.

 

또한, 배열 하나로 구현하기 때문에 인덱스 매핑으로 완전이진트리를 구현한다.

부모 노드: 자식 노드 idx // 2

왼쪽 자식: 부모 노드 * 2

오른쪽 자식: 부모 노드 * 2 + 1

 

Heap의 주요 연산

모든 연산은 연산 이후 Heap의 불변식인 모든 노드는 부모보다 작다/크다를 만족시켜야한다. 연산의 본질은 불변식이 깨진 위치만 복구하는 것이며 위로 올리면서 복구하는 sift-up(원소 삽입)와 아래로 내리면서 복구하는 sift-down(원소 삭제) 두 가지이다. 

이 두 복구 연산은 모두 최악의 경우(루트 -> 리프, 리프 -> 루트)에도 완전이진트리의 구조 상 O(logN)의 시간 복잡도를 갖게 된다.

1. peek() / pop()

루트 노드를 확인/반환한다.

 

반환 자체의 시간 복잡도는 루트 노드만 조회하면 되기 때문에 O(1)이며 삭제연산까지 이루어지는 pop()연산은 빠진 루트를 채우기 위해 다음과 같은 sift-down 연산을 반복한다.

 

1. 마지막 원소를 루트 노드로 올린다.

2. 자식 노드들과 비교하며 올바른 자리를 찾아간다.

2. insert(x)

Heap에 임의의 값 X를 삽입한다.

 

불변식을 만족하기 위해 다음과 같은 sift-up 연산을 반복한다.

 

1. 배열의 마지막에 원소를 삽입한다.

2. 부모 노드와 비교하며 올바른 자리를 찾아간다.

3. heapify(A)

주어진 배열 A를 힙으로 재구성한다.

 

배열 A를 Heap의 불변식을 만족하도록 바꾸는 세 가지 방법이 존재한다.

3.1) 배열 A를 순회하며 빈 힙에 n번 삽입 연산을 반복

• n번 O(logN)이기 때문에 O(n logN)이라고 오해하기 쉽지만 정확하게 말하자면 O(log1 + log2 + log3 + ... + logN) = O(n logN) 이다.(Stirling's approximation)

3.2) sift-up

• 같은 배열의 1번 인덱스부터 순회하며 각 인덱스를 방금 추가된 리프처럼 보고 sift-up 연산을 반복
• 사실상 1번 방법과 동일한 방법 (in-place인지 새로운 배열인지의 차이)
• 시간 복잡도 O(n logN)

3.3) sift-down (Floyd의 buildHeap)

• 현재 노드와 자식 노드를 비교하며 sift-down 연산을 한 번씩 수행
• 핵심 아이디어: "리프는 이미 힙"이라는 사실을 이용해서 마지막 내부 노드(리프 윗 노드)부터 루트 순으로 훑으며 각 노드에서 sift-down을 한 번씩 수행한다.
• 시간 복잡도는 (0 * n/2) + (1 * n/4) + ... + (h * 1)로 해당 식을 계산시 O(n)이 나오게 된다. (리프 노드의 개수는 n/2개이고 레벨이 증가할 때마다 2배씩 작아짐)

4. delete(x)

임의 위치 X의 값을 삭제한다.

 

pop() 연산과 비슷하게 마지막 원소를 X로 가져와 빈자리를 채우고 위/아래 중 필요한 방향으로 복구한다.

 

1. 마지막 원소를 X로 가져온다.

2. 현재 힙에 알맞게 부모 노드와 자식 노드랑 비교하여 어느 방향으로 복구할지 결정한다.

 

Heap 변형

1.  d-ary 힙

자식이 d개인 d진 트리로 높이는 log_d N로 줄어든다. 이로인해 sift-up 연산으로 복구하는 속도가 빨라진다(레벨(높이)이 낮아지니까).

하지만 sift-down 단계마다 최소 자식 선택 비용이 O(d) → 총 O(d * log_d n)

삽입이 많고 삭제 빈도가 적으면 더 큰 d가 유리할 수 있다.

d-ary 힙에서의 heapify

• 자식 d개: 자식 인덱스는 {d*i+1..d*i+d}
• 마지막 내부 노드: (n-2) // d
• siftDown에서 “적절한 자식”을 찾는 비용이 O(d)로 늘지만, 깊이는 log_d n로 줄어든다.
• 전체 heapify는 여전히 O(n) (상수항만 커짐)

 

2. 양방향 우선순위 큐

그렇다면 가장 높은 값과 낮은 값을 모두 효율적으로 찾을 수는 없을까? 이런 문제를 해결하기 위해 양방향 우선순위 큐가 고안되었다. 대표적으로 아래의 두 가지 방법으로 구현한다.

 

1) Min-Max Heap

완전이진트리(배열)에서 레벨을 번갈아가면서 min/max의 성질을 부여한다.

예를 들면

 

• 짝수 레벨(0,2,4, …): min-level (노드 ≤ 모든 자손)
• 홀수 레벨(1,3,5, …): max-level (노드 ≥ 모든 자손)

이렇게 되면 최소값은 루트 노드이고 최대값은 max(1레벨의 값들(2개))이 되어 O(1)로 조회가 가능하다.

sift-up / sift-down 연산은 부모/자식과 비교하는 것이 아닌 조부모/자손과 비교하며 올바른 자리를 찾게 된다. 최초 한 번은 부모/자식과 비교하여 올바른 Level을 찾아간다.

 

2) Interval Heap

각 노드가 [low, high] 두 값을 저장한다. 전체 트리에서 모든 low 값들은 최소 힙을 만족하고 모든 high 값들은 최대 힙을 동시에 만족한다.

만약 원소의 개수가 홀수일 땐 리프 하나만 단일 원소를 갖는 식으로 처리가 가능하다.

sift-up / sift-down 연산은 low/high에 맞는 부모/자식과 비교하며 올바른 자리를 찾아간다. 각 연산 이후 동일한 레벨에서 low와 high를 재비교하며 올바른 heap에서의 계산을 유지한다.

 

3. 멜더블 힙

기본적인 힙은 두 힙을 병합할 때 보통 heapify(arr(n) + arr(m)) = O(n + m)으로 처리한다. 여기서 병합할 때 더 효율적인 시간 복잡도를 갖기 위해 설계된 힙을 멜더블 힙이라고 부르며, 구현체들은 다음과 같다. Leftist, Skew, Pairing, Binomial, Fibonacci, Randomized. 멜더블 힙의 두 힙을 병합하는 meld(merge) 연산은 O(logN)에서 O(1)까지 구현체에 따라 다르다.

 

Heap의 활용

우선순위 큐

힙의 주 목적이다. 대부분의 우선순위 큐는 힙을 사용하여 구현한다.

힙 정렬

힙을 사용한 정렬로 과정은 다음과 같다.

 

배열을 최대/최소 힙(원하는 정렬 키)으로 만든 뒤 루트를 맨 뒤와 swap, 힙 크기 – 1 (swap한 원소 제외), sift-down을 반복한다.

시간 복잡도는 buildHeap 단계에서 O(n), sift-down 반복이 O(n logN) 이므로 최종 시간 복잡도는 O(n logN)이다.

 

참고

https://www.geeksforgeeks.org/dsa/heap-data-structure/

Heap Data Structure - GeeksforGeeks

 

https://opendatastructures.org/ods-java/10_2_MeldableHeap_Randomize.html

10.2 MeldableHeap: A Randomized Meldable Heap