[자료구조] 힙(heap)

힙(Heap) - 트리 자료구조의 응용

 

이진 트리의 일종으로, 여러 개의 값 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾을 수 있도록 구성된 자료구조입니다. 힙은 배열을 사용하여 구현합니다.

 

+ 트리(Tree)란?

임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 구조로, 노드 중에서 단 하나의 루트 노드(Root Node)가 있고, 루트 노드에서 하위 노드(Sub Node)들이 연결된 비선형 계층 구조입니다. 트리 구조 중 다음 데이터를 가리키는 것이 2개인 단방향 트리 구조는 이진 트리 구조라고 합니다. 트리 자료구조의 구현은 배열이나 연결 리스트를 사용합니다.

 

힙의 종류

• 최소 힙(Min Heap) : 부모 노드의 값이 항상 하위 노드의 값보다 작은 경우
• 최대 힙(Max Heap) : 부모 노드의 값이 항상 하위 노드의 값보다 큰 경우

 

파이썬은 heapq 모듈과 Queue 모듈의 PriorityQueue 클래스를 통해 heapq를 제공합니다. 모두 최소 힙으로 구현되어 있어, 가장 앞에 있는 원소가 가장 작은 원소입니다. heapq와 PriortyQueue 중에서는 heapq가 더 빠르다고 하네요. 힙은

1. 힙은 데이터가 지속적으로 정렬되어야 할 때,
2. 데이터의 삽입/삭제가 빈번하게 일어날 때 사용합니다.

 

힙 정렬 : heapify(heap)

주어진 리스트를 힙 정렬합니다. 시각 복잡도는 O(N)입니다.

가장 작은 원소인 1이 맨 앞으로 왔어요.

 

원소 추출 : heappop(heap)

힙정렬된 리스트에서 

1. 가장 작은 원소를 빼내고

2. 나머지 원소가 힙을 유지하도록 힙정렬합니다.

가장 작은 원소인 1이 리턴되었습니다.

 

원소 삽입 : heappush(heap, item)

힙정렬된 리스트의 힙 상태를 유지하면서 원소를 삽입합니다.

삽입한 원소 -1이 가장 작으므로 맨 앞에 위치

최솟값의 위치가 그대로 유지됨

 

최솟값에 접근하기

따라서 리스트를 변형하지 않은 채 가장 작은 원소를 알고 싶을 때, 인덱스 [0]을 사용해 리스트에 접근합니다.