PythonのPriority queue（優先度付きキュー）でpopすると最小値が取得できる

PythonのPriority queue（優先度付きキュー）にはheapqが利用できます。ヒープは二分木によって実現されますが、「親ノードの値が子ノードより大きい場合」と「親ノードの値が子ノードより小さい場合」の2つのパターンが考えられます。教科書的には前者が多いようですが、Pythonのheapqは後者。そのためpopすると最小値 が取得できます。ドキュメンテーションを引用すると下記の通り。

The API below differs from textbook heap algorithms in two aspects: （中略） (b) Our pop method returns the smallest item, not the largest (called a “min heap” in textbooks; a “max heap” is more common in texts because of its suitability for in-place sorting).

「教科書とは違うよ」って書いてあるのが面白いですね。

利用方法

使い方はこんな感じ。

import heapq

def test_heapq():
    a = [3,5,2,8,-2]
    heapq.heapify(a)
    v = heapq.heappop(a)
    assert v == -2

ほかの言語は？

ドキュメントベースでさらっと調べたところプログラミング言語によって「最小値を取得する」のか、「最大値を取得する」のかけっこうバラバラな様子です。どちらを選択するかをどう決めているんだろう。それぞれPopすると…

C++ std::priority_queue

最大値を取得。

Java PriorityQueue

最小値を取得。

C# PriorityQueue

最小値を取得

Rust PriorityQueue

最大値を取得