-
Notifications
You must be signed in to change notification settings - Fork 0
/
Heap.py
134 lines (119 loc) · 4.13 KB
/
Heap.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
# ##############################
# Heap.py
#
# This file provide a MinHeap class.
#
# The class constructor takes two optional
# parameters:
# item_val, which is a lambda which
# returns the value by which to sort the values
# initial_list, a list of items to build a heap out of.
# ##############################
class HeapUnderflowError(Exception):
pass
class MinHeap:
def __init__(self, item_val = None, initial_list = None):
self.heap = [None]
self.size = 0
if item_val is None:
self.item_val = lambda x: x
else:
self.item_val = item_val
if initial_list is not None:
for item in initial_list:
self.heap.append(item)
self.size += 1
for i in range(self.size//2,0,-1):
self.heapify(i)
def heapify(self, i = 1):
l = 2 * i
r = l + 1
smallest = i
if l <= self.size and self.item_val(self.heap[l]) < self.item_val(self.heap[i]) :
smallest = l
if r <= self.size and self.item_val(self.heap[r]) < self.item_val(self.heap[smallest]) :
smallest = r
if smallest != i:
item = self.heap[i]
self.heap[i] = self.heap[smallest]
self.heap[smallest] = item
self.heapify(smallest)
def insert(self, item):
self.size += 1
self.heap.append(item)
i = self.size
while i > 1 and self.item_val(self.heap[i]) < self.item_val(self.heap[i//2]):
swap_val = self.heap[i//2]
self.heap[i//2] = self.heap[i]
self.heap[i] = swap_val
i = i//2
def decrement(self, item, item_str, key_str):
for entry, idx in enumerate(self.heap,1):
# must start at 1 because 0 is always none
if entry[item_str] == item:
entry[key_str] -= 1
cur_idx = idx
parent_idx = idx //2
while parent_idx > 0 and self.heap[parent_idx][key_str] > self.heap[cur_idx][key_str]:
swap = self.heap[parent_idx]
self.heap[parent_idx] = self.heap[cur_idx]
self.heap[cur_idx] = swap
return
def extract(self):
if self.size < 1:
raise HeapUnderflowError
if self.size == 1:
self.size = 0
return self.heap.pop(-1)
self.size -= 1
swap_val = self.heap[1]
self.heap[1] = self.heap.pop(-1)
self.heapify()
return swap_val
class MaxHeap:
def __init__(self, item_val = None, initial_list = None):
self.heap = [None]
self.size = 0
if item_val is None:
self.item_val = lambda x: x
else:
self.item_val = item_val
if initial_list is not None:
for item in initial_list:
self.heap.append(item)
self.size += 1
for i in range(self.size//2,0,-1):
self.heapify(i)
def heapify(self, i = 1):
l = 2 * i
r = l + 1
largest = i
if l <= self.size and self.item_val(self.heap[l]) > self.item_val(self.heap[i]) :
largest = l
if r <= self.size and self.item_val(self.heap[r]) > self.item_val(self.heap[largest]) :
largest = r
if largest != i:
item = self.heap[i]
self.heap[i] = self.heap[largest]
self.heap[largest] = item
self.heapify(largest)
def insert(self, item):
self.size += 1
self.heap.append(item)
i = self.size
while i > 1 and self.item_val(self.heap[i]) > self.item_val(self.heap[i//2]):
swap_val = self.heap[i//2]
self.heap[i//2] = self.heap[i]
self.heap[i] = swap_val
i = i//2
def extract(self):
if self.size < 1:
raise HeapUnderflowError
if self.size == 1:
self.size = 0
return self.heap.pop(-1)
self.size -= 1
swap_val = self.heap[1]
self.heap[1] = self.heap.pop(-1)
self.heapify()
return swap_val