-
Notifications
You must be signed in to change notification settings - Fork 2
/
min_priority_queue.py
178 lines (142 loc) · 6.12 KB
/
min_priority_queue.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
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
# -*- coding: utf-8 -*-
"""
Created on Sun Oct 20 13:59:50 2019
@author: Sai
"""
import math
import copy
class min_priority_queue(object):
def __init__(self, A):
self.heap = copy.deepcopy(A) # Need to have own copy so that the array is unaffected when extract_min is run
self.heap_size = len(self.heap)
for j in range(math.floor(self.heap_size/2)-1, -1, -1):
self.min_heapify(j)
def left(self, k):
return (k << 1) + 1
def right(self, k):
return (k << 1) + 2
def parent(self, k):
return math.ceil(k/2) - 1
def min_heapify(self, k):
# print(k)
# print(self.heap)
smallest = k
if self.left(k) < self.heap_size and self.heap[self.left(k)] < self.heap[smallest]:
smallest = self.left(k)
# Do NOT use elif in the line below - did it twice so far
if self.right(k) < self.heap_size and self.heap[self.right(k)] < self.heap[smallest]:
smallest = self.right(k)
if smallest != k:
tmp = self.heap[k]
self.heap[k] = self.heap[smallest]
self.heap[smallest] = tmp
self.min_heapify(smallest)
def extract_min(self):
to_return = self.heap[0]
self.heap[0] = self.heap[self.heap_size-1]
self.heap_size -= 1
# print('min heapifying')
self.min_heapify(0)
return to_return
def decrease_key(self, k, new_val):
# Decrease the key value of the k-th element to new_val
# Recursive version
# if self.parent(k) > -1 and new_val < self.heap[self.parent(k)]:
# # Swap with the parent
# tmp = self.heap[self.parent(k)]
# self.heap[self.parent(k)] = new_val
# self.heap[k] = tmp
#
# # Recurse
# self.decrease_key(self.parent(k), new_val)
# Iterative versions are always better..
assert new_val < self.heap[k] # Make sure new value is smaller than the current value
self.heap[k] = new_val
while self.parent(k) > -1 and self.heap[self.parent(k)] > new_val:
tmp = self.heap[self.parent(k)]
self.heap[self.parent(k)] = new_val
self.heap[k] = tmp
k = self.parent(k)
def push(self, new_val):
# To push a new value, we add it at the end and let it float up
self.heap_size += 1
self.heap[self.heap_size-1] = float('inf')
self.decrease_key(self.heap_size-1, new_val)
def draw_heap(self, spacing=2, width=2):
# Draws the heap
# Number of levels = 1 + height of tree
num_levels = math.floor(math.log(self.heap_size+1,2))+1
print('heap size '+str(self.heap_size+1))
print('num levels '+str(num_levels))
# print(self.heap)
# Calculate the spacing and offset arrays
spacing_array = [0]*num_levels
offset_array = [0]*num_levels
spacing_array[-1] = spacing # Spacing at the last level is set to a fixed value
offset_array[-1] = 0 # Last level has no offset
# Now iterate backwards and calculate spacing and offsets for all levels
for j in range(num_levels-2, -1, -1):
spacing_array[j] = spacing_array[j+1]*2 + width # Spacing of the m-th level is twice the spacing of the m+1-th level
offset_array[j] = offset_array[j+1] + spacing_array[j+1]/2 + width # Offset of m-th level = offset of previous level + spacing of previous level/2
# Iterate backwards again and construct the string at each level
str_list = ['']*num_levels
fmt = '{:^'+str(width)+'d}'
for height in range(num_levels-1, -1, -1):
str_level = ' '*int(offset_array[height]) # First add the offset
for val in range(2**height):
if 2**height-1+val < self.heap_size:
str_level += fmt.format(self.heap[2**height-1+val]) # Then add the number
str_level += ' '*int(spacing_array[height]) # And the space between the numbers
else:
str_level += 'X'*width # If outside the heap, show 'X'
str_level += ' '*int(spacing_array[height])
str_list[height] = str_level
# Now print
for height in range(num_levels):
print(str_list[height]+'\n')
return str_list
# First let's test the heap
array = [1, 3, 9, 10, 14, 8, 2, 4, 16, 7, 36, 7, 8, 99, 12, 5, 43, 1, 45, 4, 22, 67, 8, 11, 48, 9, 36, 46, 77, 99]
A = min_priority_queue(array)
# Check that the heap property is maintained for all nodes
for j in range(A.heap_size):
if A.left(j) < A.heap_size:
assert A.heap[A.left(j)] >= A.heap[j]
if A.right(j) < A.heap_size:
assert A.heap[A.right(j)] >= A.heap[j]
# Now test extract_min
#print(A.heap)
assert A.extract_min() == min(array)
array.remove(min(array))
#print(A.heap)
assert A.extract_min() == min(array)
array.remove(min(array))
assert A.extract_min() == min(array)
array.remove(min(array))
assert A.extract_min() == min(array)
array.remove(min(array))
assert A.extract_min() == min(array)
array.remove(min(array))
assert A.extract_min() == min(array)
array.remove(min(array))
assert A.extract_min() == min(array)
# Now test push
A.draw_heap()
A.push(-1)
A.draw_heap()
# Check that the heap property is maintained for all nodes
for j in range(A.heap_size):
if A.left(j) < A.heap_size:
assert A.heap[A.left(j)] >= A.heap[j]
if A.right(j) < A.heap_size:
assert A.heap[A.right(j)] >= A.heap[j]
assert A.extract_min() == -1 # Because the pushed value is negative and all other numbers in the heap are positive
A.draw_heap()
A.push(10)
A.draw_heap()
# Check that the heap property is maintained for all nodes
for j in range(A.heap_size):
if A.left(j) < A.heap_size:
assert A.heap[A.left(j)] >= A.heap[j]
if A.right(j) < A.heap_size:
assert A.heap[A.right(j)] >= A.heap[j]