root node
가 leaf node
까지 가는 경우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
if left_child_index < tree_size and right_child_index < tree_size:
top_of_fam = max(tree[index], tree[left_child_index], tree[right_child_index])
if top_of_fam is tree[left_child_index]:
swap(tree, index, left_child_index)
heapify(tree, left_child_index, tree_size)
elif top_of_fam is tree[right_child_index]:
swap(tree, index, right_child_index)
heapify(tree, right_child_index, 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]
leaf node
부터 heapify
에 대입root node
의 heapify
를 호출할 차례, 밑에 모든 노드들은 힙 속성을 지키고 있음heapify
를 호출하는 건 heapify
를 개의 노드에 모두 호출leaf node
부터 heapify
)root node
와 마지막 노드를 바꿔준다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) # 자리가 바뀌어 자식 노드가 된 기존의 부모 노드를대상으로 또 heapify 함수를 호출한다
def heapsort(tree):
"""힙 정렬 함수"""
tree_size = len(tree)
for i in range(tree_size,0,-1):
heapify(tree, i, tree_size)
for j in range(tree_size-1,0,-1):
swap(tree, 1, j)
heapify(tree, 1, j)
# 실행 코드
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]
➡ =
정렬 알고리즘 | 시간 복잡도 |
---|---|
선택 정렬 | |
삽입 정렬 | |
합병 정렬 | |
퀵 정렬 | 평균 최악 |
힙 정렬 |
👉 힙 정렬은 선택 정렬과 삽입 정렬보다는 좋고, 합병 정렬과 퀵 정렬과는 비슷한 성능
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 # 삽입된 노드의 부모 노드의 인덱스 계산
largest = parent_index
if 0 < parent_index < len(tree) and tree[parent_index] < tree[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 __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)
# [None, 13, 9, 11, 3, 6, 1, 10]
from heapify_code import *
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[-1]
self.heap.pop()
heapify(self.heap, 1, len(self.heap))
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())
# 13
# 11
# 10
# 9
# 6
# 3
# 1
👉
👉
데이터 삽입 | 데이터 추출 | |
---|---|---|
정렬된 동적 배열 | ||
정렬된 더블리 링크드 리스트 | ||
힙 |
👉 정렬된 동적 배열, 더블리 링크드 리스트를 사용하면 데이터를 추출할 때 더 효율적
👉 힙을 사용하면 데이터를 삽입할 때 더 효율적