[자료구조] 힙
1. 힙 (Heap) 이란?
- 힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
- 완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 - 힙을 사용하는 이유
- 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 $O(n)$ 이 걸림
- 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, $O(log{n})$ 이 걸림
- 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨
2. 힙의 구조
- 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음
- 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임
- 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
- 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음 - 완전 이진 트리 형태를 가짐
- 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
힙과 이진 탐색 트리의 공통점과 차이점
공통점
- 힙과 이진 탐색 트리는 모두 이진 트리임
차이점
- 힙은 부모 노드의 값이 자식 노드보다 크거나 같음 (Max Heap의 경우)
- 힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
- 힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음 - 이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
- 이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨
3. 힙 (Heap) 동작
- 데이터를 힙 구조에 삽입, 삭제하는 과정을 그림을 통해 선명하게 이해하기
힙에 데이터 삽입하기 - 기본 동작
- 힙은 완전 이진 트리이므로, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 삽입
힙에 데이터 삽입하기 - 삽입할 데이터가 힙의 데이터보다 클 경우 (Max Heap 의 예)
- 먼저 삽입된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐
- 채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함 (swap)
힙의 데이터 삭제하기 (Max Heap 의 예)
- 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임
- 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임 - 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드) 를 root 노드로 이동
- root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함 (swap)
- 루트 노드를 삭제한다
- 가장 최근에 들어온 노드(이후부터
latestNode라 명명한다)를 루트 노드로 올린다 latestNode와 그 아래 자식 노드들의 값을 비교한다- 셋 중에서
latestNode의 값이 가장 큰 값이 아니라면, 두 자식 중 더 큰 값을 가진 노드와latestNode를 swap 한다 latestNode가 자식 노드보다 큰 값일 때까지 (혹은 자식 노드가 더 이상 없을 때까지) 3~4번을 반복한다
4. 힙 구현
힙과 배열
- 일반적으로 힙 구현시 배열 자료구조를 활용함
- 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해 root 노드 인덱스 번호를 1로 지정하면 구현이 좀 더 수월함
아래와 같이 표현할 때,
P: 부모 노드 인덱스 번호LC: 왼쪽 자식 노드 인덱스 번호RC: 오른쪽 자식 노드 인덱스 번호
부모 노드의 인덱스 번호를 알 때 자식 노드를 구할 수 있고, 자식 노드의 인덱스 번호를 알 때 부모 노드를 구할 수 있다
P = LC // 2혹은P = RC // 2LC = P * 2RC = P * 2 + 1
프로그래밍 연습
힙 클래스 구현
데이터 삽입
class Heap:
def __init__(self,data):
self.heapArray = list()
self.heapArray.append(None) # 1번 인덱스부터 사용하기 위해
self.heapArray.append(data)
# 인덱스 번호가 insertedIdx인 노드와 부모 노드의 크기를 비교해 swap이 필요하면 True 반환
def moveUp(self,insertedIdx):
if insertedIdx <= 1: # 루트 노드와 같을 때
return False
parentIdx = insertedIdx // 2 # 부모의 인덱스 번호는 자식의 인덱스 번호를 2로 나눈 몫
if self.heapArray[insertedIdx] > self.heapArray[parentIdx]: # 자식 노드의 값이 부모 노드의 값보다 크면 swap 대상
return True
else:
return False
def insert(self,data):
# 방어코드
if len(self.heapArray) == 0:
self.heapArray.append(None)
self.heapArray.append(data)
return True
# 룰 1: 부모 노드와 크기 비교하지 않고 일단 왼쪽부터 차곡차곡 채움
self.heapArray.append(data) # append() 자체가 리스트의 맨 끝에 추가하기 때문에 1번 룰을 따름
# 룰 2: 부모 노드와 크기 비교해서 swap
insertedIdx = len(self.heapArray) - 1 # insertedIdx: 방금 들어간 데이터의 인덱스 번호 # 0번 인덱스에 None이 있으니 -1 해주어야 함
while self.moveUp(insertedIdx):
parentIdx = insertedIdx // 2
# 부모 노드와 자식 노드 swap # A와 B를 swap 하는 문법: A,B = B,A
self.heapArray[insertedIdx], self.heapArray[parentIdx] = self.heapArray[parentIdx], self.heapArray[insertedIdx]
# 부모 노드와 swap을 했으니 비교할 대상(insertedIdx)에도 부모 노드의 인덱스 번호를 대입
insertedIdx = parentIdx
return True
데이터 삽입 테스트 추가 설명
우선, 아래와 같은 룰으로 데이터를 삽입한다.
만약 15 -> 10 -> 8 -> 5 -> 4 -> 20 의 순서로 데이터를 삽입한다면,
insertedNode가 20일 때에만 moveUp()이 True를 반환할 것이다.
그럼 아래 사진과 같이 20보다 부모 노드의 값이 더 클 때까지 (혹은 20이 루트 노드가 될 때까지) swap 한다.
테스트에서 heapArray의 출력 결과가 아래와 같이 나왔는데,
이때 1번 인덱스는 루트노드이고, 2번 인덱스부터 두 개씩 묶어서 보면 된다. (아래 사진 참고)
힙에 데이터 삭제 구현 (Max Heap 예)
- 보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임
- 힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임 - 상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드) 를 root 노드로 이동
- root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함 (swap)
- 특정 노드의 관련 노드 위치 알아내기
- 부모 노드 인덱스 번호 (parent node’s index) = 자식 노드 인덱스 번호 (child node’s index) // 2
- 왼쪽 자식 노드 인덱스 번호 (left child node’s index) = 부모 노드 인덱스 번호 (parent node’s index) * 2
- 오른쪽 자식 노드 인덱스 번호 (right child node’s index) = 부모 노드 인덱스 번호 (parent node’s index) * 2 + 1
class Heap:
def __init__(self,data):
self.heapArray = list()
self.heapArray.append(None) # 1번 인덱스부터 사용하기 위해
self.heapArray.append(data)
# 자식노드 값과 비교하여 swap 해야하는지 판단 (swap 해야하면 True 반환)
def moveDown(self,popedIdx):
leftChildPopedIdx = popedIdx * 2 # 왼쪽 자식노드 인덱스 계산
rightChildPopedIdx = popedIdx * 2 + 1 # 오른쪽 자식노드 인덱스 계산
# case 1: 왼쪽 자식노드도 없을 때
if leftChildPopedIdx >= len(self.heapArray): # 예를들어 heapArray의 len이 3이라면 0번 인덱스 제외하고 데이터 2개 있는 것
return False
# case 2: 왼쪽 자식노드는 있고 오른쪽 자식노드만 없을 때
elif rightChildPopedIdx >= len(self.heapArray):
if self.heapArray[popedIdx] < self.heapArray[leftChildPopedIdx]: # 자식이 더 크니까 swap 해야함
return True
else:
return False
# case 3: 양쪽 자식노드 둘 다 있을 때
else:
# 자식노드끼리 값 비교
if self.heapArray[leftChildPopedIdx] > self.heapArray[rightChildPopedIdx]: # 왼쪽 자식노드가 더 큰 경우
if self.heapArray[popedIdx] < self.heapArray[leftChildPopedIdx]: # 왼쪽 자식노드와 부모노드 값 비교
return True
else:
return False
else: # 오른쪽 자식노드가 더 큰 경우
if self.heapArray[popedIdx] < self.heapArray[rightChildPopedIdx]: # 오른쪽 자식노드와 부모노드 값 비교
return True
else:
return False
def pop(self): # 맥스힙이라고 가정하면, 루트 노드를 반환하면 됨
# 방어코드
if len(self.heapArray) <= 1:
return None
res = self.heapArray[1] # res는 pop할 데이터 (루트노드 값)
self.heapArray[1] = self.heapArray[-1] # 마지막 데이터를 루트노드로 올리기
del self.heapArray[-1]
popedIdx = 1 # 루트노드의 인덱스이기 때문에 항상 1부터 시작
while self.moveDown(popedIdx): # True가 나오는 동안은 계속해서 swap 해주어야 함
leftChildPopedIdx = popedIdx * 2 # 왼쪽 자식노드 인덱스 계산
rightChildPopedIdx = popedIdx * 2 + 1 # 오른쪽 자식노드 인덱스 계산
# case 2: 왼쪽 자식노드는 있고 오른쪽 자식노드만 없을 때
if rightChildPopedIdx >= len(self.heapArray):
if self.heapArray[popedIdx] < self.heapArray[leftChildPopedIdx]: # 자식이 더 크니까 swap 해야함
self.heapArray[popedIdx], self.heapArray[leftChildPopedIdx] = self.heapArray[leftChildPopedIdx], self.heapArray[popedIdx]
popedIdx = leftChildPopedIdx # 바뀐 인덱스 번호 업데이트
# case 3: 양쪽 자식노드 둘 다 있을 때
else:
# 자식노드끼리 값 비교
if self.heapArray[leftChildPopedIdx] > self.heapArray[rightChildPopedIdx]: # 왼쪽 자식노드가 더 큰 경우
if self.heapArray[popedIdx] < self.heapArray[leftChildPopedIdx]: # 왼쪽 자식노드와 부모노드 값 비교
self.heapArray[popedIdx], self.heapArray[leftChildPopedIdx] = self.heapArray[leftChildPopedIdx], self.heapArray[popedIdx]
popedIdx = leftChildPopedIdx # 바뀐 인덱스 번호 업데이트
else: # 오른쪽 자식노드가 더 큰 경우
if self.heapArray[popedIdx] < self.heapArray[rightChildPopedIdx]: # 오른쪽 자식노드와 부모노드 값 비교
self.heapArray[popedIdx], self.heapArray[rightChildPopedIdx] = self.heapArray[rightChildPopedIdx], self.heapArray[popedIdx]
popedIdx = rightChildPopedIdx # 바뀐 인덱스 번호 업데이트
return res
moveDown()에서 고려해야할 경우의 수
- 자식 노드가 없는 경우
- 자식 노드가 1개인 경우
- 자식 노드가 2개인 경우 -> 1. 두 자식을 비교해 더 큰 값을 찾기 2. 그 값과 부모 노드의 값을 비교해 swap 할 지 판단
전체 테스트
위에서 구현한 삽입 코드와 함께 테스트를 진행한다.
pop()을 했을 때 정상적으로 루트노드 값(=20)이 나오는 것을 확인할 수 있다.
추가로, pop() 호출 이후에 heapArray를 출력해보면, 15가 루트노드로 정상적으로 재배치 되었음을 확인할 수 있다.
5. 힙 (Heap) 시간 복잡도
- depth (트리의 높이) 를 h라고 표기한다면, 총 h번 비교를 해야한다. ( =$O(h)$ )
- n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제 시,
최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 $h = log_{2}{n}$ 에 가까우므로, 시간 복잡도는 $O(h)$ = $O(log{n})$ 이다.
- 참고: 빅오 표기법에서 $log{n}$ 에서의 log의 밑은 10이 아니라, 2 이다.
- 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미한다.
💛 개인 공부 기록용 블로그입니다. 👻