파이썬 힙 큐 알고리즘

힙 데이터 구조는 우선 순위 큐를 나타내는 데 사용할 수 있습니다. 파이썬에서는 heapq 모듈에서 사용할 수 있습니다. 여기에서 최소 힙을 생성합니다. 따라서 우선 순위가 1일 때 가장 높은 우선 순위를 나타냅니다. 새 요소가 삽입되면 힙 구조가 업데이트됩니다.

이 모듈을 사용하려면 −

import heapq

일부 힙 관련 작업이 있습니다. 이들은 -

메서드 heapq.heapify(반복 가능)

iterable 데이터 세트를 힙 데이터 구조로 변환하는 데 사용됩니다.

메서드 heapq.heappush(힙, 요소)

이 메서드는 요소를 힙에 삽입하는 데 사용됩니다. 그런 다음 전체 힙 구조를 다시 힙합니다.

heapq.heappop(힙) 메소드

이 메서드는 힙의 맨 위에서 요소를 반환 및 삭제하고 나머지 요소에 대해 heapify를 수행하는 데 사용됩니다.

메서드 heapq.heappushpop(힙, 요소)

이 메소드는 하나의 명령문에 요소를 삽입하고 팝업하는 데 사용됩니다.

메서드 heapq.heapreplace(힙, 요소)

이 메서드는 하나의 문에 요소를 삽입하고 팝업하는 데 사용됩니다. 힙의 루트에서 요소를 제거한 다음 요소를 힙에 삽입합니다.

메서드 heapq.nlargest(n, iterable, key=None)

이 메서드는 힙에서 가장 큰 n개의 요소를 반환하는 데 사용됩니다.

메서드 heapq.nsmallest(n, iterable, key=None)

이 메서드는 힙에서 가장 작은 n개의 요소를 반환하는 데 사용됩니다.

예시 코드

import heapq
my_list = [58, 41, 12, 17, 89, 65, 23, 20, 10, 16, 17, 19]
heapq.heapify(my_list)
print(my_list)
heapq.heappush(my_list, 7)
print(my_list)
print('Popped Element: ' + str(heapq.heappop(my_list)))
print(my_list)
new_iter = list()
new_iter = heapq.nlargest(4, my_list)
print(new_iter)

출력

[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[7, 16, 10, 17, 17, 12, 23, 20, 41, 89, 58, 65, 19]
Popped Element: 7
[10, 16, 12, 17, 17, 19, 23, 20, 41, 89, 58, 65]
[89, 65, 58, 41]