In diesem Artikel möchte ich ein Beispiel für die Implementierung in Python 3 über den Algorithmus vorstellen, den ich durch Lesen von "Algorithm Picture Book" gelernt habe. Der Algorithmus ist diesmal die Heap-Sortierung. Der Schriftsteller ist ein Amateur. Ich würde mich freuen, wenn Sie mir verschiedene Dinge erzählen könnten.
Ich bin nicht mit Python2 vertraut, aber ich weiß nur, dass ich Python3 verwende (Ist es Python3.6.0?). Daher lautet der Titel des Artikels Python3.
Ich werde die Problemstellung und den Ansatz nur kurz erläutern. Wir verwenden eine Datenstruktur namens "Heap". Einzelheiten zum Heap finden Sie im "Algorithm Picture Book".
Gibt die Spalten in aufsteigender Reihenfolge für eine bestimmte Anzahl von Spalten zurück.
Beispiel: 5, 2, 7, 3, 6, 1, 4 → 1, 2, 3, 4, 5, 6, 7
Speichern Sie die angegebene Zahl im absteigenden Heap (maximale Wurzel) und wiederholen Sie "Wert von Wurzel nehmen → Ganz links platzieren". Weitere Informationen finden Sie im "Algorithm Picture Book".
Der implementierte Code wird unten gezeigt. Zuerst werde ich eine kleine Idee erklären.
Außerdem habe ich es gewagt, es für das Studium zu implementieren, aber es scheint, dass Python ein Modul namens heapq in der Standardbibliothek hat, daher denke ich, dass es gut ist, es praktisch zu verwenden (https: //docs.python). .org / ja / 3 / library / heapq.html).
Eine als Heap bezeichnete Datenstruktur wird realisiert, indem die Bedeutung in der Reihenfolge der Elemente des Arrays angenommen wird. Es ist leichter zu verstehen, wenn Sie sich die Ergänzung im Abschnitt "Heap-Sortierung" des "Algorithm Picture Book" ansehen.
Außerdem ist es im Heap (2-Minuten-Heap) praktisch, die Elementnummer von 1 aus zu starten (Wikipedia Bi-Minuten-Heap # Implementierung des Heaps % 8C% E5% 88% 86% E3% 83% 92% E3% 83% BC% E3% 83% 97 #% E3% 83% 92% E3% 83% BC% E3% 83% 97% E3% 81% AE% E5% AE% 9F% E8% A3% 85))).
Grob gesagt sieht es wie folgt aus.
Die Liste, die anfänglich den variablen Daten zugewiesen wird, ist die zu verarbeitende Zahlenspalte.
Außerdem kann dieser Code verwirrend sein, daher füge ich der (?) Version des Codes unten einige Funktionen hinzu, um die Sichtbarkeit zu verbessern. Wir würden uns freuen, wenn Sie uns Ihre Meinung dazu mitteilen könnten, welche besser ist.
heap_sort.py
data = [5, 2, 7, 3, 6, 1, 4]
print("input :" + str(data))
data_len = len(data)
heap = [0] #Das 0. Element ist ein Dummy(Es ist einfach zu berechnen, ob von 1 im Heap gezählt wird)
#Speichern Sie die Eingabedaten der Reihe nach im Heap(Erstellen Sie den Heap jedes Mal neu)
for i in range(0, data_len):
heap.append(data[i])
if i > 0:
child = i + 1
parent = child // 2
while(heap[parent] < heap[child]):
heap[parent], heap[child] = heap[child], heap[parent]
if parent > 1:
child = parent
parent = child // 2
else:
#Es hat die Wurzel erreicht, also werde ich hier verlassen
break
#Ruft Werte aus dem Stammverzeichnis des Heaps ab(Erstellen Sie den Heap jedes Mal neu)
output_data = list() #Array für die Ausgabe
for i in range(0, data_len):
#Stammwert kopieren
output_data.insert(0, heap[1])
#Entfernen Sie die Stammwerte und erstellen Sie den Heap neu
heap[1] = heap[-1]
heap.pop(-1)
parent = 1
while(len(heap) >= 2 * parent + 1):
if len(heap) == 2 * parent + 1:
if heap[parent] < heap[2 * parent]:
heap[parent], heap[2 * parent] = heap[2 * parent], heap[parent]
#Es gibt keine Zweige darüber hinaus, also wird es herauskommen
break
else:
if heap[2 * parent] > heap[2 * parent + 1]:
child = 2 * parent
else:
child = 2 * parent + 1
if heap[parent] < heap[child]:
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
else:
break
print("output :" + str(output_data))
python
$ python heap_sort.py
input :[5, 2, 7, 3, 6, 1, 4]
output :[1, 2, 3, 4, 5, 6, 7]
Wenn Sie Fragen haben, weisen Sie bitte darauf hin und stellen Sie Fragen. Besonders wenn es Verbesserungen beim Schreiben des Codes gibt, denke ich, dass es für das Lernen nützlich sein wird.
Ich würde mich auch über Hinweise zum Testen des Implementierungscodes und zum Vergleichen der Geschwindigkeit mit anderen Algorithmen freuen. (Ich habe es noch nicht getestet (^^;)
Dies ist die (?) Version des obigen Codes, die durch die Definition einiger Funktionen die Sichtbarkeit verbessert hat.
heap_sort_2.py
def parent_of(child):
return child // 2
def left_child_of(parent):
return 2 * parent
def right_child_of(parent):
return 2 * parent + 1
def heap_size(heap):
return len(heap[1:])
data = [5, 2, 7, 3, 6, 1, 4]
# data = [43, 1, -4, 91, 46, -609]
print("input :" + str(data))
data_len = len(data)
heap = [0] #Das 0. Element ist ein Dummy(Es ist einfach zu berechnen, ob von 1 im Heap gezählt wird)
#Speichern Sie die Eingabedaten der Reihe nach im Heap(Erstellen Sie den Heap jedes Mal neu)
for i in range(0, data_len):
heap.append(data[i])
if i > 0:
child = i + 1
parent = parent_of(child)
while(heap[parent] < heap[child]):
heap[parent], heap[child] = heap[child], heap[parent]
if parent > 1:
child = parent
parent = parent_of(child)
else:
#Es hat die Wurzel erreicht, also werde ich hier verlassen
break
#Ruft Werte aus dem Stammverzeichnis des Heaps ab(Erstellen Sie den Heap jedes Mal neu)
output_data = list() #Array für die Ausgabe
for i in range(0, data_len):
#Stammwert kopieren
output_data.insert(0, heap[1])
#Entfernen Sie die Stammwerte und erstellen Sie den Heap neu
heap[1] = heap[-1]
heap.pop(-1)
parent = 1
while(heap_size(heap) >= left_child_of(parent)):
if heap_size(heap) == left_child_of(parent):
child = left_child_of(parent)
if heap[parent] < heap[child]:
heap[parent], heap[child] = heap[child], heap[parent]
#Es gibt keine Zweige darüber hinaus, also wird es herauskommen
break
else:
if heap[left_child_of(parent)] > heap[right_child_of(parent)]:
child = left_child_of(parent)
else:
child = right_child_of(parent)
if heap[parent] < heap[child]:
heap[parent], heap[child] = heap[child], heap[parent]
parent = child
else:
break
print("output :" + str(output_data))
Recommended Posts