Python의 힙 큐(또는 heapq)

<시간/>

힙 큐는 각 부모 노드가 자식 노드보다 작거나 같은 특수한 트리 구조입니다. 파이썬에서는 heapq 모듈을 사용하여 구현됩니다. 가중치가 높은 대기열 항목에 처리 우선 순위가 더 높은 우선 순위 대기열을 구현하는 데 매우 유용합니다.

힙 생성

heapq라는 파이썬 내장 라이브러리를 사용하여 힙 큐를 생성합니다. 이 라이브러리에는 힙 데이터 구조에 대한 다양한 작업을 수행하는 관련 기능이 있습니다. 다음은 이러한 기능의 목록입니다.

무거워지다 – 이 함수는 일반 목록을 힙으로 변환합니다. 결과 힙에서 가장 작은 요소는 인덱스 위치 0으로 푸시됩니다. 그러나 나머지 데이터 요소는 반드시 정렬되지는 않습니다.
힙푸시 – 이 함수는 현재 힙을 변경하지 않고 힙에 요소를 추가합니다.
힙팝 – 이 함수는 힙에서 가장 작은 데이터 요소를 반환합니다.
힙프리플레이스 – 이 함수는 가장 작은 데이터 요소를 함수에 제공된 새 값으로 대체합니다.

힙은 단순히 heapify 함수와 함께 요소 목록을 사용하여 생성됩니다. 아래 예에서 요소 목록을 제공하고 heapify 함수는 가장 작은 요소를 첫 번째 위치로 가져오는 요소를 재정렬합니다.

import heapq
H = [21,1,45,78,3,5]
# Use heapify to rearrange the elements
heapq.heapify(H)
print(H)

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다 -

[1, 3, 5, 78, 21, 45]

데이터 요소를 힙에 삽입하면 항상 마지막 인덱스에 요소가 추가됩니다. 그러나 값이 가장 작은 경우에만 새로 추가된 요소를 첫 번째 인덱스로 가져오기 위해 heapify 기능을 다시 적용할 수 있습니다. 아래 예에서는 숫자 8을 삽입합니다.

import heapq
H = [21,1,45,78,3,5]
# Covert to a heap
heapq.heapify(H)
print(H)
# Add element
heapq.heappush(H,8)
print(H)

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다 -

[1, 3, 5, 78, 21, 45]
[1, 3, 5, 78, 21, 45, 8]

이 함수를 사용하여 첫 번째 인덱스의 요소를 제거할 수 있습니다. 아래 예에서 함수는 항상 인덱스 위치 1에 있는 요소를 제거합니다.

import heapq

H = [21,1,45,78,3,5]
# Create the heap

heapq.heapify(H)
print(H)

# Remove element from the heap
heapq.heappop(H)

print(H)

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다 -

[1, 3, 5, 78, 21, 45]
[3, 21, 5, 78, 45]

heapreplace 함수는 항상 힙의 가장 작은 요소를 제거하고 어떤 순서로 고정되지 않은 위치에 새로운 들어오는 요소를 삽입합니다.

import heapq
H = [21,1,45,78,3,5]
# Create the heap
heapq.heapify(H)
print(H)
# Replace an element
heapq.heapreplace(H,6)
print(H)

위의 코드가 실행되면 다음과 같은 결과가 생성됩니다 -

[1, 3, 5, 78, 21, 45]
[3, 6, 5, 78, 21, 45]