정의
큐나 스택처럼 추상 자료형(내부적인 구현보다 기능에 집중하게 함)
저장한 데이터가 우선순위 순서대로 나오는 구조
ex) 우선순위가 높은 데이터를 처리할때, 고객문의 처리(불만도가 높은, 고객의 등급이 가장 높은), 가장 큰 값부터 출력
연산
1. 힙의 마지막 인덱스에 데이터를 삽입
2. 삽입한 데이터와 부모 노드의 데이터를 비교
3. 부모 노드의 데이터가 더 작으면 둘의 위치를 바꿔준다.
구현
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 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) # 삽입된 노드를 대상으로 다시 reverse_heapify 호출
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 __str__(self):
return str(self.heap)
# 테스트 코드
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)
힙에서 데이터를 추출 - (우선순위가 높은 데이터를 추출)
1. root 노드와 마지막 노드를 서로 바꿔 준다.
2. 마지막 노드의 데이터를 변수에 저장해 준다.
3. 마지막 노드를 삭제한다.
4. root 노드에 heapify를 호출해서 망가진 힙 속성을 고친다.
5. 변수에 저장한 데이터를 리턴한다. (최고 우선순위 데이터)
구현
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) # root 노드와 마지막 노드의 위치 바꿈
max_value = self.heap.pop() # 힙에서 마지막 노드 추출(삭제)해서 변수에 저장
heapify(self.heap, 1, len(self.heap)) # 새로운 root 노드를 대상으로 heapify 호출해서 힙 속성 유지
return max_value # 최우선순위 데이터 리턴
def __str__(self):
return str(self.heap)
# 출력 코드
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.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())
힙의 삽입 연산 시간 복잡도 - O(lg(n))
1. 힙의 마지막 인덱스에 노드를 삽입
동적배열로 구현하므로 O(1)
2. 삽입된 노드의 값과 부모 노드의 값을 비교 - O(1)
삽입된 데이터가 더 큰 경우 부모 노드와의 위치를 변경 - O(1)
즉, O(2) -> O(1)
3. 최악의 경우 leaf 노드에서 root 까지 가야하므로 힙의 높이만큼 반복 - O(lg(n))
힙의 추출 연산 시간 복잡도 - O(lg(n))
1. root 노드와 마지막 노드의 위치를 변경 - O(1)
2. 마지막 위치로 간 원래 root 노드의 데이터를 별도 변수에 저장하고, 노드는 힙에서 지운다. - O(1)
3. 새로운 root 노드를 대상으로 heapify 해서 망가진 힙 속성을 복원 - O(lg(n))
4. 2에서 따로 저장해 둔 최우선순위 데이터를 리턴 - O(1)