둔필승총

힙과 우선순위 큐

자료구조 힙(heap):

힙 자료구조는 완전 이진 트리의 일종으로 우선순위 큐(Prioirty Queue)를 위하여 만들어진 자료구조이다. 힙을 사용한 모듈은 heapq 모듈이다. 파이썬은 최소 힙만 구현되어 있다. 최소 힙은 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값을 갖게 되며, 우선순위 큐에서 가장 작은 값을 추출하는 것은 매번 힙의 루트를 가져오는 형태로 구현된다. 

우선순위 큐(Prioirty Queue):

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다. 우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 여러 개의 값들 중에서 최대값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이다. 대표적으로 최댓값 추출을 보면 예를 들어 큐에 [1, 4, 5, 3, 2] 가 들어 있고 최댓값을 추출하는 우선순위 큐가 있다고 가정하자. 이 경우 항상 남아 잇는 요소들의 최댓값이 우선순위에 따라 추출되어 5, 4, 3, 2, 1 순으로 추출된다. 

힙의 특징

힙에서 착각하기 쉬운 특징은, 힙은 정렬된 구조가 아니라는 점이다. 최소 힙의 경우 부모 노드가 항상 작다는 조건만 만족할 뿐, 서로 정렬되어 있지 않다. 예를 들어 오른쪽의 자식 노드가 더 커야될 것 같지만 왼쪽 노드보다 작은 경우도 얼마든지 있을 수 있다. 부모, 자식 간의 관계만 정의할 뿐, 좌우에 대한 관계는 정의하지 않기 때문이다. 

자식이 둘인 힙은 특별히 이진 힙(Binary Heap)이라 하며, 대부분은 이진 힙이 널리 사용된다. 힙을 저장하는 표준적인 자료구조는 배열이다. 구현을 쉽게 하기 위해 첫 번째 인덱스인 0은 사용되지 않는다. 힙은 여러 알고리즘에서 사용되는데 우선 순위 큐 뿐만 아니라 다익스트라 알고리즘, 최소 신장 트리를 구현하는 프림 알고리즘 등에도 활용된다.