Wie wird die Reihenfolge der von Pythons heapq-Bibliothek verwalteten Elemente festgelegt?

Question

Ich hatte den Eindruck, dass der erste Wert eine Werteposition im Heap bestimmt hat, aber das scheint nicht der Fall zu sein.

from __future__ import print_function 
import heapq 

q = [] 
heapq.heappush(q, (10, 11)) 
heapq.heappush(q, (11, 12)) 
heapq.heappush(q, (9, 10)) 
print(q) 

Das gibt mir eine Ausgabe von

[(9, 10), (11, 12), (10, 11)] 

aber ich war eine Ausgabe wie

[(9, 10), (10, 11), (11, 12)] 

Answer 1

Die Bedingung auf heapq erwarten ist keine „Art Garantie“ über die bereitgestellten Liste. Stattdessen garantiert es q[k] <= q[2*k+1] und q[k] <= q[2*k+2] (unter Verwendung q wie in Ihrem Beispiel).

Dies liegt daran, dass es intern als Binärbaum verwaltet wird.

Wenn Sie einfach die sortierte Liste verwenden möchten, können Sie heappop als shown here verwenden. In Ihrem speziellen Beispiel könnten Sie:

sorted_q = [heappop(q) for i in range(len(q)) 

und das Ergebnis, wie erwartet, wird sein:

>>> print sorted_q 
[(9, 10), (10, 11), (11, 12)] 

---

Die Theorie erklärt here in the docs. Relevant ist die folgende Zeile:

Die interessante Eigenschaft eines Heap ist, dass a [0] immer sein kleinstes Element ist.

die eine direkte Folge der Erkrankung ist q[k] <= q[2*k+1] und q[k] <= q[2*k+2], die eine Bedingung des Haufens ist.

Es gibt jedoch keine weiteren Garantien über die Reihenfolge auf dem Rest des Arrays. Und in der Tat sind beide folgende Bäume gültig Haufen:

0 
1  2 
2 5 3 4 

und

0 
2  1 
5 3 4 2 

, die gespeichert sind, jeweils als

[0, 1, 2, 2, 5, 3, 4] 

und

[0, 2, 1, 5, 3, 4, 2]