Python에서 최소 힙 구현
트리는 요소가 여러 수준으로 배열된 비선형 데이터 구조입니다. 힙은 트리를 기반으로 하는 데이터 구조입니다.
모든 부모 노드에는 두 개의 자식 노드가 있음을 의미하는 완전한 이진 트리입니다. 힙은 다른 알고리즘을 구현하고, 다른 구조를 정렬하고, 대기열의 우선 순위를 지정하는 등의 작업을 수행합니다.
힙에는 최대 및 최소의 두 가지 유형이 있습니다. 이는 상위 노드와 비교하여 하위 노드의 값을 기반으로 합니다.
이 튜토리얼에서는 Min Heap과 Python에서의 구현에 대해 설명합니다.
Python의 최소 힙
모든 상위 노드는 최소 힙의 하위 노드보다 작거나 같습니다. 오름차순을 따르며 항상 작은 노드가 우선 순위입니다.
주어진 노드 n의 경우 왼쪽 자식은 2n+1에 있고 오른쪽은 2n+2에 있습니다.
다음 이미지를 참조하십시오.
Python에서 Min Heap은 두 가지 방법으로 구현할 수 있습니다. 이에 대해서는 아래에서 설명합니다.
Python에서 최소 힙을 구현하는 클래스 만들기
Python에서 Min Heap을 구현하는 클래스를 만들 수 있습니다. 힙 크기로 클래스 개체를 시작하고 요소 삽입 프로세스를 수행하고 해당 인덱스에 매핑하는 메서드를 정의합니다.
예:
import sys
class min_heap:
def __init__(self, size):
self.storage = [0] * size
self.size = size
self.heap_size = 0
self.Heap = [0] * (self.size + 1)
self.Heap[0] = sys.maxsize * -1
self.parent = 1
self.root = 1
def parent_idx(self, idx):
return (idx - 1) // 2
def lf_child_idx(self, idx):
return 2 * idx + 1
def rt_child_idx(self, idx):
return 2 * idx + 2
def has_parent(self, idx):
return self.parent_idx(idx) >= 0
def insert(self, idx):
if self.heap_size >= self.size:
return
self.heap_size += 1
self.Heap[self.heap_size] = idx
heap = self.heap_size
while self.Heap[heap] < self.Heap[heap // 2]:
self.swap(heap, heap // 2)
heap = heap // 2
def swap(self, left, right):
self.Heap[left], self.Heap[right] = self.Heap[right], self.Heap[left]
def print_heap(self):
for i in range(1, (self.heap_size // 2) + 1):
print(
"Parent:",
str(self.Heap[i]),
"Lt: " + str(self.Heap[2 * i]),
"Rt: ",
str(self.Heap[2 * i + 1]),
)
min_heap = min_heap(10)
min_heap.insert(5)
min_heap.insert(1)
min_heap.insert(8)
min_heap.insert(2)
min_heap.insert(3)
min_heap.insert(7)
min_heap.insert(9)
min_heap.insert(6)
min_heap.insert(10)
min_heap.print_heap()
출력:
Parent: 1 Lt: 2 Rt: 7
Parent: 2 Lt: 5 Rt: 3
Parent: 7 Lt: 8 Rt: 9
Parent: 5 Lt: 6 Rt: 10
insert() 메서드는 요소를 힙에 추가합니다. 요소의 인덱스와 순서는 rt_child_index() 및 lt_child_index() 함수를 사용하여 부모 노드의 값을 기준으로 자식 노드의 수준을 조정하는 swap() 메서드를 사용하여 관리됩니다.
최소 힙은 클래스의 print_heap() 함수를 사용하여 반복되고 순서대로 표시됩니다.
heapq 모듈을 사용하여 Python에서 최소 힙 구현
Python은 다른 클래스를 만들지 않고 힙 데이터 구조를 구현할 수 있는 heapq 모듈을 제공합니다. 이 모듈은 최소 힙 구조를 유지하기 위해 매번 힙의 가장 작은 요소가 팝되도록 합니다.
목록을 사용하여 힙의 노드를 유지 관리합니다. heappush() 함수를 사용하여 요소를 추가하고 그에 따른 순서를 유지하여 Min Heap의 구조가 유지되도록 합니다.
heappop()은 힙에서 가장 작은 요소인 루트 노드를 팝합니다.
예:
import heapq as heap
lst = []
heap.heappush(lst, 7)
heap.heappush(lst, 1)
heap.heappush(lst, 5)
heap.heappush(lst, 4)
heap.heappush(lst, 8)
heap.heappush(lst, 3)
print("Heap: ", lst)
print("Parent Node: ", heap.heappop(lst))
print("Child Nodes: ", lst)
출력:
Heap: [1, 4, 3, 7, 8, 5]
Parent Node: 1
Child Nodes: [3, 4, 5, 7, 8]
위의 예에서는 힙을 유지하기 위해 lst 목록을 사용했습니다. 요소가 추가되고 heappush() 함수로 순서가 자동으로 조정됩니다.
최소 힙이 표시됩니다. 상위 노드는 heappop() 메서드를 사용하여 팝되고 표시됩니다.
나머지 자식 노드는 부모 노드를 제거한 후에도 표시됩니다.
Manav is a IT Professional who has a lot of experience as a core developer in many live projects. He is an avid learner who enjoys learning new things and sharing his findings whenever possible.
LinkedIn