Хотел реализовать Heap на пайтоне. Но в функции SiftDown произошло что-то с функцией swap и она не определяется после третьего вызова.
КОД:
class Heap:
def __init__(self):
self.arr = []
@staticmethod
def parent(i):
return i // 2
@staticmethod
def left(i):
return i * 2 + 1
@staticmethod
def right(i):
return i * 2 + 2
def PrintMin(self):
print(min(self.arr))
def MinChild(self, i):
if self.arr[left(i)] <= self.arr[right(i)]:
return left(i)
elif self.arr[left(i)] > self.arr[right(i)]:
return right(i)
def swap(first, second):
tmp = first
first = second
second = tmp
def levels(self):
NumOfLevels = 0
for i in range(self.size()):
if self.size() // 2 >=1:
NumOfLevels = NumOfLevels + 1
else:
break
NumOfLevels = NumOfLevels + 1
return NumOfLevels
def SiftDown(self, i):
for m in reversed(range(self.size()-1)):
n = m
while (self.arr[n] < self.arr[n//2]):
swap(self.arr[n], self.arr[n//2])
n = n//2
def size(self):
return len(self.arr)
def add(self, data):
self.arr.append(data)
self.SiftDown(0)
def delete(self, data):
self.arr.remove(data)
self.SiftDown(0)
def main():
Q = int(input())
heap = Heap()
for i in range(Q):
command = input()
command = command.split()
if command[0] == "1":
heap.add(int(command[1]))
elif command[0] == "2":
heap.delete(int(command[1]))
elif command[0] == "3":
heap.PrintMin()
if __name__ == "__main__":
main()
Пример input
6
1 9
1 4
1 6
НУ И САМА ОШИБКА
Traceback (most recent call last):
File "C:\Users\\source\repos\PythonApplication1\PythonApplication1\PythonApplication1.py", line 85, in
main()
File "C:\Users\\source\repos\PythonApplication1\PythonApplication1\PythonApplication1.py", line 77, in main
heap.add(int(command[1]))
File "C:\Users\\source\repos\PythonApplication1\PythonApplication1\PythonApplication1.py", line 60, in add
self.SiftDown(0)
File "C:\Users\\source\repos\PythonApplication1\PythonApplication1\PythonApplication1.py", line 50, in SiftDown
swap(self.arr[n], self.arr[n//2])
NameError: name 'swap' is not defined
