Làm thế nào để làm cho heapq đánh giá heap off của một thuộc tính cụ thể?

Question

Tôi muốn giữ một đống đồ vật, không chỉ là số. Họ sẽ có một thuộc tính số nguyên trong đó đống có thể sắp xếp theo. Cách dễ nhất để sử dụng heaps trong python là heapq, nhưng làm thế nào để tôi nói với nó để sắp xếp theo một thuộc tính cụ thể khi sử dụng heapq?

Answer 1

heapq cả các loại đối tượng theo cùng một cách list.sort không, vì vậy chỉ cần xác định một phương pháp __cmp__() trong định nghĩa lớp học của bạn, mà sẽ so sánh bản thân với một thể hiện của cùng lớp:

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

trình bằng Python 2.x.

Trong sử dụng 3.x:

def __lt__(self, other): 
    return self.intAttribute < other.intAttribute 

Answer 2

Thật không may, bạn không thể, mặc dù đây là tính năng thường được yêu cầu.

Một tùy chọn sẽ là chèn (khóa, giá trị) vào bộ nhớ. Tuy nhiên, điều đó sẽ không hoạt động nếu các giá trị ném một ngoại lệ khi so sánh (chúng sẽ được so sánh trong trường hợp liên kết giữa các khóa).

Tùy chọn thứ hai là xác định phương thức __lt__ (ít hơn) trong lớp sẽ sử dụng thuộc tính thích hợp để so sánh các phần tử để sắp xếp. Tuy nhiên, điều đó có thể không thực hiện được nếu các đối tượng được tạo bởi một gói khác hoặc nếu bạn cần chúng để so sánh ở một nơi khác trong chương trình.

Tùy chọn thứ ba sẽ là sử dụng lớp sortedlist từ mô-đun blist (tuyên bố từ chối trách nhiệm: Tôi là tác giả). Hàm tạo cho số sortedlist có tham số key cho phép bạn chỉ định hàm trả về khóa sắp xếp của phần tử, tương tự như thông số key của list.sort và sorted.

Answer 3

Theo ví dụ từ documentation, bạn có thể sử dụng các bộ, và nó sẽ sắp xếp theo các yếu tố đầu tiên của tuple:

>>> 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') 

Vì vậy, nếu bạn không muốn (hoặc không thể?) làm phương pháp __cmp__, bạn có thể trích xuất thủ công khóa sắp xếp của mình tại thời điểm đẩy.

Lưu ý rằng nếu các phần tử đầu tiên trong một cặp tuples bằng nhau, các phần tử khác sẽ được so sánh. Nếu đây không phải là những gì bạn muốn, bạn cần đảm bảo rằng mỗi phần tử đầu tiên là duy nhất.