힙, 우선순위큐 는 완전 이진 트리 임
그래서
왼쪽 자식 index: 2*i
오른쪽 자식 index: 2*i +1
부모 index = i/2
단 행렬에서, index 는 1부터..
leftChild of i = heap[2 * i]
rightChild of i = heap[(2 * i) + 1]
parent of i = heap[i // 2]
힙(Heap)의 종류
힙에는 크게 두 가지 유형이 있습니다:
- 최소 힙 (Min Heap):
- 루트 노드에 가장 작은 값이 위치합니다.
- 가장 작은 값이 우선순위가 가장 높으며, 가장 먼저 제거됩니다.
- 최대 힙 (Max Heap):
- 루트 노드에 가장 큰 값이 위치합니다.
- 가장 큰 값이 우선순위가 가장 높으며, 가장 먼저 제거됩니다.
이번 내용에서는 **최소 힙(Min Heap)**에 초점을 맞추지만, 최대 힙(Max Heap)의 구현도 동일합니다.
단, 최소 값 대신 최대 값을 우선 처리하도록 변경하면 됩니다.
힙의 속성
힙은 이진 트리(Binary Tree)의 일종이며, 다음 두 가지 주요 속성을 만족해야 합니다:
1. 구조 속성 (Structure Property)
- 힙은 **완전 이진 트리(Complete Binary Tree)**여야 합니다.
- 완전 이진 트리는 모든 레벨의 노드가 왼쪽에서 오른쪽으로 연속적으로 채워지는 구조입니다.
- 단, 가장 마지막 레벨은 비어 있을 수 있지만, 이는 왼쪽에서 오른쪽으로 채워진 경우에만 가능합니다.
2. 순서 속성 (Order Property)
- 최소 힙(Min Heap):
- 각 노드의 값은 자식 노드의 값보다 작거나 같아야 합니다.
- 즉, 루트 노드의 값이 y라면, 오른쪽과 왼쪽 서브트리의 모든 노드 값은 y보다 크거나 같아야 합니다.
- 이 속성은 재귀적으로 모든 하위 트리에도 적용됩니다.
- 최대 힙(Max Heap):
- 각 노드의 값은 자식 노드의 값보다 크거나 같아야 합니다.
- 즉, 루트 노드의 값이 y라면, 오른쪽과 왼쪽 서브트리의 모든 노드 값은 y보다 작거나 같아야 합니다.
3. 중복 값 허용
- 힙은 이진 탐색 트리(Binary Search Tree)와 달리, 중복 값을 허용합니다.
요약
- 최소 힙과 최대 힙은 각각 루트 노드에 가장 작은 값 또는 가장 큰 값을 유지합니다.
- 힙은 완전 이진 트리 구조를 가지며, 각 노드가 자식 노드와 비교했을 때 순서를 만족해야 합니다.
- 중복 값이 허용되며, 데이터 정렬 및 우선순위 큐 구현에 자주 사용됩니다.
구현
class Heap:
"""
leftChild of i = heap[2 * i]
rightChild of i = heap[(2 * i) + 1]
parent of i = heap[i // 2]
"""
def __init__(self):
self.heap = [0]추가 (Push)
데이터 쌓는 self.heap 변수는 stack 이지만.
데이터 넣고,
- leftChild of i = heap[2 * i]
- rightChild of i = heap[(2 * i) + 1]
- parent of i = heap[i // 2]
이렇게..데이터 정렬을 함 swap 을 사용해서!!
삭제 (Pop)
일단,
- self.heap 개수가 1개 이면, 데이터가 없는 거임. 왜냐? self.heap[0] 에는 아무것도 사용하지 않음
- self.heap 개수가 2개 이면, 데이터가 1개 있는 것임. 그래서, self.heap.pop()
- 아니면, (self.heap 개수가 3개 이상, 즉 실제로 2개 이상 있으면)
-> root 에 있는 min heap 또는 max heap 을 삭제 해야 함
그러나, 실제로는
마지막 값을 삭제하면서, root 로 덮어씀.. 그럼 root 가 삭제되는 상황임.
self.heap[1] = self.heap.pop()
그리고, self.heap 를 index 1 부터.. 전체를 순회하면서,
부모보다 자식 값을 비교하면서 ordering 정렬 진행 (swap 로직)
min heap 삭제 (Pop)
max heap 삭제 (Pop)
# Min Heap
class Heap:
def __init__(self):
self.heap = [0]
def push(self, val):
self.heap.append(val)
i = len(self.heap) - 1
# Percolate up
while i > 1 and self.heap[i] < self.heap[i // 2]:
tmp = self.heap[i]
self.heap[i] = self.heap[i // 2]
self.heap[i // 2] = tmp
i = i // 2
def pop(self):
if len(self.heap) == 1:
return None
if len(self.heap) == 2:
return self.heap.pop()
res = self.heap[1]
# Move last value to root
self.heap[1] = self.heap.pop()
i = 1
# Percolate down
while 2 * i < len(self.heap):
if (2 * i + 1 < len(self.heap) and
self.heap[2 * i + 1] < self.heap[2 * i] and
self.heap[i] > self.heap[2 * i + 1]):
# Swap right child
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i + 1]
self.heap[2 * i + 1] = tmp
i = 2 * i + 1
elif self.heap[i] > self.heap[2 * i]:
# Swap left child
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i]
self.heap[2 * i] = tmp
i = 2 * i
else:
break
return res
def top(self):
if len(self.heap) > 1:
return self.heap[1]
return None
def heapify(self, arr):
# 0-th position is moved to the end
arr.append(arr[0])
self.heap = arr
cur = (len(self.heap) - 1) // 2
while cur > 0:
# Percolate down
i = cur
while 2 * i < len(self.heap):
if (2 * i + 1 < len(self.heap) and
self.heap[2 * i + 1] < self.heap[2 * i] and
self.heap[i] > self.heap[2 * i + 1]):
# Swap right child
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i + 1]
self.heap[2 * i + 1] = tmp
i = 2 * i + 1
elif self.heap[i] > self.heap[2 * i]:
# Swap left child
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i]
self.heap[2 * i] = tmp
i = 2 * i
else:
break
cur -= 1
삭제 (Pop) 로직 상세
def pop(self):
# 힙에 원소가 하나(인덱스 0의 더미 요소)만 있으면 None 반환
if len(self.heap) == 1:
return None
# 힙에 두 개의 원소(더미 + 하나의 값)만 있으면 마지막 값을 제거하고 반환
if len(self.heap) == 2:
return self.heap.pop()
# 루트 값(힙의 최우선값)을 저장해 반환할 준비
res = self.heap[1]
# 마지막 값을 루트 위치로 이동
self.heap[1] = self.heap.pop() # 마지막 요소를 제거하고 루트에 할당
# 루트 노드(인덱스 1)부터 시작
i = 1
# 힙 속성을 유지하기 위해 루트를 아래로 이동하며 자리 잡음
while 2 * i < len(self.heap): # 왼쪽 자식이 존재하는 동안 반복
# 오른쪽 자식이 존재하고, 왼쪽 자식보다 작으며 현재 노드보다 작으면
if (2 * i + 1 < len(self.heap) and
self.heap[2 * i + 1] < self.heap[2 * i] and
self.heap[i] > self.heap[2 * i + 1]):
"""
1. 2 * i + 1 < len(self.heap)
- 현재 노드(i)의 오른쪽 자식이 힙의 범위 안에 존재하는지 확인합니다.
- 왼쪽 자식은 항상 2 * i로 계산되므로, 오른쪽 자식(2 * i + 1)이 존재하려면
전체 힙의 길이(len(self.heap))보다 작아야 합니다.
2. self.heap[2 * i + 1] < self.heap[2 * i]
- 오른쪽 자식의 값이 왼쪽 자식의 값보다 작은지 확인합니다.
- 최소 힙에서는 더 작은 값을 위로 올려야 하므로, 오른쪽 자식이 더 작다면
오른쪽 자식과 교체해야 합니다.
3. self.heap[i] > self.heap[2 * i + 1]
- 현재 부모 노드(i)의 값이 오른쪽 자식의 값보다 큰지 확인합니다.
- 최소 힙의 특성상, 부모 노드는 자식 노드보다 작아야 합니다.
- 만약 부모 노드가 오른쪽 자식보다 크다면, 최소 힙 속성을 위반한 것이므로
오른쪽 자식과 교체해야 합니다.
"""
# 오른쪽 자식과 교체
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i + 1]
self.heap[2 * i + 1] = tmp
# 오른쪽 자식으로 인덱스를 이동
i = 2 * i + 1
# 그렇지 않고 왼쪽 자식이 현재 노드보다 작으면
elif self.heap[i] > self.heap[2 * i]:
"""
- 현재 부모 노드(i)의 값이 왼쪽 자식(2 * i)의 값보다 큰지 확인합니다.
- 최소 힙의 특성상, 부모 노드는 자식 노드보다 작아야 합니다.
- 만약 부모 노드가 왼쪽 자식보다 크다면, 최소 힙 속성을 위반한 것이므로
왼쪽 자식과 교체해야 합니다.
"""
# 왼쪽 자식과 교체
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i]
self.heap[2 * i] = tmp
# 왼쪽 자식으로 인덱스를 이동
i = 2 * i
# 현재 부모 노드가 자식 노드보다 작거나 같다면
# 더 이상 교환할 필요가 없으므로 반복 종료
else:
"""
힙 속성이 복구된 상태:
- 부모 노드가 자식 노드들보다 작거나 같은 경우
- 부모 노드가 최소 힙의 규칙을 만족하므로 더 이상의 정렬 작업이 필요하지 않음
자식 노드가 없는 경우:
- 루프 조건인 2 * i < len(self.heap)가 만족되지 않으면 루프가 종료
"""
break # 힙 속성이 복원되었으므로 루프 종료
# 저장해둔 루트 값을 반환
return res
Heapify: build heap
def heapify(self, arr):
# 0-th position is moved to the end
arr.append(arr[0])
self.heap = arr
cur = (len(self.heap) - 1) // 2
while cur > 0:
# Percolate down
i = cur
while 2 * i < len(self.heap):
if (2 * i + 1 < len(self.heap) and
self.heap[2 * i + 1] < self.heap[2 * i] and
self.heap[i] > self.heap[2 * i + 1]):
# Swap right child
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i + 1]
self.heap[2 * i + 1] = tmp
i = 2 * i + 1
elif self.heap[i] > self.heap[2 * i]:
# Swap left child
tmp = self.heap[i]
self.heap[i] = self.heap[2 * i]
self.heap[2 * i] = tmp
i = 2 * i
else:
break
cur -= 1
Max Heap Heapify
'Coding Test > 알고리즘 이론' 카테고리의 다른 글
| 위상정렬(Topologcal Sort) (0) | 2025.01.27 |
|---|---|
| HashMap (0) | 2025.01.20 |
| 트리 종합 - leetcode (31) (0) | 2025.01.12 |
| 구간 트리 (Interval Trees) - leetcode (11) (0) | 2025.01.11 |
| 동적인 순서 통계 (Dynamic Order Statistics) - leetcode (8) (0) | 2025.01.11 |