Python/MaxHeap.py at master · pythonminna/Python · GitHub

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# Python MaxHeap
# public functions: push, peek, pop
# private functions: __swap, __floatUp, __bubbleDown

classMaxHeap:
def__init__(self, items=[]):
super().__init__()
self.heap= [0]
foriinitems:
self.heap.append(i)
self.__floatUp(len(self.heap) -1)

defpush(self, data):
self.heap.append(data)
self.__floatUp(len(self.heap) -1)

defpeek(self):
ifself.heap[1]:
returnself.heap[1]
else:
returnFalse

defpop(self):
iflen(self.heap) >2:
self.__swap(1, len(self.heap) -1)
max=self.heap.pop()
self.__bubbleDown(1)
eliflen(self.heap) ==2:
max=self.heap.pop()
else:
max=False
returnmax

def__swap(self, i, j):
self.heap[i], self.heap[j] =self.heap[j], self.heap[i]

def__floatUp(self, index):
parent=index//2
ifindex<=1:
return
elifself.heap[index] >self.heap[parent]:
self.__swap(index, parent)
self.__floatUp(parent)

def__bubbleDown(self, index):
left=index*2
right=index*2+1
largest=index
iflen(self.heap) >leftandself.heap[largest] <self.heap[left]:
largest=left
iflen(self.heap) >rightandself.heap[largest] <self.heap[right]:
largest=right
iflargest!=index:
self.__swap(index, largest)
self.__bubbleDown(largest)

m=MaxHeap([95, 3, 21])
m.push(10)
print(str(m.heap[0:len(m.heap)]))
print(str(m.pop()))