82

数字だけでなく、たくさんの物を持っていきたいです。それらには、ヒープがソートできる整数属性が含まれます。Pythonでヒープを使用する最も簡単な方法はheapqですが、heapqを使用するときに特定の属性で並べ替えるように指示するにはどうすればよいですか？

4

8 に答える 8

117

ドキュメントの例によると、タプルを使用でき、タプルの最初の要素で並べ替えられます。

>>> h = []
>>> heappush(h, (5, 'write code'))
>>> heappush(h, (7, 'release product'))
>>> heappush(h, (1, 'write spec'))
>>> heappush(h, (3, 'create tests'))
>>> heappop(h)
(1, 'write spec')

したがって、メソッドを実行したくない（または実行できない）__cmp__場合は、プッシュ時に手動で並べ替えキーを抽出できます。

タプルのペアの最初の要素が等しい場合、さらに要素が比較されることに注意してください。これが希望どおりでない場合は、最初の各要素が一意であることを確認する必要があります。

于 2010-10-17T18:28:00.093 に答える
93

heapqオブジェクトを同じ方法で並べ替えるので、クラス定義内list.sortでメソッドを定義するだけ__cmp__()で、同じクラスの別のインスタンスと比較されます。

def __cmp__(self, other):
    return cmp(self.intAttribute, other.intAttribute)

Python2.xで動作します。

3.xでの使用：

def __lt__(self, other):
    return self.intAttribute < other.intAttribute
于 2010-10-17T18:19:17.820 に答える
31

公式文書によると、これに対する解決策は、エントリをタプルとして保存することです（セクション8.4.1および8.4.2を参照してください）。

たとえば、オブジェクトはタプルの形式 （key、value_1、value_2）で次のようになります。

オブジェクト（つまりタプル）をヒープに入れると、オブジェクトの最初の属性（この場合はkey）が比較されます。同点が発生した場合、ヒープは次の属性（つまり、value_1）を使用します。

例えば：

import heapq

heap = []
heapq.heappush(heap, (0,'one', 1))
heapq.heappush(heap, (1,'two', 11))
heapq.heappush(heap, (1, 'two', 2))
heapq.heappush(heap, (1, 'one', 3))
heapq.heappush(heap, (1,'two', 3))
heapq.heappush(heap, (1,'one', 4))
heapq.heappush(heap, (1,'two', 5))
heapq.heappush(heap, (1,'one', 1))

show_tree(heap)

出力：

                                      (0, 'one', 1)                                       
                (1, 'one', 1)                                (1, 'one', 4)                
    (1, 'one', 3)         (1, 'two', 3)         (1, 'two', 2)         (1, 'two', 5)     
(1, 'two', 11)

Pythonでヒープをきれいに印刷する方法について（リンクを更新）：show_tree（）

于 2018-07-06T07:14:07.263 に答える
9

最も簡単な方法は、heapqモジュールの既存のcmp_lt関数をオーバーライドすることだと思います。簡単な例：

import heapq

# your custom function. Here, comparing tuples a and b based on their 2nd element
def new_cmp_lt(self,a,b):
    return a[1]<b[1]

#override the existing "cmp_lt" module function with your function
heapq.cmp_lt=new_cmp_lt

#Now use everything like normally used
于 2019-11-19T07:19:59.767 に答える
8

私は同じ質問をしましたが、いくつかは近くにありましたが、十分に詳しく説明されていませんでしたが、上記の答えはどれもその場に出ませんでした。とにかく、私はいくつかの調査を行い、このコードを試しました。うまくいけば、これは答えを得ようとしている次の誰かにとって十分なはずです。

タプルを使用する際の問題は、柔軟性があまり高くない最初のアイテムのみを使用することです。次のようなC++のstd::priority_queueに似たもの std::priority_queue<pair<int, int>, vector<pair<int, int>>, comparator> pq; が必要でした。実際のアプリケーションでより一般的な独自のコンパレータを設計できます。

以下のスニペットがお役に立てば幸いです： https ：//repl.it/@gururajks/EvenAccurateCylinders

import heapq
class PQNode:

    def __init__(self, key, value):
        self.key = key
        self.value = value

    # compares the second value
    def __lt__(self, other):
        return self.value < other.value

    def __str__(self):
        return str("{} : {}".format(self.key, self.value))

input = [PQNode(1, 4), PQNode(7, 4), PQNode(6, 9), PQNode(2, 5)]
hinput = []
for item in input:
    heapq.heappush(hinput, item)

while (hinput):
    print (heapq.heappop(hinput))
于 2019-07-19T04:42:45.353 に答える
4

残念ながら、これは頻繁に要求される機能ですが、できません。

1つのオプションは、（キー、値）タプルをヒープに挿入することです。ただし、比較時に値が例外をスローした場合は機能しません（キーが同点の場合は比較されます）。

2番目のオプションは__lt__、適切な属性を使用して要素を比較して並べ替える（未満の）メソッドをクラスに定義することです。ただし、オブジェクトが別のパッケージによって作成された場合、またはプログラムの他の場所で異なる方法で比較する必要がある場合は、それが不可能な場合があります。

3番目のオプションは、 blistモジュールのsortedlistクラスを使用することです（免責事項：私は作成者です）。のコンストラクターは、およびのパラメーターと同様に、要素のソートキーを返す関数を指定できるパラメーターを取ります。sortedlistkeykeylist.sortsorted

于 2010-10-17T18:19:06.207 に答える
0

ヒープディクトを実装できます。最も優先度の低いアイテムを取得するためにpopitem（）を使用していることに注意してください。

import heapdict as hd
import string
import numpy as np

h = hd.heapdict()
keys = [char for char in string.ascii_lowercase[:10]]
vals = [i for i in np.random.randint(0,10, 10)]
for k,v in zip(keys,vals):
    h[k] = v
for i in range(len(vals)):
    print h.popitem()
于 2019-02-15T14:00:20.107 に答える
0

と呼ばれるモジュールがありますheaps。Githubアドレスはhttps://github.com/gekco/heapyです。クラスのインスタンス化時または配列からヒープを作成するときに、独自のキー/ソート関数を適用できます。これにより、アクションを実行するたびに引数としてヒープを追加する手間が省けます。

タプルの最後の位置にある最小の要素がヒープの一番上にあるリストが必要な例：

>>> from heapy.heap import Heap 
>>> a = [(3, 5, 10), (-5, 3, 8), (7, 8, 9), (-4, 0, 2)]
>>> x = Heap.from_array(a, key=lambda t : t[-1])
>>> x.length
4
>>> x.top()
(-4, 0, 2)
>>> x.insert((-1, 0, 1))
>>> x.length
5
>>> x.top()
(-1, 0, 1)
>>> a
[(3, 5, 10), (-5, 3, 8), (7, 8, 9), (-4, 0, 2)]
于 2021-10-20T11:22:08.343 に答える