1. 힙이란?
힙(Heap)
- 다음 두 가지 속성을 만족하는 트리
- 형태 속성: 완전 이진 트리다
- 힙 속성: 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 같다(max heap) 혹은 작거나 같다(min heap)
- 뒤에 나오는 내용은 max heap에 대한 내용을 다뤘다.
2. 힙 만들기
heapify 알고리즘
- 힙 속성을 만족하도록 하나의 노드를 재배치하는 알고리즘
def swap(tree, index_1, index_2):
"""완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다"""
temp = tree[index_1]
tree[index_1] = tree[index_2]
tree[index_2] = temp
def heapify(tree, index, tree_size):
"""heapify 함수"""
left_child_index = 2 * index
right_child_index = 2 * index + 1
largest = index # 일단 부모 노드의 값이 가장 크다고 설정
# 왼쪽 자식 노드의 값과 비교
if 0 < left_child_index < tree_size and tree[largest] < tree[left_child_index]:
largest = left_child_index
# 오른쪽 자식 노드의 값과 비교
if 0 < right_child_index < tree_size and tree[largest] < tree[right_child_index]:
largest = right_child_index
if largest != index:
swap(tree, index, largest)
heapify(tree, largest, tree_size)
tree = [None, 15, 5, 12, 14, 9, 10, 6, 2, 11, 1] # heapify하려고 하는 완전 이진 트리
heapify(tree, 2, len(tree)) # 노드 2에 heapify 호출
print(tree)[None, 15, 14, 12, 11, 9, 10, 6, 2, 5, 1]4. 정렬 문제
정렬(Sort)
- 여러 개의 데이터 요소들을 특정 순서로 배치하는 것
- 정렬 알고리즘으로 삽입 정령, 선택 정렬, 퀵 정렬, 합병 정령, 힙 정렬 등이 있다.
힙 정렬(Heapsort)
- 힙을 만든다 (O(n))
- root와 마지막 노드를 바꾸고 알고리즘 내에서 사용할 배열의 크기를 1만큼 줄인다. (O(1))
- 새로운 루트 노드로 heapify 함수를 호출한다. (O(log(n)))
- 알고리즘 내의 배열의 크기가 1이 아닌 경우 2단계로 이동한다.
def swap(tree, index_1, index_2):
"""완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다"""
temp = tree[index_1]
tree[index_1] = tree[index_2]
tree[index_2] = temp
def heapify(tree, index, tree_size):
"""heapify 함수"""
# 왼쪽 자식 노드의 인덱스와 오른쪽 자식 노드의 인덱스를 계산
left_child_index = 2 * index
right_child_index = 2 * index + 1
largest = index # 일단 부모 노드의 값이 가장 크다고 설정
# 왼쪽 자식 노드의 값과 비교
if 0 < left_child_index < tree_size and tree[largest] < tree[left_child_index]:
largest = left_child_index
# 오른쪽 자식 노드의 값과 비교
if 0 < right_child_index < tree_size and tree[largest] < tree[right_child_index]:
largest = right_child_index
if largest != index: # 부모 노드의 값이 자식 노드의 값보다 작으면
swap(tree, index, largest) # 부모 노드와 최댓값을 가진 자식 노드의 위치를 바꿔준다
heapify(tree, largest, tree_size) # 자리가 바뀌어 자식 노드가 된 기존의 부모 노드를대상으로 또 heapify 함수를 호출한다
def heapsort(tree):
"""힙 정렬 함수"""
tree_size = len(tree)
for i in range(tree_size - 1, 0, -1):
heapify(tree, i, tree_size)
while tree_size > 1:
tree_size = tree_size - 1
swap(tree, 1, tree_size)
heapify(tree, 1, tree_size)
# test
data_to_sort = [None, 6, 1, 4, 7, 10, 3, 8, 5, 1, 5, 7, 4, 2, 1]
heapsort(data_to_sort)
print(data_to_sort)[None, 1, 1, 1, 2, 3, 4, 4, 5, 5, 6, 7, 7, 8, 10]- Worst-case time complexity: O(nlog(n))
- Best-case time complexity: O(nlog(n))(distict keys) or O(n)(equal keys)
- Average time complexity: O(nlog(n))
- Worst-case space complexity: O(n) (total) O(1) (auxliary)
- 다른 정렬 알고리즘들과의 비교 참조
5. 우선순위 큐
우선순위 큐(Priority Queue)
- 우선 순위가 높은 요소부터 순서대로 나오는 큐
- 힙을 사용하면 우선순위 큐를 효율적으로 구현할 수 있다.
6. 우선순위 큐 데이터 다루기
힙에 데이터 삽입하기
- 힙의 마지막 노드(인덱스)로 새 데이터를 삽입하고 siftup heapify시킨다.
- Worst-case time complexity: O(log(n))
- Best-case time complexity: O(1)
- Average time complexity: O(log(n))
- Worst-case space complexity: O(1)
힙에서 최고 우선순위 데이터 추출하기
- 루트 노드와 마지막 노드를 바꾼다. (O(1))
- 마지막 노드를 추출한다. (O(1))
- 루트 노드를 siftdown heapify시킨다. O(log(n))
- 최고 우선순위 데이터를 변수에 저장했다가 heapify가 완료되면 그 변수를 리턴하는 식으로 구현한다.
- Worst-case time complexity: O(log(n))
- Best-case time complexity: O(1)
- Average time complexity: O(log(n))
- Worst-case space complexity: O(1)
def swap(tree, index_1, index_2):
"""완전 이진 트리의 노드 index_1과 노드 index_2의 위치를 바꿔준다"""
temp = tree[index_1]
tree[index_1] = tree[index_2]
tree[index_2] = temp
def heapify(tree, index, tree_size):
"""heapify 함수"""
left_child_index = 2 * index
right_child_index = 2 * index + 1
largest = index # 일단 부모 노드의 값이 가장 크다고 설정
# 왼쪽 자식 노드의 값과 비교
if 0 < left_child_index < tree_size and tree[largest] < tree[left_child_index]:
largest = left_child_index
# 오른쪽 자식 노드의 값과 비교
if 0 < right_child_index < tree_size and tree[largest] < tree[right_child_index]:
largest = right_child_index
if largest != index:
swap(tree, index, largest)
heapify(tree, largest, tree_size)
def reverse_heapify(tree, index):
"""삽입된 노드를 힙 속성을 지키는 위치로 이동시키는 함수"""
parent_index = index // 2
if 0 < parent_index < len(tree) and tree[index] > tree[parent_index]:
swap(tree, index, parent_index)
reverse_heapify(tree, parent_index)
class PriorityQueue:
"""힙으로 구현한 우선순위 큐"""
def __init__(self):
self.heap = [None] # 파이썬 리스트로 구현한 힙
def insert(self, data):
"""삽입 메소드"""
self.heap.append(data)
reverse_heapify(self.heap, len(self.heap)-1)
def extract_max(self):
"""최우선순위 데이터 추출 메소드"""
swap(self.heap, 1, len(self.heap) - 1)
max_value = self.heap.pop()
heapify(self.heap, 1, len(self.heap))
return max_value
def __str__(self):
return str(self.heap)
# test
priority_queue = PriorityQueue()
priority_queue.insert(6)
priority_queue.insert(9)
priority_queue.insert(1)
priority_queue.insert(3)
priority_queue.insert(10)
priority_queue.insert(11)
priority_queue.insert(13)
print(priority_queue)
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue.extract_max())
print(priority_queue)[None, 13, 9, 11, 3, 6, 1, 10]
13
11
10
9
6
3
1
[None]7. 힙으로 구현한 우선순위 큐 평가
- 정렬된 동적 배열, 정렬된 더블리 링크드 리스트로 우선순위 큐를 구현할 수 있다.
정렬된 동적 배열
- 삽입
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average time complexity:
- Worst-case space complexity:
- 추출
- Worst-case time complexity: O(1)
- Best-case time complexity: O(1)
- Average time complexity: O(1)
- Worst-case space complexity: O(1)
정렬된 더블리 링크드 리스트
- 삽입
- Worst-case time complexity: O(n)
- Best-case time complexity: O(1)
- Average time complexity:
- Worst-case space complexity:
- 추출
- Worst-case time complexity: O(1)
- Best-case time complexity: O(1)
- Average time complexity: O(1)
- Worst-case space complexity: O(1)
결론
- 정렬된 동적 배열/더블리 링크드 리스트를 사용하면 데이터를 추출할 때 더 효율적이다.
- 힙을 사용하면 데이터를 삽입할 때 더 효율적이다.
Feedback
- 힙 빌딩 시간 복잡도 글을 번역하고 분석해보자.
- 힙 정렬 시간 복잡도를 분석해보자.
- 언어별로 힙을 구현해보자.
- 힙으로 추상 자료형을 구현해보자.
- 마지막 average랑 space 아직 못구했다
참고 자료
job's done