Xác định chủ chốt đống cho một mảng của các bộ

Question

Một ví dụ đơn giản cho việc sử dụng của python heap implementation là

>>> from heapq import heappush, heappop 
>>> heap = [] 
>>> data = [1, 3, 5, 7, 9, 2, 4, 6, 8, 0] 
>>> for item in data: 
     heappush(heap, item) 

Trong một kịch bản phức tạp hơn, tôi có một mảng của các bộ như

tuples = [(5,"foo",True),(2,"bar", False),(8,"foobar",True)] 

và muốn để sử dụng mục nhập đầu tiên của mỗi tuple là khóa heap, tức là các bộ dữ liệu cần được sắp xếp theo số trong bộ dữ liệu theo heap.

Tôi có thể làm như thế nào?

Answer 1

Bạn có thể chỉ cần sử dụng bộ nhớ giống như chúng. Python documentation explicitly makes note chẳng hạn như cách sử dụng:

Yếu tố heap có thể là bộ dữ liệu. Đây là hữu ích cho gán giá trị so sánh (như ưu tiên nhiệm vụ) cùng với các hồ sơ chính đang được theo dõi:

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

Đơn giản chỉ cần đẩy tuples để đống, và bật chúng khi cần thiết:

>>> from heapq import heappush, heappop 
>>> 
>>> heap = [] 
>>> tuples = [(5,"foo",True),(2,"bar", False),(8,"foobar",True)] 
>>> 
>>> for tup in tuples: 
...  heappush(heap, tup) 
... 
>>> heappop(heap) 
(2, 'bar', False) 

vì the implementation for heap sử dụng mặc định sắp xếp cho các bộ

while pos > startpos: 
    ... 
    if newitem < parent: 
     ... 
    ... 
... 

và Python phân loại các bộ yếu tố khôn ngoan, en đảm bảo các đối tượng mà bạn muốn các bộ dữ liệu được sắp xếp đến trước.