heap구현, heapq사용법

알고리즘/자료구조

heap구현, heapq사용법

씩씩한 IT블로그 2020. 6. 16. 23:06

heap의종류 2가지

최대힙 : 부모노드가 자식노드보다 크거나 같음(root node에 최댓값)

최소힙: 부모노드가 자식노드보다 작거나 같음(root node에 최솟값)

< (최소)힙 알고리즘 >

* 직접 구현한 힙

# unsorted : heap으로 만들고자하는 리스트
# index : 아래로 내려가며 heap을 만들기 시작하는 노드 (해당 index의 자식노드들은 모두 heapify된다) 
def heapify(unsorted, index, heap_size):
    smallist = index
    left_index = 2 * index + 1
    right_index = 2 * index + 2
    if left_index < heap_size and unsorted[left_index] < unsorted[smallist]:
        smallist = left_index
    if right_index < heap_size and unsorted[right_index] < unsorted[smallist]:
        smallist = right_index
    if smallist != index:
        unsorted[smallist], unsorted[index] = unsorted[index], unsorted[smallist]
        heapify(unsorted, smallist, heap_size)

왼쪽 자식노드 -> 오른쪽 자식노드 순서대로 비교하여 (부모,왼쪽자식,오른쪽자식) 중 가장 작은 노드의 값을 구함. 이때 변화가 없으면 재귀를 종료하고, 변화가 있으면 변화된 자식노드로 내려가서 다시 재귀 시작.

파이썬 기본 라이브러리의 힙을 이용할땐 import heapq

* heapify (heapq.heapify(L) : 리스트 L을 heapfiy)

heap으로 구성된 tree는 리스트로 나타낼 수 있다.