[DS&AL] Heap 자료구조
Heap 자료구조
Heap은 완전 이진 트리의 일종으로, 우선순위 큐를 위해 만들어진 자료구조입니다. 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조를 Heap이라고 합니다.
힙 자료구조는 일종의 반정렬 상태(느슨한 상태)를 유지하는데, 이는 부모 노드의 키 값이 자식 노드의 키 값보다 항상 크거나 작은 이진 트리를 의미합니다. 힙 자료구조에서는 중복된 값을 허용하며, 최대, 혹은 최소값을 찾기 위해 기존의 시간복잡도가 $O(n)$ ->$O(logN)$으로 감소합니다.
Heap 자료구조의 종류
힙 자료구조는 크게 2가지 구조로 나뉩니다. 최대 힙, 최소 힙 방법이 있습니다.
Max Heap (최대 힙)
최대 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리를 의미합니다. 항상, 어떠한 상황에서든 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같습니다.
Min Heap (최소 힙)
최대 힙과는 다르게 최소 힙은 부모 노드의 키 값이 자식 노드의 키 값보다 항상 작거나 같은 완전 이진 트리를 의미합니다. 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은, 즉 클 수 없습니다.
Heap 코드 구현
파이썬에서는 heapq 라이브러리를 통해 간편하게 사용할 수 있습니다. 이 heapq 라이브러리를 사용할 때, default로 최소 힙 형태로 제공됩니다.
활용 예시는 다음과 같습니다.
import heapq
heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)
print(heap) # [10, 50, 20]
이 코드에서는 heapq 라이브러리를 불러와서 빈 리스트를 생성 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘깁니다. heappush를 사용해서 값을 집어넣습니다. 이 과정에서 print를 한다면, 10, 50, 20 순서대로 출력하지만, 실제로는 꺼내게 된다면 10 -> 20 -> 50 순으로 나오게 됩니다.
그리고 이미 리스트 안에 변수가 있다면, heapify 함수를 통해 해당 리스트를 힙 자료형으로 변환할 수 있습니다.
heap2 = [50 ,10, 20]
heapq.heapify(heap2)
print(heap2) # [10, 50, 20]
힙에서 자료를 가져오려면 pop을 통해 제거하면서 가져오는 방식이나, 혹은 리스트처럼 [0], [1] 과 같은 인덱싱 방식으로 가져올 수 있습니다.
pop을 통해 원소를 제거하고, 그에 해당하는 자료형을 가져오는 방법은 하기 코드와 같습니다.
removed_value = heapq.heappop(heap) # heappop 함수를 통해 heap에서 가장 작은 원소 제거하고 반환
print(removed_value) # 10
print(heap) # [20, 50]
이렇게 heapq를 사용해서 힙을 만들 수 있지만, 이는 Min Heap 기준이기에, Max heap을 구현하기 위해서는 다음의 방법처럼 전환해야 합니다.
import heapq
values = [1, 2, 3, 4, 5]
heap = []
max_heap = []
for value in values:
heapq.heappush(heap, -value)
print(heap) # [-5, -4, -2, -1, -3]
for i in range(len(heap)):
max_heap.append(-heapq.heappop(heap))
print(max_heap) # [5, 4, 2, 1, 3]
여기서는 먼저 값을 음수로 바꾼 다음 양수로 전환하는 방법을 사용합니다. 먼저 heap에 heappush를 진행할 때는 원래 값 대신, -를 붙인 음수를 min-heap에 넣습니다. 그래서 힙 안에는 음수로 정렬된 값들이 들어갑니다. 다음에 이제 힙에서 꺼내서 원래대로 복원을 하는데, heappop에서 힙에서 항상 작은 값을 먼저 꺼내는 것을 이용합니다. 그렇게 되기에 -5, -4, … 순서대로 양수로 바뀌어서 다시 들어가는 것이죠.
예시로, heapq를 사용하지 않고, max heap, min heap을 구현하는 경우는 다음과 같습니다.
## heapq를 사용하지 않고 Min Heap 구현
min_heap = [0] # sentinel
def min_push(x):
min_heap.append(x)
child = len(min_heap) - 1
parent = child // 2
# 위로 끌어올리기 (부모 > 자식 이면 교환)
while parent > 0 and min_heap[parent] > min_heap[child]:
min_heap[parent], min_heap[child] = min_heap[child], min_heap[parent]
child = parent
parent = child // 2
def min_pop():
if len(min_heap) <= 2: # 루트만 남았을 때
return min_heap.pop()
root = min_heap[1] # 루트 백업
min_heap[1] = min_heap.pop() # 말단 노드를 루트로 승격
parent = 1
child = parent * 2
# 아래로 내리기 (더 작은 자식과 교환)
while child < len(min_heap):
if child + 1 < len(min_heap) and min_heap[child + 1] < min_heap[child]:
child += 1
if min_heap[parent] > min_heap[child]:
min_heap[parent], min_heap[child] = min_heap[child], min_heap[parent]
parent = child
child = parent * 2
else:
break
return root
# 사용 예시
for v in [2,5,7,3,4,6]:
min_push(v)
print("min_heap:", min_heap)
while len(min_heap) >= 2:
print("min_pop ->", min_pop())
## heapq를 사용하지 않고 Max Heap 구현
max_heap = [0] # sentinel
def max_push(x):
max_heap.append(x)
child = len(max_heap) - 1
parent = child // 2
# 위로 끌어올리기 (부모 < 자식 이면 교환)
while parent > 0 and max_heap[parent] < max_heap[child]:
max_heap[parent], max_heap[child] = max_heap[child], max_heap[parent]
child = parent
parent = child // 2
def max_pop():
if len(max_heap) <= 2:
return max_heap.pop()
root = max_heap[1]
max_heap[1] = max_heap.pop()
parent = 1
child = parent * 2
# 아래로 내리기 (더 큰 자식과 교환)
while child < len(max_heap):
if child + 1 < len(max_heap) and max_heap[child + 1] > max_heap[child]:
child += 1
if max_heap[parent] < max_heap[child]:
max_heap[parent], max_heap[child] = max_heap[child], max_heap[parent]
parent = child
child = parent * 2
else:
break
return root
# 사용 예시
for v in [2,5,7,3,4,6]:
max_push(v)
print("max_heap:", max_heap)
while len(max_heap) >= 2:
print("max_pop ->", max_pop())
Leave a comment