코딩 테스트 (Python)/문법
[문법] 힙(heapq) 개념 및 구현(Python)
hihyuk
2024. 1. 6. 09:39
힙이란?
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
항상 최대/최소의 값들이 필요한 연산이 있는 경우
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조
부모 노드의 값이 자식 노드의 값보다 항상 큼
가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 간다. 따라서 최대의 값들을 빠르게 구할 수 있게 된다.
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 힙이라고 한다.
- BST(이진탐색트리)와 다르다. 좌, 우 자식의 위치가 대소관계를 반영하지 않음.
- 계산 편의를 위해 인덱스는 1부터 사용한다. (parent: x, left: 2x, right: 2x+1)
최대 힙 - 삽입 알고리즘
힙의 규칙
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 한다.
따라서, 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 한다.
원소를 추가하는 방법
1. 원소를 맨 마지막에 넣는다.
2. 그리고 부모 노드와 비교한다. 만약 더 크다면 자리를 바꾼다.
3. 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 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
최대 힙 - 삽입 시간복잡도
힙은 원소를 맨 밑에 넣어서 꼭대기까지 비교하면서 올리고 있다.
완전 이진트리의 최대 높이는 O(log(N))이기 때문에 반복하는 최대 횟수도 O(log(N)) 이다.
즉 맥스 힙의 원소 추가는 O(log(N)) 만큼의 시간 복잡도를 가진다.
최대 힙 - 추출 알고리즘
최대 힙에서 원소를 추출하는 방법은 최댓값, 루트 노드를 삭제하는 것이다.
스택과 같이 맨 위에 있는 원소만 제거할 수 있고, 다른 위치의 노드를 삭제할 수는 없다.
또한 맥스 힙에 원소를 추가했던 것과 마찬가지로 원소를 삭제할때도 힙의 규칙이 지켜져야 한다.
1. 루트 노드와 맨 끝에 있는 원소를 교체한다.
2. 맨 뒤에 있는 원소를 (원래 루트 노드)를 삭제한다.
3. 변경된 노드와 자식 노드들을 비교한다. 두 자식 중 더 큰 자식과 비교해서 자신보다 자식이 더 크다면 자리를 바꾼다.
4. 자식 노드 둘 보다 부모 노드가 크거나 가장 바닥에 도달하지 않을 때까지 3. 과정을 반복한다.
5. 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
7 6 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을 반환
최대 힙 - 추출 시간복잡도
결국 원소를 맨 위에 올려서 바닥까지 비교하면서 내리고 있다.
완전 이진트리의 최대 높이는 O(log(N)) 이기 때문에 반복하는 최대 횟수도 O(log(N)) 이다.
즉 맥스 힙의 원소 삭제는 O(log(N)) 만큼의 시간 복잡도를 가진다.
힙을 이용한 문제 풀이 (Python)
리트코드 215
class BinaryMaxHeap:
def __init__(self):
self.items = [None]
def __len__(self):
return len(self.items) - 1
def _percolate_up(self):
cur = len(self)
parent = cur // 2
while parent > 0:
if self.items[cur] > self.items[parent]:
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]
cur = parent
parent = cur // 2
def _percolate_down(self, cur):
biggest = cur
left = 2 * cur
right = 2 * cur + 1
if left <= len(self) and self.items[left] > self.items[biggest]:
biggest = left
if right <= len(self) and self.items[right] > self.items[biggest]:
biggest = right
if biggest != cur:
self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
self._percolate_down(biggest)
def insert(self, k):
self.items.append(k)
self._percolate_up()
def extract(self):
if len(self) < 1:
return None
root = self.items[1]
self.items[1] = self.items[-1]
self.items.pop()
self._percolate_down(1)
return root
한 줄씩 코드 해석해보기
def __init__(self):
self.items = [None]- 배열의 첫번째 값을 None으로 만들어 준다.
- 계산 편의를 위해 0이 아닌 1번째 인덱스부터 사용한다.
def __len__(self):
return len(self.items) - 1- len() 연산을 가능하게 하는 매직 메서드 덮어쓰기(Override).
- 첫번째 값에 None을 넣어놨기 때문에 길이를 출력할 때 -1을 해주는 메서드
def _percolate_up(self):
cur = len(self)
parent = cur // 2- 전체 길이를 구한 후 cur에 넣어준다.
- left 라면 2*cur, right 라면 2*cur + 1 이므로 parent 는 항상 cur // 2
while parent > 0:
if self.items[cur] > self.items[parent]:
self.items[cur], self.items[parent] = self.items[parent], self.items[cur]- 부모의 위치가 0이 되기 전까지 계속 반복한다.
- 나의 값이 부모의 값보다 큰 경우 위치를 바꾼다.
cur = parent
parent = cur // 2- 나의 위치를 부모의 위치로 바꾼 후 부모의 값을 다시 계산 후 while문 반복
def _percolate_down(self, cur):
biggest = cur
left = 2 * cur
right = 2 * cur + 1- 현재 위치를 받고 biggest에 넣어준다.
- 내 위치의 왼쪽 요소와 오른쪽 요소의 값을 넣어준다.
if left <= len(self) and self.items[left] > self.items[biggest]:
biggest = left
if right <= len(self) and self.items[right] > self.items[biggest]:
biggest = right- 인덱스 값이 범위안에 있고
- 왼쪽 요소가 부모보다 크다면 가장 큰 요소에 왼쪽 값을 넣어준다.
- 오른쪽 요소가 부모보다 크다면 가장 큰 요소에 오른쪽 값을 넣어준다.
if biggest != cur:
self.items[cur], self.items[biggest] = self.items[biggest], self.items[cur]
self._percolate_down(biggest)- 만약 biggest에 저장된 값이 나의 값이 아니라면
- 가장 큰 요소의 위치와 나의 위치를 바꾼 후 percolate_down을 다시 실행한다.
def insert(self, k):
self.items.append(k)
self._percolate_up()- items 리스트 안에 전달 받은 요소를 마지막에 넣는다
- percolate_up()을 통해 힙의 구조를 만들어준다.
def extract(self):
if len(self) < 1:
return None- 배열의 길이가 1보다 작으면 추출할 것이 없기 때문에 None을 반환한다.
root = self.items[1]
self.items[1] = self.items[-1]
self.items.pop()
self._percolate_down(1)
return root- root에 첫번째 값을 가져온다.
- 루트와 제일 마지막에 있는 요소와 값을 바꾼 후
- pop을 통해 마지막으로 온 root를 제거한다.
- percolate_down(1)을 통해 힙의 구조를 만들어준다.
- 1을 넣어준 이유는 root부터 살펴 보기 위함이다.
- 모든 실행이 끝난 후 root를 반환한다.
from heap.structures import BinaryMaxHeap
def test_maxheap_we_made(lst, k):
maxheap = BinaryMaxHeap()
for elem in lst:
maxheap.insert(elem)
return [maxheap.extract() for _ in range(k)][k - 1]