| 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
|
# This module defines the classes Stack, Queue, and PriorityQueue
#----------------------------------------------------------------------
class Stack:
"""
A simple list implementation of a stack. Interface methods:
s.isEmpty() returns True if s is empty
s.insert(x) inserts x into s at the front
s.remove() removes and returns the first element from s
"""
def __init__(self):
self.contents = []
def isEmpty(self):
return len(self.contents) == 0
def remove(self):
if self.isEmpty():
return None
else:
return self.contents.pop(0)
def insert(self, new):
self.contents.insert(0, new)
#----------------------------------------------------------------------
class Queue:
"""
A simple list implementation of a queue. Interface methods:
q.isEmpty() returns True if q is empty
q.insert(x) inserts x into q at the end
q.remove() removes and returns the first element from q
"""
def __init__(self):
self.contents = []
def isEmpty(self):
return len(self.contents) == 0
def remove(self):
if self.isEmpty():
return None
else:
return self.contents.pop(0)
def insert(self, new):
self.contents.append(new)
#----------------------------------------------------------------------
class PriorityQueue:
"""
This is a heap implementation of a priority queue. The insert and
remove operations each take O(log n) time. To create a new priority
queue, call the constructor with a function that maps queue elements
to cost values. Interface methods:
q.isEmpty() returns True if q is empty
q.insert(x) inserts x into q according to the cost of x
q.remove() removes and returns the lowest-cost element from q
Example:
q = PriorityQueue(lambda x: x)
q.insert(5)
q.insert(1)
q.insert(3)
q.insert(8)
q.insert(2)
print q.remove() ==> 1
print q.remove() ==> 2
print q.remove() ==> 3
print q.remove() ==> 5
print q.remove() ==> 8
print q.remove() ==> None
"""
# costFunction is a function that maps queue elements to cost values
def __init__(self, costFunction):
# current number of elements in queue
self.size = 0
# current maximum size of queue (can be changed - see insert below)
self.limit = 10
# the elements themselves (position 0 is not used)
self.contents = [None] * (self.limit + 1)
# a function that returns the cost of the element at position i
self.cost = lambda i: costFunction(self.contents[i])
def isEmpty(self):
# returns True if the queue is empty, or else False
return self.size == 0
def isRoot(self, i):
# returns True if element i is the root of the heap
return i == 1
def isLeaf(self, i):
# returns True if element i is a leaf
return self.left(i) == None and self.right(i) == None
def parent(self, i):
# returns the position of the parent of element i
return i / 2
def left(self, i):
# returns the position of the left child of element i
child = i * 2
if child > self.size:
return None
else:
return child
def right(self, i):
# returns the position of the right child of element i
child = i * 2 + 1
if child > self.size:
return None
else:
return child
def smallestChild(self, i):
# returns the position of the smallest child of element i
leftChild = self.left(i)
rightChild = self.right(i)
if leftChild == None:
return rightChild
elif rightChild == None:
return leftChild
elif self.cost(leftChild) < self.cost(rightChild):
return leftChild
else:
return rightChild
def swap(self, i, j):
# swaps elements in positions i and j (using parallel assignment)
self.contents[i], self.contents[j] = self.contents[j], self.contents[i]
def insert(self, new):
# inserts a new element into the heap
if self.size == self.limit:
# this doubles the amount of space available in self.contents
self.contents.extend([None] * self.size)
self.limit += self.size
self.size += 1
self.contents[self.size] = new
# push new element up toward the root as far as possible
current = self.size
while not self.isRoot(current):
parent = self.parent(current)
if self.cost(current) >= self.cost(parent):
return
self.swap(current, parent)
current = parent
def remove(self):
# deletes the current element at the root of the heap and returns it
if self.size == 0:
return None
else:
min = self.contents[1]
self.contents[1] = self.contents[self.size]
self.size -= 1
# push new root element down into the heap as far as possible
current = 1
while not self.isLeaf(current):
child = self.smallestChild(current)
if self.cost(current) <= self.cost(child):
return min
self.swap(current, child)
current = child
return min |
