Repository navigation
Expand file tree
/
Copy pathMaxHeap.py
More file actions
60 lines (52 loc) · 1.34 KB
/
Copy pathMaxHeap.py
File metadata and controls
60 lines (52 loc) · 1.34 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
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
class MaxHeap:
def __init__(self, items=[]):
super().__init__()
self.heap = [0]
for i in items:
self.heap.append(i)
self.__floatUp(len(self.heap) - 1)
def push(self, data):
self.heap.append(data)
self.__floatUp(len(self.heap) - 1)
def peek(self):
if self.heap[1]:
return self.heap[1]
else:
return False
def pop(self):
if len(self.heap) > 2:
self.__swap(1, len(self.heap) - 1)
max = self.heap.pop()
self.__bubbleDown(1)
elif len(self.heap) == 2:
max = self.heap.pop()
else:
max = False
return max
def __swap(self, i, j):
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
def __floatUp(self, index):
parent = index//2
if index <= 1:
return
elif self.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
if len(self.heap) > left and self.heap[largest] < self.heap[left]:
largest = left
if len(self.heap) > right and self.heap[largest] < self.heap[right]:
largest = right
if largest != 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()))