There are two python files, one is An in place quick sort and other is Binary Heap.
1. the In place quick sort, it uses multiple lists in order to do the search, Revise it to use the same list instead of multiple lists. This will require recursion.
2. For the Binary Heap, it does not handle the max requirement on insert. Revise it, give the class a max value and check it in the insert and then remove the least significant element. Figure out what is the least significant element in the implementation.
import math
import random
class BinaryHeap:
def __init__(self, array, direction=1, size=100):
if(size > len(array)):
self.size = len(array)
else:
self.size = size;
self.bBinaryHeap = array[:]
if 0 < direction:
self.compare = self.greater
else:
self.compare = self.less
self.buildBinaryHeap()
def node(self, index):
return (index << 1) + 1
def parent(self, index):
return (index – 1) >> 1
def bBinaryHeapifyDown(self, index):
swap = self.bBinaryHeap[index]
while self.node(index) < self.size:
node = self.node(index)
if node + 1 < self.size and self.compare(self.bBinaryHeap[node],
self.bBinaryHeap[node + 1]) > 0:
node += 1
if self.compare(swap, self.bBinaryHeap[node]) > 0:
self.bBinaryHeap[index] = self.bBinaryHeap[node];
else:
break
index = node
self.bBinaryHeap[index] = swap
def upheapify(self, index):
while 0 < index and self.compare(self.bBinaryHeap[index],
self.bBinaryHeap[self.parent(index)]) < 0:
parent = self.parent(index)
swap = self.bBinaryHeap[parent]
self.bBinaryHeap[parent] = self.bBinaryHeap[index]
self.bBinaryHeap[index] = swap
index = parent
def buildBinaryHeap(self):
indices = range(0, int(self.size / 2))
reversed(indices)
for index in indices:
self.bBinaryHeapifyDown(index)
def insert(self, value):
self.shrink()
index = self.size
self.bBinaryHeap[index] = value
self.size += 1
self.upheapify(index)
def search(self, value):
for index in range(self.size):
if self.bBinaryHeap[index] == value:
return index
def delete(self, value): index = self.search(value)
self.size -= 1
self.bBinaryHeap[index] = self.bBinaryHeap[self.size]
parent = self.parent(index)
if (index == 0) or (self.compare(self.bBinaryHeap[parent],
self.bBinaryHeap[index]) < 0):
self.bBinaryHeapifyDown(index)
else:
self.upheapify(index)
def shrink(self):
capacity = len(self.bBinaryHeap)
if capacity == self.size:
self.bBinaryHeap.extend([0] * capacity)
def greater(self, value1, value2):
if value1 == value2:
return 0
elif value1 < value2:
return 1
elif value1 > value2:
return -1
def less(self, value1, value2):
if value1 == value2:
return 0
elif value1 < value2:
return -1
elif value1 > value2:
return 1
def getLevel(self, index):
return int(math.floor(math.log(index + 1, 2)))
def displayBinaryHeap(self):
printBinaryHeap = str(self.bBinaryHeap)
height = self.getLevel(self.size)
previous = -1
for index in range(self.size):
getLevel = self.getLevel(index)
n = height – getLevel
indent = int(math.pow(2, n + 1) – 2)
spacing = 2 * indent
if getLevel != previous:
printBinaryHeap += '
'
printBinaryHeap += ' ' * indent
previous = getLevel
else:
printBinaryHeap += ' ' * spacing
printBinaryHeap += '%4d' % self.bBinaryHeap[index]
print(printBinaryHeap) if __name__ == "__main__":
size =10
array = [random.randint(0, 100) for i in range(size)]
bBinaryHeap = BinaryHeap(array, 1, 100)
print('Binary bBinaryHeap:')
bBinaryHeap.displayBinaryHeap()