1. 힙(heqp)의 개념 및 규칙
2. heapq 함수 활용하기
3. 힙(heap) 정렬
4. 최대 힙(heap)
1. 힙(heqp)의 개념 및 규칙
앞에서 큐는 데이터가 들어온 순서대로 나가는 선입선출(First In First Out)의 자료구조라고 공부했습니다. 그런데 들어가는 데이터에 우선순위를 매겨서 들어간 순서와 관계없이 나갈 때 우선순위가 높은 데이터가 먼저 나가는 자료를 "우선순위 큐" 라고 합니다. 힙(heap)은 이러한 우선순위 큐를 구현한 자료구조 입니다.
힙은 다음과 같은 규칙을 지닌 이진트리입니다.
1. 노드를 왼쪽에서 오른쪽으로 하나씩 빠짐없이 채워나간다.
2. 최소 힙은 부모 노드가 자식 노드의 값보다 작거나 같아야한다. (최대힙은 부모노드가 자식 노드의 값보다 크거나 같다.)
또한, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 합니다.
파이썬에서는 이러한 힙을 내장 모듈인 heapq 을 사용하여 쉽게 구현할 수 있습니다. 모든 부모 노드는 그의 자식 노드보다 값이 작거나 큰 이진트리(binary tree) 구조인데, 내부적으로는 인덱스 0에서 시작해 k번째 원소가 항상 자식 원소들(2k+1, 2k+2) 보다 작거나 같은 최소 힙의 형태로 정렬됩니다.
heapq를 사용해서 힙을 만들려면, []로 초기화된 리스트를 사용하거나, heapify()함수를 통해 값이 들어 있는 리스트를 힙으로 변환 하는 두가지 방법이 있습니다.
import heapq
arr=[]
heapq.heappush(arr,10)
heapq.heappush(arr,50)
heapq.heappush(arr,20)
heapq.heappush(arr,40)
heapq.heappush(arr,30)
print(arr) #[10, 30, 20, 40, 50]
import heapq
arr=[10,50,20,40,30]
heapq.heapify(arr) #만들어져 있는 리스트를 힙으로 변환
print(arr) #[10, 30, 20, 40, 50]
상황에 맞게 두가지 방법중 적절한 방법을 선택해 힙을 만들면 되겠습니다.
2. heapq 함수 활용하기
1. heappush(heap, item)
item값을 heap으로 푸시합니다.
import heapq
arr=[10,50,20,40,30]
heapq.heapify(arr)
print(arr) #[10, 30, 20, 40, 50]
heapq.heappush(arr,60)
print(arr) #[10, 30, 20, 40, 50, 60]
2. heappop(heap)
heap에서 가장 작은 항목을 팝하고 반환합니다. (heap이 비어있으면, IndexError가 발생)
import heapq
arr=[10,50,20,40,30]
heapq.heapify(arr)
print(arr) #[10, 30, 20, 40, 50]
print(heapq.heappop(arr)) #10
print(arr) #[20, 30, 50, 40]
하지만 이런식으로 heappop을 사용하여 최솟값을 얻으면 원본에 변화가 생기게 됩니다. 원본에 영향을 끼치지 않고 최솟값만 얻고싶으면
import heapq
arr=[10,50,20,40,30]
heapq.heapify(arr)
print(arr) #[10, 30, 20, 40, 50]
print(arr[0]) #10
print(arr) #[10,20, 30, 50, 40]이렇게 [0] 인덱싱을 통해 접근하면 됩니다.
3. heapify(array)
리스트 array를 선형시간으로 제자리에서 힙으로 변환합니다.
import heapq
arr=[10,50,20,40,30]
heapq.heapify(arr) #만들어져 있는 리스트를 힙으로 변환
print(arr) #[10, 30, 20, 40, 50]
3. 힙(heap) 정렬
앞에서 설명한 힙을 이용해서 손쉽게 힙정렬을 구현할 수 있는데
import heapq
arr=[1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
def heapsort(iterable):
h = []
for value in iterable:
heapq.heappush(h, value)
return [heapq.heappop(h) for i in range(len(h))]
result=heapsort(arr)
print(result) #[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
이렇게 모든 값을 힙으로 푸시하고 한 번에 하나씩 가장 작은 값을 팝 하여 구현할 수 있습니다. 새로운 배열을 만드는 것이 아니고 원본을 정렬해도 상관이 없다면 아래와 같이 코드를 더 간단하게 작성할 수 있습니다.
import heapq
arr=[1, 3, 5, 7, 9, 2, 4, 6, 8, 0]
heapq.heapify(arr)
for i in range(len(arr)):
print(heapq.heappop(arr),end=' ')
4. 최대 힙(heap)
heapq에서는 최소 힙을 기본적으로 제공하고 별도로 최대 힙을 제공하지는 않습니다. 따라서 아래 코드처럼 부호를 이용하여 최대 힙을 구현할 수 있습니다.
import heapq
heap = []
values = [1, 5, 3, 2, 4]
for value in values:
heapq.heappush(heap, -value)
print(heap) # [-5, -4, -3, -1, -2]
for i in range(len(heap)):
print(-heapq.heappop(heap), end=' ') # 5 4 3 2 1기존에 있는 값들로 힙을 바로 만드는 것이 아니라 부호를 바꾼 후 힙을 만들어 줍니다. 이렇게 되면 최댓값(5)이 부호가 바뀌어서 최솟값(-5)이 되었기 때문에 루트 노트에 위치하게 됩니다. 나중에 heappop으로 최솟값을 출력할때 다시 부호를 반대로 바꿔주면 최댓값을 되어 최대 힙이 만들어집니다.
참고 자료
https://docs.python.org/ko/3/library/heapq.html
'자료구조' 카테고리의 다른 글
| [자료구조] 스택(Stack)과 큐(Queue) (0) | 2024.01.18 |
|---|
댓글