[자료구조] Heap (힙) 이란?

December 2, 2020

Heap (힙) 이란?

완전 이진 트리의 일종의 자료구조 이다.

완전 이진 트리

위의 그림과 같이 node들이 부모 노드와 자식 노드간에 연결되어있는 node가 2개 초과하는 node들이 없는 형태를 완전 이진 트리 라고 한다.

종류

최소 힙 : 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리

최대 힙 : 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리

Python에는 리스트를 이용하여 heapq 라는 함수를 이용하여 리스트를 Heap과 같은 구조로 사용할 수 있다. heapq의 기본 설정은 최소 힙 이다.

예) 최소힙 삽입

import heapq as hq

a = []
b = [5, 6, 2, 7, 3, 1, 4]

for i in b:
    hq.heappush(a, i)

print(a) # [1, 3, 2, 7, 6, 5, 4]

예) 최소힙 제거

import heapq as hq

a = []
b = [5, 6, 2, 7, 3, 1, 4]

# 삽입
for i in b:
    hq.heappush(a, i)

# 제거
for _ in range(len(a)):
    print(a)
    hq.heappop(a)

#[1, 3, 2, 7, 6, 5, 4]
#[2, 3, 4, 7, 6, 5]
#[3, 5, 4, 7, 6]
#[4, 5, 6, 7]
#[5, 7, 6]
#[6, 7]
#[7]