힙 Heap

우선순위 큐를 위해 만들어진 자료구조이다.

먼저, 우선순위 큐에 대해 짧게 알아보면...

 

# 우선순위 큐

우선순위의 개념을 큐에 도입한 자료구조이다.

데이터들이 우선순위를 가지고 있고 우선순위가 높은 데이터가 먼저 나간다.

 

# 우선순위 큐 이용사례

시뮬레이션 시스템

네트워크 트래픽 제어

운영 체제에서의 작업 스케쥴링

수치 해석적인 계산

 

우선순위 큐는 배열, 연결리스트, 힙으로 구현이 가능하다.

이 중에서 힙으로 구현이 가능하는게 가장 효율적이라고 한다.

힙으로 구현할 시 삽입과 삭제의 시간복잡도는 각각 O(logn)이 된다고 한다.

 

# 힙 heap

완전 이진 트리(Complete tree)의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다.

완전이진트리는 왼쪽부터 아래쪽으로 삽입해 나간다. 또한 리프노드의 위쪽부분들은 Full tree로 돼있다.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다.

힙은 일종의 반정렬 상태를 유지한다.

- 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도

- 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 말한다.

- 힙 트리에서는 중복된 값을 허용한다. (이진 탐색 트리에서는 중복된 값을 허용하지 않는다)

- 키값의 대소관계는 부모/자식 간에만 성립하고, 형제노드 사이에는 대소관계가 정해지지 않는다

 

# 힙의 종류

최대 힙(max heap)

- 부모 노드의 키 값이 자식 녿드의 키 값보다 크거나 같은 완전 이진 트리

 

최소 힙(min heap)

- 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

# 삽입

맨 밑의 리프노드 자리에 삽입을 하고 percolate-up 처럼 뿌리에서부터 위로 올라간다.

부모노드와 우선순위를 비교해서 부모가 더 작다면(최대 힙) 두 자리를 바꿔준다. 이런식으로 반복해

heap property를 지켜준다.

 

# 힙의 구현 (파이썬)

파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

이진트리 구조로 내부적으로는 인덱스 0부터 시작해 k번째 원소가 항상 자식 원소들

(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬된다.

 

heapq.heappush(heap, item) : item을 heap에 추가

heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴. 비어 있는 경우 IndexError가 호출된다.

heapq.heapify(x) : 리스트 x를 즉각적ㅇ로 heap으로 변환함 (O(N))

 

heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있기 때문에, 빈 리스트를 생성한 후 heapq의

함수를 호출할 때마다 리스트를 인자에 넘겨야 한다.

 

import heapq

heap = []

heapq.heappush(heap, 100)

이런식으로 한다.

 

원소를 삭제하지 않고 가져오고 싶으면 [0] 인덱싱을 통해 접근한다.

파이썬에서 힙은 최소 힙으로 구현되어 있어서 최대 힙을 구현하기 위해선

원소를 추가할 때, (-item, item)의 튜플 형태로 넣어 첫 번째 원소를 우선순위로 힙을 구성해

최대 힙으로 쓸 수 있게 한다.