erarbeitet von: Ivar und Yann
Steckbrief Heap Sort
- Zeitkomplexität
- Platzkomplexität
- stabil
- nein
- in-place
- ja
- rekursiv
- ja
Der Heapsort Algorithmus bearbeitet Datenstrukturen namens Heap, ein Heap ist eine Baumstruktur oder ein “Binary Tree”. Er besteht aus zwei primären teilen, der Heapsort Funktion und der Heapify Funktion. Heap Sort nimmt die verschiedenen Werte eines Arrays und baut damit ein Binary Tree. Dieses Binary Tree wird danach nach der Grösse der Werte absteigend sortiert, dies heisst, dass jeder Wert im Baum grösser ist als die Werte unter ihm und kleiner als die Werte über ihm. Dieser Teil ist die Heapify Funktion. Der grösste Wert wird entfernt und an das Ende des Arrays hinzugefügt. Danach wird der Schritt des Ordnens nach Grösse wiederhold, dies macht diesen Algorithmus rekursiv. Da der Algorithmus In-place arbeitet, wird kein zusätzlicher Speicherplatz benötigt.
import matplotlib.pyplot as plt
from matplotlib.animation import FuncAnimation
import time
import numpy as np
def heapify(i, N, arr):
largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < N and arr[left] > arr[largest]:
largest = left
if right < N and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
plt.bar(x, arr, width=1)
plt.pause(1e-17)
plt.clf()
heapify(largest, N, arr)
def heapSort(arr):
N = len(arr)
for i in range(N//2 - 1, -1, -1):
heapify(i, N, arr)
for i in range(N-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(0, i, arr)
if __name__ == '__main__':
arr = np.arange(1, 101)
np.random.shuffle(arr)
x = np.arange(0, len(arr), 1)
heapSort(arr)
plt.show()
N = len(arr)
print("Sorted array is")
for i in range(N):
print("%d" % arr[i], end=" ")
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46