# by default, only the result of the last expression in a cell is displayed after evaluation.
# the following forces display of *all* self-standing expressions in a cell.
from IPython.core.interactiveshell import InteractiveShell
InteractiveShell.ast_node_interactivity = "all"
class PriorityQueue: # sort the list, max is at last position in the list
def __init__(self):
self.data = []
def add(self, x):
self.data.append(x)
# self.data.sort() # default list sort is increasing order O(n lgn)
# default sort is on the value stored assuming you can compare those values
# list sort allows an argument "key" which is a function to apply to the data before comparing
def max(self):
return self.data[-1]
def pop_max(self):
temp = self.data[-1]
del self.data[-1]
return temp
def __bool__(self):
return len(self.data) > 0
def __len__(self):
return len(self.data)
def __repr__(self):
return repr(self.data)
pq = PriorityQueue()
import random
for _ in range(10):
pq.add(random.randrange(100))
pq
[3, 5, 21, 23, 42, 53, 53, 74, 87, 96]
while pq:
print(pq.pop_max())
96 87 74 53 53 42 23 21 5 3
pq1 = PriorityQueue()
pq1.add('matt')
pq1.add('Matt')
pq1.add('matthew')
while pq1:
print(pq1.pop_max())
matthew matt Matt
class PriorityQueue1: # sort the list, max is at last position in the list
def __init__(self, key=lambda x:x):
self.data = []
self.key=key
# when user constructs a PriorityQueue1, they can send a function to apply to the data
# before comparing in the sort
def add(self, x):
self.data.append(x)
# self.data.sort() # default list sort is increasing order O(n lgn)
# default sort is on the value stored assuming you can compare those values
# list sort allows an argument "key" which is a function to apply to the data before comparing
self.data.sort(key=self.key) # O(n lg n)
def max(self):
return self.data[-1]
def pop_max(self):
temp = self.data[-1]
del self.data[-1]
return temp
def __bool__(self):
return len(self.data) > 0
def __len__(self):
return len(self.data)
def __repr__(self):
return repr(self.data)
pq2 = PriorityQueue1(key = lambda x:-x)
import random
for _ in range(10):
pq2.add(random.randrange(100))
while pq2:
print(pq2.pop_max())
2 27 45 49 51 59 67 67 90 93
pq3 = PriorityQueue1(key = lambda x:len(x))
pq3.add('matt')
pq3.add('Matth')
pq3.add('matthew')
while pq3:
print(pq3.pop_max())
matthew Matth matt
class PriorityQueue2: # sort the list, max is at last position in the list
def __init__(self, key=lambda x:x):
self.data = []
self.key=key
# when user constructs a PriorityQueue1, they can send a function to apply to the data
# before comparing in the sort
def add(self, x):
self.data.append(x)
# self.data.sort() # default list sort is increasing order O(n lgn)
# default sort is on the value stored assuming you can compare those values
# list sort allows an argument "key" which is a function to apply to the data before comparing
# self.data.sort(key=self.key) # O(n lg n)
i = len(self.data)-1
while i>0 and key(self.data[i]) < key(self.data[i-1]) : #O(n)
self.data[i], self.data[i-1]= self.data[i-1], self.data[i]
def max(self):
return self.data[-1]
def pop_max(self):
temp = self.data[-1]
del self.data[-1]
return temp
def __bool__(self):
return len(self.data) > 0
def __len__(self):
return len(self.data)
def __repr__(self):
return repr(self.data)
pq3 = PriorityQueue1(key = lambda x:-x)
import random
for _ in range(10):
pq3.add(random.randrange(100))
while pq3:
print(pq3.pop_max())
11 14 46 53 54 59 69 73 78 98
class Heap:
def __init__(self):
self.data = []
@staticmethod # I can just call the method, not needed to be calls on an object NO self._parent
def _parent(idx): # function starting with _ is private
return (idx-1)//2
@staticmethod # I can just call the method, not needed to be calls on an object NO self._parent
def _left(idx): # function starting with _ is private
return (idx*2)+1
@staticmethod # I can just call the method, not needed to be calls on an object NO self._parent
def _right(idx): # function starting with _ is private
return (idx*2)+2
def add(self, x): # O(lg n)
# append the new value on the end of the list
self.data.append(x) # this also updates len(self.data) which is the heapsize ASSUME O(1)
# walk it up # do I have a parent and is it smaller than me
myIndex = len(self.data)-1 #index of the newly insert value
parentIndex = Heap._parent(myIndex)
while parentIndex>=0 and self.data[parentIndex]< self.data[myIndex ]:
self.data[parentIndex],self.data[myIndex ] = self.data[myIndex],self.data[parentIndex]
myIndex=parentIndex
parentIndex= Heap._parent(myIndex)
def max(self): # assuming not empty heap
return self.data[0]
def pop_max(self): #O(lgn)
# save the root value
temp = self.data[0]
# move the value from last node to root
self.data[0] = self.data[len(self.data)-1]
# remove that node from the heap (array)
del self.data[len(self.data)-1]
# heapify from there downward (walk it down)
self._heapify(0)
# return the old root value
return temp
def _heapify(self, idx): #O(lg n)
leftIdx=Heap._left(idx)
rightIdx=Heap._right(idx)
swapFlag=True
while leftIdx<len(self.data) and swapFlag:
# three way compare to find the node with max value
bigIdx=idx
if leftIdx<len(self.data) and self.data[leftIdx]>self.data[bigIdx]:
bigIdx=leftIdx
if rightIdx<len(self.data) and self.data[rightIdx]>self.data[bigIdx]:
bigIdx=rightIdx
#swap value of max node with idx node
if bigIdx != idx:
self.data[bigIdx],self.data[idx] = self.data[idx],self.data[bigIdx]
# update idx to be the node I swapped with
idx=bigIdx
leftIdx=Heap._left(idx)
rightIdx=Heap._right(idx)
else:
swapFlag=False
# do it again (stop when no children OR when idx value is biggest)
def __bool__(self):
return len(self.data) > 0
def __len__(self):
return len(self.data)
def __repr__(self):
return repr(self.data)
h = Heap()
import random
for _ in range(10):
h.add(random.randrange(100))
h
[92, 50, 25, 28, 38, 23, 16, 0, 27, 20]
print(h.pop_max())
h
92
[50, 38, 25, 28, 20, 23, 16, 0, 27]
while h:
print(h.pop_max())
50 38 28 27 25 23 20 16 0
-1//2
-1
for i in range(10-1,-1,-1):
print(i)
9 8 7 6 5 4 3 2 1 0
def heapsort(iterable):
heap = Heap()
for x in iterable: # iteration over n times
heap.add(x) # each add is O(lgn)
temp=[0]*len(iterable)
for i in range(len(iterable)-1,-1,-1): # iteration over n times
temp[i]=heap.pop_max() # each popmax is O(lgn)
return temp
# upper bound O(n lg n)
heapsort([-4,4,7,0,3,1])
[-4, 0, 1, 3, 4, 7]
import random
def pairs(iterable):
it = iter(iterable)
a = next(it)
for i in range(len(iterable)-1):
b = next(it)
yield a,b
a = b
lst = heapsort([random.random() for _ in range(1000)])
all((a <= b) for a, b in pairs(lst))
True
import timeit
def time_heapsort(n):
return timeit.timeit('heapsort(rlst)',
'from __main__ import heapsort; '
'import random; '
'rlst = ([random.random() for _ in range({})])'.format(n),
number=10)
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
ns = np.linspace(100, 10000, 50, dtype=np.int_)
plt.plot(ns, [time_heapsort(n) for n in ns], 'r+')
plt.show()
[<matplotlib.lines.Line2D at 0x1fa26e5e970>]
%matplotlib inline
import matplotlib.pyplot as plt
import numpy as np
ns = np.linspace(100, 10000, 50, dtype=np.int_)
plt.plot(ns, [time_heapsort(n) for n in ns], 'r+')
plt.plot(ns, ns*np.log2(ns)*0.01/10000, 'b') # O(n log n) plot
plt.show()
[<matplotlib.lines.Line2D at 0x1fa2719d700>]
[<matplotlib.lines.Line2D at 0x1fa2719daf0>]
