質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

Q&A

解決済

1回答

3413閲覧

任意のクラスにおけるheapqの使用

退会済みユーザー

退会済みユーザー

総合スコア0

Python 3.x

Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

0グッド

0クリップ

投稿2017/08/15 19:10

###前提・実現したいこと
入力データ数"N"のデータ群のリスト"data"において
枝と長さをメンバとするクラス"Branch"のコンストラクタ"b"をヒープキュー"H"に格納したい。

###質問
下記のエラーを解決するためにはどこを書き直せばよいですか。

###発生している問題・エラーメッセージ

Traceback (most recent call last): File "Main.py", line 15, in <module> heapq.heappush(H, b) TypeError: unorderable types: Branch() < Branch()

###該当のソースコード

python3

1import heapq 2class Branch: 3 def __init__(self, start, end, length): 4 self.start = start 5 self.end = end 6 self.length = length 7 8N = int(input()) 9data = [list(map(int, input().split())) for i in range(N)] 10H = [] 11heapq.heapify(H) 12 13for d in data: 14 start, end, length = d 15 b = Branch(start, end, length) 16 heapq.heappush(H, b)

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

クラス"Branch"のインスタンス同士の大小比較ができないために提示エラーが発生しています。
Branchクラスに、比較メソッド__lt__を追加してください。
比較処理の詳細(どの値を見るか)はクラスによって適切に決める必要があります。

参考:
PythonのPriorityQueueとobjectの拡張比較メソッド
Pythonソートチートシート

Python

1import heapq 2class Branch: 3 def __init__(self, start, end, length): 4 self.start = start 5 self.end = end 6 self.length = length 7 def __lt__(self,other): 8 return (self.start,self.end,self.length) < (other.start,other.end,other.length) 9 10 # 以下:各メンバ毎に比較する例 11 """ 12 ret = (self.start < other.start) 13 if( ret != True): return ret 14 15 ret = (self.end < other.end) 16 if( ret != True): return ret 17 18 ret = (self.length < other.length) 19 return ret 20 """ 21 22H = [] 23heapq.heapify(H) 24A = [] 25for s in reversed(range(2)): 26 for e in reversed(range(2)): 27 for l in reversed(range(2)): 28 b = Branch(s,e,l) 29 heapq.heappush(H, b) 30 A.append(b) 31 32print('A') 33A.sort() 34for a in A: print(a.start,a.end,a.length) 35 36print('H') 37for h in H: print(h.start,h.end,h.length)
A 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1 H 0 0 0 0 0 1 0 1 0 1 0 0 1 0 1 1 1 0 0 1 1 1 1 1

投稿2017/08/16 00:22

編集2017/08/16 05:44
can110

総合スコア38234

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

退会済みユーザー

退会済みユーザー

2017/08/16 04:43

回答ありがとうございます。 上記のプログラムでは.startのみを比較にしていると思われますが、 その他のメンバでの比較、およびヒープの利用はどのようにすればよろしいでしょうか。
can110

2017/08/16 05:45

いえ、start,end,lengthをタプルで(一括)比較しています。 各メンバ毎の比較例も追加しました。
退会済みユーザー

退会済みユーザー

2017/08/16 10:31

タプルによるメンバの一括比較とありますが、メンバの大小関係がばらばらの場合はどうなるのでしょうか。 self.start > other.start and self.end < other.end などの場合のことです。
can110

2017/08/16 10:42

メンバの大小関係がばらばらの場合は、各メンバ毎に比較する例に示した通りに各メンバ毎に比較すればよいです。 ちなみになのですがBranchインスタンス同士は、どのようなルールで大小が決まるのでしょうか?
退会済みユーザー

退会済みユーザー

2017/08/16 11:10

なるほど。わかりました。 Branchはweightの大小でインスタンスの大小とみなす仕様を考えています。 木構造の生成に応用しようと思っていまして、各頂点間"start","end"の重みを"weight"と考えています。
can110

2017/08/16 11:18

ではおそらく、weight()はstart,endから求まる何らかの値を返すとして self.weight() < other.weight() のような式になるかと思います。
退会済みユーザー

退会済みユーザー

2017/08/16 11:24

わかりました。ありがとうございます。
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問