-
Notifications
You must be signed in to change notification settings - Fork 0
/
myHeap.py
163 lines (138 loc) · 3.44 KB
/
myHeap.py
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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
__author__ = 'Dimitri Zhang'
class myHeap(object):
"""
a min-heap
"""
def __init__(self):
# a list where elements rest, reresenting a binary tree
self.heap = []
# the size of heap
self.size = 0
def __str__(self):
return str(self.heap)
def __iter__(self):
return iter(self.heap)
def __getitem(self, key):
try:
return self.heap[key]
except IndexError:
raise
except TypeError:
raise
def insert(self, val):
"""
insert an element into the heap in O(logn) time, n is the number of elements in the heap
"""
# append the element to the end of heap
self.heap.append(val)
# increase heap size by 1
self.size += 1
# if more than 1 element in the heap, then swap nodes if necessary to mantain the heap property
if self.size > 1:
# the index of the newly-added element
index = self.size - 1
# the index of the newly-added element's parent
parent = (index - 1) >> 1
# while the current node is smaller than its parent, swap it with its parent
while self.heap[parent] > self.heap[index]:
tmp = self.heap[parent]
self.heap[parent] = self.heap[index]
self.heap[index] = tmp
# set index to its parent
index = parent
# reach the root, the heap invariance is fully restored
if index == 0:
break
# the parent of current index
parent = (index - 1) >> 1
def pop(self):
"""
pop the smallest element fromt the heap, mantain heap invariant
"""
if self.size == 0:
return None
top = self.heap[0]
if self.size == 1:
del self.heap[0]
self.size -= 1
return top
self.heap[0] = self.heap[-1]
del self.heap[-1]
self.size -= 1
index = 0
left = index * 2 + 1
right = index * 2 + 2
smallest = index
while True:
if left < self.size and self.heap[left] < self.heap[smallest]:
smallest = left
if right < self.size and self.heap[right] < self.heap[smallest]:
smallest = right
if smallest != index:
tmp = self.heap[index]
self.heap[index] = self.heap[smallest]
self.heap[smallest] = tmp
index = smallest
left = index * 2 + 1
right = index * 2 + 2
else:
break
return top
def heapify(self, arr):
"""
heapify an arbitrary array into a min-heap in O(n) time in a bottom-up manner
"""
self.size = len(arr)
index = self.size - 1
# if arr is not empty, heapify arr
if self.size:
for i in range((index - 1) // 2, -1, -1):
self.minHeapify(arr, i)
self.heap = arr
def minHeapify(self, arr, index):
"""
heapify the subtree rooted at index in list arr
"""
smallest = index
left = index * 2 + 1
right = index * 2 + 2
length = len(arr)
if left < length and arr[left] < arr[smallest]:
smallest = left
if right < length and arr[right] < arr[smallest]:
smallest = right
if smallest != index:
tmp = arr[index]
arr[index] = arr[smallest]
arr[smallest] = tmp
self.minHeapify(arr, smallest)
def peek(self):
"""
retrieve but not pop the top element from the heap
"""
# if heap is not empty
if self.size:
return self.heap[0]
# return None if the heap is empty
return None
def isEmpty(self):
"""
check if the heap is empty
"""
return self.size == 0
def main():
heap = myHeap()
# heap.insert(1)
# heap.insert(3)
# heap.insert(2)
# heap.insert(0)
# print(heap)
# while not heap.isEmpty():
# print(heap.pop())
# print(heap.pop())
heap.heapify([4,1,3,2,4,1])
print(heap)
while not heap.isEmpty():
print(heap.pop())
if __name__ == '__main__':
main()