forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmin-heap.py
More file actions
81 lines (63 loc) · 1.46 KB
/
min-heap.py
File metadata and controls
81 lines (63 loc) · 1.46 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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
class MinHeap(object):
def __init__(self):
self.heap = []
self.size = 0
def push(self, x):
def bubbleUp(i):
p = max((i-1)//2, 0)
if self.heap[p]>self.heap[i]:
self.heap[p], self.heap[i] = self.heap[i], self.heap[p]
bubbleUp(p)
self.heap.append(x)
bubbleUp(self.size)
self.size += 1
def pop():
if self.size<=0: return None
m = self.heap[0]
remove(0)
return m
def remove(self, i):
def bubbleDown(i):
l = i*2+1
r = i*2+2
left_child = self.heap[l] if l<self.size else float('inf')
right_child = self.heap[r] if r<self.size else float('inf')
if self.heap[i]>left_child or self.heap[i]>right_child:
if left_child<right_child:
self.heap[i], self.heap[l] = self.heap[l], self.heap[i]
bubbleDown(l)
else:
self.heap[i], self.heap[r] = self.heap[r], self.heap[i]
bubbleDown(r)
if i>=self.size:
return
elif i==self.size-1:
self.heap = self.heap[:-1]
self.size -= 1
return
else:
self.heap[i], self.heap[-1] = self.heap[-1], self.heap[i]
self.heap = self.heap[:-1]
self.size -= 1
bubbleDown(i)
return
min_heap = MinHeap()
min_heap.push(3)
min_heap.push(1)
min_heap.push(2)
min_heap.push(10)
min_heap.push(4)
min_heap.push(7)
min_heap.push(9)
print min_heap.heap
min_heap.remove(2)
print min_heap.heap
min_heap.remove(2)
min_heap.remove(2)
min_heap.remove(2)
min_heap.remove(2)
print min_heap.heap
min_heap.remove(2)
min_heap.remove(1)
min_heap.remove(0)
print min_heap.heap