[파이썬/python] 힙 (heap)

힙은 최대값 및 최소값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리 기반의 자료구조이다.

 

힙은 부모노드와 자식노드의 관계로 최대 힙, 최소 힙으로 나뉜다.

키 값의 대소관계는 부모노드와 자식노드 간에만 성립하며 형제 사이에는 성립하지 않을 수 있다.

• 최대 힙 : 부모노드 키 값 >= 자식노드 키 값. 뿌리노드가 항상 제일 큼
• 최소 힙 : 부모노드 키 값 <= 자식노드 키 값. 뿌리노드가 항상 제일 작음

 

배열에 있는 데이터의 최대값 또는 최소값을 찾으려면 O(n)이 걸리지만

힙에 있는 데이터의 최대값 또는 최소값을 찾으려면 O(logn)이 걸리므로 더 효율적이다. 

 

힙으로 구현된 이진트리구조는 배열로 저장된다.

 

예시로 이해하기

아래의 예시는 최대 힙으로 정렬된 트리 구조가 있을 때 20을 추가하는 과정이다.

완성된 이진트리를 배열로 나타내면 아래와 같다.

[20, 13, 15, 3, 8, 10]

 

파이썬으로 구현하기

최소힙 구현

파이썬에서는 내장 모듈 heapq를 이용하여 간단히 구현할 수 있다.

 

heapq 모듈을 import 한 후 저장할 배열 heap을 만든다.

• heappush : 배열 heap에 원소 추가
• heappop : 배열 heap의 가장 작은 원소 삭제
• heapify : 기존 리스트를 힙으로 변환

import heapq
heap = []

# heappush
heapq.heappush(heap, 5)

# heappop
heapq.heappop(heap)

# heapify
list = [3, 6, 8, 2]
heapq.heapify(list)