Heap
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리이다.
힙이란 자료 구조는 "응급실"을 떠올리면 된다.
응급실에 많은 환자가 존재하지만, 그 중에서 우선순위는 존재한다.
예를 들어서 "감기", "골절", "출혈" 환자가 있다면, 우선순위를 배정한 다음
"출혈" -> "골절" -> "감기" 순으로 치료를 진행할 것이다.
그때, "심정지"라는 새로운 환자가 들어오게되면,
우선순위를 가장 높게 부여한 후 가장 먼저 치료 받게 해야한다.
"심정지" -> "출혈" -> "골절" -> "감기"이 자료구조가 바로 힙이다.
힙의 특징을 다시 생각해보자.
-
환자들 중 에서 우선 순위가 높은 환자가 왔다면 먼저 치료해야한다.
-> 힙은 특정 순서에 맞춰서 항상 데이터를 정렬해주는 자료구조이다. -
기존 환자들이 있지만, 우선 순위가 높은 환자가 왔다면 그 환자를 먼저 치료해야한다.
-> 힙에 새로운 자료 구조가 추가될 경우, 항상 다시 순서에 맞춰서 정렬을 시켜줘야한다. -
그렇다면 정렬과는 무엇이 다른가?
-> 정렬은 항상 O(NlogN)만큼의 시간 복잡도가 매번 걸리는 연산입니다.
반면, 힙은 데이터를 가져오고 빼는데 O(logN)만큼의 시간 복잡도가 걸리는 대신 매번 정렬을 해주지 않아도 정렬된 상태를 유지할 수 있다.
항상 최대 혹은 최소 값들이 필요한 연산이 있다면? 힙을 사용하자.
힙의 구현
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨이 있도록 하는 자료구조이다. 즉, 부모 노드의 값이 자식 노드의 값보다 항상 커야한다.
8 Level 0
6 3 Level 1
2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이
4 2 5 Level 2 # 자식 노드보다 크지 않아서 힙이 아닙니다..!
참고로, 힙은 최대값을 맨 위로 올릴수도 있고, 최솟값을 맨 위로 올릴수도 있다.
최댓값이 맨 위인 힙을 Max 힙, 최솟값이 맨 위인 힙을 Min 힙이라고 한다.
힙은 항상 큰 값이 상위 레벨에 있고 작은 레벨은 하위 레벨에 있어야한다.는 꼭 지켜져야 한다.
원소 추가
규칙을 지키면서 다음과 방식으로 진행하면 된다.
- 원소를 맨 마지막에 넣는다.
- 부모 노드와 비교해서 만약 더 크다면 자리를 바꾼다.
- 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2번 과정을 반복한다.
이 맥스 힙에서 9를 추가해보겠습니다! 8 Level 0 6 3 Level 1 4 2 1 Level 2 1. 맨 마지막에 원소를 넣습니다. 8 Level 0 6 3 Level 1 4 2 1 9 Level 2 2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다. 8 Level 0 6 3 Level 1 4 2 1 9 Level 2 8 Level 0 6 9 Level 1 4 2 1 3 Level 2 2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다. 8 Level 0 6 9 Level 1 4 2 1 3 Level 2 9 Level 0 6 8 Level 1 4 2 1 3 Level 2 3. 가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다! 9 Level 0 6 8 Level 1 4 2 1 3 Level 2
MaxHeap 초기화
def __init__(self): self.items = [None] # 여기에 코드 구현 return
MaxHeap에 원소 추가
def insert(self, value): self.items.append(value) # 파이썬의 list는 length랑 capacity를 가짐. append() 시간 복잡도 O(1) cur_index = len(self.items) - 1 while cur_index > 1: parent_index = cur_index // 2 if self.items[cur_index] > self.items[parent_index]: self.items[cur_index], self.items[parent_index] = self.items[parent_index], self.items[cur_index] cur_index = parent_index else: break return
원소 제거
최대 힙에서 원소를 제거 하는 방법은 최댓값, 루트 노드를 삭제하는 것이다.
스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수 없다. 또한 원소를 삭제할때도 힙의 규칙은 지켜져야 한다.
- 루트 노드와 맨 끝에 있는 원소를 교체한다.
- 맨 뒤에 있는 원스를 삭제한다.
- 변경된 노드와 자식 노드를 비교한다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다.
- 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3번 과정을 반복합니다.
- 2에서 제거한 원래 루트 노드를 반환한다.
이 맥스 힙에서 원소를 제거해보겠습니다! (항상 맨 위의 루트 노드가 제거 됩니다.) 8 Level 0 6 7 Level 1 2 5 4 3 Level 2 1. 루트 노드와 맨 끝에 있는 원소를 교체한다. 8 Level 0 6 7 Level 1 2 5 4 3 Level 2 3 Level 0 6 7 Level 1 2 5 4 8 Level 2 2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제합니다. 이 값이 기존 맥스힙에 있던 가장 큰 값입니다. 따라서 이 값을 마지막에는 반환해줘야 합니다! 3 Level 0 6 7 Level 1 2 5 4 X Level 2 3-1. 변경된 노드를 더 큰 자식 노드와 비교해야 합니다. 우선 부모와 왼쪽 자식을 비교합니다. 그리고 부모와 오른쪽 자식을 비교합니다. 그리고 부모 보다 큰 자식 중, 더 큰 자식과 변경해야 합니다. 왼쪽 자식인 6과 오른쪽 자식인 7 중에서 7이 더 크고, 부모인 3보다 크니까 둘의 자리를 변경합니다. 3 Level 0 6 7 Level 1 2 5 4 Level 2 7 Level 0 6 3 Level 1 2 5 4 Level 2 3-2. 다시 자식 노드와 비교합니다. 우선 부모와 왼쪽 자식을 비교합니다. 왼쪽 자식인 4는 부모인 3보다 더 크니까 둘의 자리를 변경합니다. 7 Level 0 6 3 Level 1 2 5 4 Level 2 7 Level 0 6 4 Level 1 2 5 3 Level 2 4. 가장 아래 레벨에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삭제했습니다! 7 Level 0 6 4 Level 1 2 5 3 Level 2 5. 그리고, 아까 제거한 원래 루트 노드, 8을 반환하면 됩니다!
MaxHeap에 원소 제거
def remove(self):
if len(self.items) <= 1: # 0번 인덱스는 비어있으므로
return -1 # 또는 에러 처리
# 1. 루트 값을 저장하고, 마지막 노드를 루트로 옮김
max_val = self.items[1]
last_val = self.items.pop()
if len(self.items) == 1: # 마지막 노드 하나만 있었던 경우
return max_val
self.items[1] = last_val
cur_index = 1
# 2. Down-heap (Sift-down) 시작
while True:
left_child = cur_index * 2
right_child = cur_index * 2 + 1
largest = cur_index
# 왼쪽 자식이 있고, 현재(largest)보다 크다면
if left_child < len(self.items) and self.items[left_child] > self.items[largest]:
largest = left_child
# 오른쪽 자식이 있고, 현재(largest)보다 크다면
if right_child < len(self.items) and self.items[right_child] > self.items[largest]:
largest = right_child
# 자식들이 나보다 작으면 멈춤
if largest == cur_index:
break
# 더 큰 자식과 교체
self.items[cur_index], self.items[largest] = self.items[largest], self.items[cur_index]
cur_index = largest
return max_valPriority Queue
큐는 먼저 들어오는 데이터가 먼저 나가는 구조였다면, 우선순위 큐는 먼저 들어오는 데이터가 아니라, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료 구조이다. 우선 순위 큐는 힙으로 구현하는 것이 가장 효율적이다.
- 배열, 연결리스트 삽입/삭제 시간복잡도: O(n)
- 힙의 삽입/삭제 시간복잡도: O(log2n) - 완전 이진트리 구조라서
우선순위 큐 = 개념
힙 = 구현체
Priority Queue vs Heapq
Priority Queue는 Thread Safe하고 Heque는 Non Safe하다.
Thread Safe는 thread가 동시에 데이터를 읽고 쓰는 상황에서, 데이터가 손상되지 않도록 안전하게 보호하는 것
-> 코딩테스트 환경에서는 대부분 싱글 스레드 환경이므로 Thread Safe를 신경쓰지말고, 속도를 위해 heapq를 사용하자.
파이썬 - heapq 사용하기
heapq는 별도의 자료구조 클래스를 제공하지 않고, 일반 리스트를 힙처럼 다루도록 메서드를 제공하는 방식이다.
heap = "리스트 + 힙 연산 메서드"
1. heapq 메서드
- heapq.heappush(heap, item)
: 최소힙 자료구조 특성을 유지한 채로 item 값을 heap에 추가. 가장 작은 값이 루트(heap[0])에 위치- heapq.heappop(heap)
: 최소힙 자료구조 특성을 유지한 채로 heap의 첫 번째 요소를 삭제 후 반환- heapq.heapify(list)
: 기존에 존재하는 리스트를 받아 Heap 구조로 변환heap = [] heapq.heappush(heap, 5) heapq.heappush(heap, 1) heapq.heappush(heap, 3) print(heap) print(heapq.heappop(heap)) print(heapq.heappop(heap)) print(heapq.heappop(heap)) 결과 [1, 5, 3] 1 3 52. 최대힙 구현하기
heapq는 기본적으로 최소힙 구조를 가지므로 이를 응용해서 최대힙을 구현해야한다. 각 값들에 마이너스(-)를 취한 후 heap에 넣은 뒤 heappop으로 빼낸 값에 다시 - 를 취해주면 최대값을 구할 수 있다.
import heapq heap = [] heapq.heappush(heap, -5) # heap = [-5] heapq.heappush(heap, -1) # heap = [-5, -1] (내부적으로 최소 힙 유지) heapq.heappush(heap, -3) # heap = [-5, -1, -3] print(-heapq.heappop(heap)) # -(-5) → 5 print(-heapq.heappop(heap)) # -(-3) → 3 print(-heapq.heappop(heap)) # -(-1) → 1 즉, heapq는 원래 최소 힙이지만, 우리가 값을 넣을 때 - 부호를 붙여 넣고, 뺄 때 다시 -를 붙여주면 결과적으로 최대 힙처럼 동작하는 것이다.
-
힙이란 자료구조에, 숫자만 넣는 것이 아니다. (우선순위, 값)쌍이나 자료구조도 넣는 경우가 많다.
-
heapq는 튜플을 넣으면 첫 번째 원소 기준으로 정렬합니다.
import heapq
heap = []
heapq.heappush(heap, (1, "apple"))
heapq.heappush(heap, (3, "banana"))
heapq.heappush(heap, (2, "cherry"))
print(heapq.heappop(heap)) # (1, 'apple')
