Wie berechnet Python Werte in einem Heap?

Question

zum Beispiel eine Liste von Zufallszahlen:

>>> x = [1,24,5,1,5,1,23,6] 
>>> heapq.heapify(x) 
[1, 1, 1, 6, 5, 5, 23, 24] 

Warum 5,5,6 oder 5,6,5 ist es willkürlich tun 6,5,5 und nicht?

Answer 1

enthalten Python docs folgenden Beschreibung heapq:

Heaps sind binäre Bäume für die jeder Elternknoten einen Wert kleiner als oder gleich zu einem seiner Kinder hat. Diese Implementierung verwendet Arrays, bei denen heap[k] <= heap[2*k+1] und heap[k] <= heap[2*k+2] für alle k Elemente von Null zählen. Zum Vergleich werden nicht existierende Elemente als unendlich betrachtet. Die interessante Eigenschaft eines Heaps ist, dass sein kleinstes Element immer der Stamm heap[0] ist.

Sie können diese Daten mit Ihrem Beispiel überprüfen:

>>> for i in xrange(len(x)): 
...  print '{0} <= {1}'.format(x[i], x[i*2+1:i*2+3]) 
... 
1 <= [1, 1] 
1 <= [6, 5] 
1 <= [5, 23] 
6 <= [24] 
5 <= [] 
5 <= [] 
23 <= [] 
24 <= [] 

Weitere Informationen über binäre Haufen Sie Wikipedia überprüfen können.