Repository navigation
Expand file tree
/
Copy pathHeapSort.py
More file actions
42 lines (39 loc) · 2.5 KB
/
Copy pathHeapSort.py
File metadata and controls
42 lines (39 loc) · 2.5 KB
1
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
class HeapSort:
def __init__(self, a):
self.arr = a
self.HeapObject = [None] * len(self.arr) # создаем итоговый архив с нанами
for i in range(len(self.arr)): # пробегаем по данным исходного массива начиная со второго тк первый уже вставили
self.Add(a[i])
def GetNextMax(self):
if len(self.HeapObject) == self.HeapObject.count(None):
return -1
count = len(self.HeapObject) - self.HeapObject.count(None)
index = 0
root = self.HeapObject[0]
self.HeapObject[0] = self.HeapObject[count - 1]
self.HeapObject[count - 1] = None
while True: # if self.HeapObject[2]== None and self.HeapObject[0] < self.HeapObject[1] меняем местами
if 2 * index + 1 >= count - 2 or 2 * index + 2 >= count - 2:
return root
if self.HeapObject[2 * index + 2] >= self.HeapObject[2 * index + 1]:
swapR = self.HeapObject[index]
self.HeapObject[index] = self.HeapObject[2 * index + 2]
self.HeapObject[2 * index + 2] = swapR
index = 2 * index + 2
if 2 * index + 1 >= count - 2 or 2 * index + 2 >= count - 2:
return root
if self.HeapObject[2 * index + 2] <= self.HeapObject[2 * index + 1]:
swapL = self.HeapObject[index]
self.HeapObject[index] = self.HeapObject[2 * index + 1]
self.HeapObject[2 * index + 1] = swapL
index = 2 * index + 1
def Add(self, key):
count = len(self.HeapObject) - self.HeapObject.count(None)
if None not in self.HeapObject:
return False # если куча вся заполнена
self.HeapObject[count] = key
while self.HeapObject[count] > self.HeapObject[int((count - 1) / 2)]: # если элемент больше родителя
swap = self.HeapObject[int((count - 1) / 2)] # сохраняем значение родителя в переменной
self.HeapObject[int((count - 1) / 2)] = self.HeapObject[count] # меняем значение родителя на ребенка
self.HeapObject[count] = swap # меняем значение ребенка на родителя
count = int((count - 1) // 2) # увеличивваем индекс на родительский