Python Heap Sort
Python3-BeispieleHeapsort ist ein Sortieralgorithmus, der unter Verwendung der Heap-Datenstruktur entworfen wurde. Ein Heap ist eine Struktur, die einem vollständigen Binärbaum angenähert ist und gleichzeitig die Heap-Eigenschaft erfüllt: Das heißt, der Schlüssel oder Index eines Kindknotens ist immer kleiner (oder größer) als der seines Elternknotens. Man kann sagen, dass Heapsort eine Auswahlsortierung ist, die das Konzept eines Heaps zum Sortieren verwendet.
Beispiel
def heapify(arr, n, i):
largest = i
l = 2 * i + 1 # left = 2*i + 1
r = 2 * i + 2 # right = 2*i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # Swap
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Baue einen Max-Heap.
for i in range(n, -1, -1):
heapify(arr, n, i)
# Elemente nacheinander tauschen
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i] # Tauschen
heapify(arr, i, 0)
arr = [ 12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print ("Nach dem Sortieren")
for i in range(n):
print ("%d" %arr[i]),
Die Ausgabe beim Ausführen des obigen Codes ist:
排序后 5 6 7 11 12 13Andere Erweiterungen