우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조
우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용
자료구조 | 추출되는 데이터 |
---|---|
스택(Stack) | 가장 나중에 삽입된 데이터 |
큐(Queue) | 가장 먼저 삽입된 데이터 |
우선순위 큐(Priority Queue) | 가장 우선순위가 높은 데이터 |
우리는 힙(heap)을 이용하여 구현하는 방법에 대해 알아볼 것 !
데이터의 개수가 N개일 때, 구현 방식에 따른 시간 복잡도
우선순위 큐 구현 방식 | 삽입 시간 | 삭제 시간 |
---|---|---|
리스트 | O(1) | O(N) |
힙(Heap) | O(logN) | O(logN) |
heapq
모듈은 내장 모듈이기 때문에 파이썬만 설치되어 있으면 다음과 같이 간단하게 임포트 후에 힙 관련 함수를 사용할 수 있다.from heapq import heappush, heappop //, ... 다른 함수들
heapq
모듈에은 파이썬의 보통 리스트를 마치 최소 힙처럼 다룰 수 있도록 도와준다.PriorityQueue
클래스처럼 리스트와 별개의 자료구조가 아니므로 일단 빈 리스트를 생성해놓은 다음, heapq
모듈의 함수를 호출할 때 마다 이 리스트를 인자로 넘겨야 한다.heap
모듈을 통해 원소를 추가하거나 삭제한 리스트
가 최소 힙이다.heap = []
heappush()
함수는 O(log(n))
의 시간 복잡도를 가진다.from heapq import heappush
heappush(heap, 4)
heappush(heap, 1)
heappush(heap, 7)
heappush(heap, 3)
print(heap) # [1, 3, 7, 4]
heapq
모듈의 heappop()
함수를 이용하여 힙에서 원소를 삭제할 수 있다.가장 작은 원소
를 삭제 후에 그 값을 리턴한다.heappop()
함수도 역시 O(log(n))
의 시간 복잡도를 가진다.from heapq import heappop
print(heappop(heap)) # 1
print(heap) # [3, 4, 7]
print(heap[0]) # 3
heappop()
함수를 호출하여 원소를 삭제할 때마다 이진 트리의 재배치를 통해 매번 새로운 최소값을 인덱스 0에 위치시키기 때문이다.heap[1]
으로 접근하면 안 되고, 반드시 heappop()
을 통해 가장 작은 원소를 삭제 후에 heap[0]
를 통해 새로운 최소값에 접근해야 한다.heapq
모듈의 heapify()
라는 함수에 사용하면 된다.from heapq import heapify
heap = [4, 1, 7, 3, 8, 5]
heapify(heap)
print(heap) # [1, 3, 5, 4, 8, 7]
heapify()
함수에 리스트를 인자로 넘기면 리스트 내부의 원소들의 위에서 다룬 힙 구조에 맞게 재배치되며 최소값이 0번째 인덱스에 위치된다.heappush()
함수로 원소를 하나씩 추가한 효과와 같다.heapify()
함수의 성능은 인자로 넘기는 리스트의 원소수에 비례하므로 O(n)
의 시간 복잡도를 가진다.heapify()
함수를 사용할 때 주의할 점은 새로운 리스트를 반환하는 것이 아니라 인자로 넘긴 리스트에 직접 변경한다는 것이다. nums = [4, 1, 7, 3, 8, 5]
heap = nums[:]
heapify(heap)
print(nums) # [4, 1, 7, 3, 8, 5]
print(heap) # [1, 3, 5, 4, 8, 7]
(우선 순위, 값)
구조의 튜플(tuple)을 힙에 추가하거나 삭제한다.from heapq import heappush, heappop
nums = [4, 1, 7, 3, 8, 5]
heap = []
for num in nums:
heappush(heap, (-num, num)) # (우선 순위, 값)
while heap:
print(heappop(heap)[1]) # index 1
8
7
5
4
3
1
n
번째로 작은 값이나 n
번째로 큰 값을 효과적으로 구할 수 있다.n
번째 최소값을 구하기 위해서는 주어진 배열로 힙을 만든 후, heappop()
함수를 n
번 호출하면 된다.from heapq import heappush, heappop
def nth_smallest(nums, n):
heap = []
for num in nums:
heappush(heap, num)
nth_min = None
for _ in range(n):
nth_min = heappop(heap)
return nth_min
print(nth_smallest([4, 1, 7, 3, 8, 5], 3)) # 4
heapify()
함수를 활용하면 힙을 만들 때 굳이 루프를 돌면서 숫자를 매번 하나씩 추가해 줄 필요가 없다.from heapq import heapify, heappop
def nth_smallest(nums, n):
heapify(nums)
nth_min = None
for _ in range(n):
nth_min = heappop(nums)
return nth_min
heapq
모듈에 이미 이러한 용도로 사용할 수 있는 nsmallest()
라는 함수가 존재한다.nsmallest()
함수는 주어진 리스트에서 가장 작은 n
개의 값을 담은 리스트를 반환한다.n
번째 작은 값이다.from heapq import nsmallest
nsmallest(3, [4, 1, 7, 3, 8, 5])[-1]
nlargest()
함수를 사용하면 된다.from heapq import nlargest
nlargest(3, [4, 1, 7, 3, 8, 5])[-1]
from heapq import heappush, heappop
def heap_sort(nums):
heap = []
# 모든 원소를 차례대로 힙에 삽입
for num in nums:
heappush(heap, num)
sorted_nums = []
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
while heap:
sorted_nums.append(heappop(heap))
return sorted_nums
print(heap_sort([4, 1, 7, 3, 8, 5])) # [1, 3, 4, 5, 7, 8]
from heapq import heappush, heappop
def heapsort(nums):
heap = []
# 모든 원소를 차례대로 힙에 삽입
for num in nums:
heappush(heap, (-num, num))
result = []
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
while heap:
result.append(heappop(heap)[1])
return result
print(heapsort([4, 1, 7, 3, 8, 5])) # [8, 7, 5, 4, 3, 1]
위에서 알아본 heapq 모듈을 파이썬 코드로 직접 구현해보면서, heap 자료구조에 대해 더 자세히 알아보자.
[3, 4, 6, 8, 5, 7]
라는 힙에 원소 2
를 추가한다고 해보자.
def heappush(heap, data):
heap.append(data)
# 추가한 원소의 인덱스를 구한다.
current = len(heap) - 1
# 현재 원소가 루트(인덱스 0)에 도달하면 종료
while current > 0:
# 추가한 원소의 부모 인덱스를 구한다.
parent = (current - 1) // 2
# 새 값이 부모의 값보다 작으면 값을 교환
if heap[parent] > heap[current]:
heap[parent], heap[current] = heap[current], heap[parent]
# 추가한 원소의 인덱스를 갱신한다.
current = parent
else:
break
def heappush(heap, data):
heap.append(data)
current = len(heap) - 1
while current > 0:
parent = (current - 1) // 2
# 새 값이 부모의 값보다 크면 교환
if heap[parent] < heap[current]:
heap[parent], heap[current] = heap[current], heap[parent]
current = parent
else:
break
[3, 4, 6, 8, 5, 7]
라는 힙에서 원소 3
을 삭제한다고 해보자.
def heappop(heap):
if not heap:
return "Empty Heap!"
elif len(heap) == 1:
return heap.pop()
pop_data, heap[0] = heap[0], heap.pop()
current, child = 0, 1
while child < len(heap):
sibling = child + 1
if sibling < len(heap) and heap[child] > heap[sibling]:
child = sibling
if heap[current] > heap[child]:
heap[current], heap[child] = heap[child], heap[current]
current = child
child = current * 2 + 1
else:
break
return pop_data
def heappop(heap):
if not heap:
return 0
elif len(heap) == 1:
return "Empty Heap!"
pop_data, heap[0] = heap[0], heap.pop()
current, child = 0, 1
while child < len(heap):
sibling = child + 1
# 오른쪽 자식 노드가 왼쪽 자식 노드보다 크면 child = 오른쪽 자식 노드
# (더 큰 자식 노드와 현재 노드를 비교하기 위해)
if sibling < len(heap) and heap[child] < heap[sibling]:
child = sibling
# 현재 노드와 자식 노드 비교
# 현재 노드보다 자식 노드가 더 크면 swap하고 현재 노드 인덱스 갱신
if heap[current] < heap[child]:
heap[current], heap[child] = heap[child], heap[current]
current = child
child = current * 2 + 1
else:
break
return pop_data
[6, 2, 5, 1, 3, 4]
배열을 heapify 한다고 가정해보자.
def heapify(arr):
last = len(arr) // 2 - 1
for current in range(last, -1, -1):
while current <= last:
child = current * 2 + 1
sibling = child + 1
if sibling < len(arr) and arr[child] > arr[sibling]:
child = sibling
if arr[current] > arr[child]:
arr[current], arr[child] = arr[child], arr[current]
current = child
else:
break
def max_heapify(arr):
last = len(arr) // 2 - 1
for current in range(last, -1, -1):
while current <= last:
child = current * 2 + 1
sibling = child + 1
if sibling < len(arr) and arr[child] < arr[sibling]:
child = sibling
if arr[current] < arr[child]:
arr[current], arr[child] = arr[child], arr[current]
current = child
else:
break
매우매우 도움이 되었습니다