4

やや怠惰に実装したプログラムに興味深いバグを見つけ、それを正しく理解しているかどうか疑問に思いました。短いバージョンでは、Pythonのheapq実装は実際にはリストを並べ替えず、ヒープ中心の方法でリストを作成するだけです。具体的にはheapify()、順序付けられた方法でリストの理解を容易にする順序付けられたリストになることを期待していました。

Pythonのドキュメントのように、優先度キューの例を使用します。

from heapq import heapify, heappush, heappop
from random import shuffle

class Item(object):
    def __init__(self, name):
        self.name = name

lst = []

# iterate over a pseudo-random list of unique numbers
for i in sample(range(100), 15):
    it = Item("Some name for %i" % i)
    heappush(lst, (i, it))

print([i[0] for i in lst])

結果は

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]

これは、リストの元の順序ではなく、ここで説明するヒープ中心の順序であることに注意してください。私はこれが完全に注文されることを怠惰に期待していました。

テストとして、heapify（）を介してリストを実行しても、変更はありません（リストはすでにヒープのように順序付けられているため）。

heapify(lst)

print([i[0] for i in lst])

>>> [2, 22, 7, 69, 32, 40, 10, 97, 89, 33, 45, 51, 94, 27, 67]

関数を使用してリストを反復処理すると、heappop()期待どおりの順序になります。

lst2 = []
while lst: lst2.append(heappop(lst))

print([i[0] for i in lst2])

>>> [2, 7, 10, 22, 27, 32, 33, 40, 45, 51, 67, 69, 89, 94, 97]

したがって、heapq（少なくとも人間の意味では）リストを順序付けないように見えますが、heappush()andheappop()関数はヒープのように順序付けられたリストを取得できます。

結果：ヒープリストに対するスライスおよびリスト内包演算は、順序付けされていない結果になります。

これは本当ですか、そしてこれは常に本当ですか？

（BTW：WinXPシステム上のPython 3.0.1）

4

4 に答える 4

9

ヒープはソートされたリストではありません（部分的にソートされたバイナリツリーの表現です）。

そうです、そうです。ヒープ化されたリストがソートされたリストのように動作することを期待している場合は、がっかりするでしょう。ヒープについて行うことができる唯一のソートの仮定は、それheap[0]が常に最小の要素であるということです。

（あなたがすでに書いたものに多くを追加するのは難しいです-あなたの質問は物事がどのようになっているのかについての優れた記事です。8-）

于 2009-06-25T23:23:49.367 に答える
0

結果：ヒープリストに対するスライスおよびリスト内包演算は、順序付けされていない結果になります。

これは本当ですか、そしてこれは常に本当ですか？

1回限りの並べ替えリストを取得するだけの場合は、次を使用します。

myList.sort()

優先キュー/ヒープは、並べ替えを実装するために使用することも、キューを優先形式に保つために使用することもできます。ヒープへの挿入はO（lg n）、getはO（1）、削除はO（lg n）です。これは、リスト全体を何度も繰り返すよりもはるかに優れています。

于 2009-06-25T23:30:05.203 に答える
0

「結果：ヒープ化されたリストに対するスライスおよびリスト内包演算は、順序付けられていない結果を生成します。これは真実ですか、これは常に真実ですか？」いいえ、常に正しいとは限りません。ほとんどの場合、注文はありませんが、注文することは可能です。heapify（）は、「ヒープ不変量」を満たすリストを生成します。この場合、それは最小ヒープです。ソートされたリストもヒープ不変条件を満たしていることがわかります（heapq段落4：「heap.sort（）はヒープ不変条件を維持します」を参照）。したがって、理論的には、ヒープ化されたリストもたまたまソートされる可能性があります。

于 2009-06-26T04:13:54.960 に答える
0

"" "heapify（）が、順序付けられた方法でリストの理解を容易にする順序付けられたリストになることを期待していました。" ""：この期待がマニュアルの読みに基づいている場合は、ドキュメントのバグレポートを作成する必要があります。

"" "結果：ヒープ化されたリストに対するスライスおよびリスト内包演算は、順序付けられていない結果を生成します。これは正しいですか、これは常に正しいですか？" ""：たとえばrandom.shuffle（）のように、言及されたアクティビティは次のとおりです。 「順序付けられた」結果を生成するように定義されていません。それは時々「順序付けられた」結果を生み出すかもしれませんが、これは偶然であり、信頼されるべきではなく、尋ねる価値はありません（IMHO）。

于 2009-06-26T00:11:15.153 に答える