소개

파이썬에서 우선순위가 있는 큐의 거동으로 신비한 부분이 있어 조사해 보았다.

불가해한 행동

여기 을 참고로, Python에서 우선도 첨부 큐가 조사하고 있었는데, heapq 라이브러리로 실현이 가능하다는 것.
상기 링크처에서는, heapq의 사용예로서 이하와 같이 기재되어 있었다.

#引用元：https://qiita.com/ell/items/fe52a9eb9499b7060ed6
import heapq  # heapqライブラリのimport

a = [1, 6, 8, 0, -1]
heapq.heapify(a)  # リストを優先度付きキューへ
print(a)
# 出力: [-1, 0, 8, 1, 6] (優先度付きキューとなった a)

왜 출력이 이 줄([-1, 0, 8, 1, 6] )인가?
아무도 흥미 없을 것 같은 의문이 솟아왔다 (오름차순을 기대하고 있었기 때문에).

이유 : 목록의 요소가 힙 대기열 알고리즘으로 정렬되기 때문에

Python에서는 우선 순위가 지정된 큐를 목록으로 표현하고 있지만,
파이썬 문서 에 의하면, 힙 큐 알고리즘으로 리스트의 내용을 재정렬하고 있다고 한다.

여기 힙 설명 사이트에서 힙 알고리즘 설명을 자세히 설명하지만,
트리 구조를 리스트로 표현할 수 있다는 것(부모 노드의 리스트 인덱스를 i로 하면, 아이의 왼쪽 노드가 2*i, 오른쪽 노드가 2*i+1).
부모 - 자식 관계가 성립하도록 목록의 요소를 바꾸면 위의 출력이 얻어졌습니다.

힙 큐 알고리즘에 의한 정렬 흐름

※자세한 알고리즘은 여기 를 참조

힙 조건: 각 노드가 자식 노드보다 작거나 같음
초기 배열: [1, 6, 8, 0, -1]