Project 3 of Adv.Algorithm
Question Description:
Main:
import math
import random
class bin_heap():
# root is 0
# parent:(i-1)//2
# left child: 2*i+1
# right child: 2*i+2
def __init__(self):
self.heap_list = []
self.heap_size = 0 # size of the heap
# build the min_binary heap, so the min of it is the root
def heap_min(self):
if self.heap_size == 0:
return None
else:
return self.heap_list[0]
# sort the array and maximum is the last index of the array
def heap_max(self):
if self.heap_size == 0:
return None
else:
# search the maximum from the last node
length = self.heap_size - 1
array = self.heap_list
max_heap =length
for i in range(length, -1, -1):
left_child = 2 * i + 1
# search the maximum until the node has children
if left_child > length:
if array[max_heap] < array[i - 1]:
max_heap = i-1
else:
break
return array[max_heap]
# insert the element to the end, and compare it to its parent until the root node
def insert(self, element):
self.heap_list.append(element)
# recompute the size of the heap
self.heap_size = len(self.heap_list)
# the index of element and index of it's parent
i_element = self.heap_size - 1
# compare it with its parent
while i_element > 0:
# i_parent = root
if self.heap_list[i_element] < self.heap_list[(i_element-1)//2]:
self.heap_list[i_element], self.heap_list[(i_element-1)//2] = self.heap_list[(i_element-1)//2], self.heap_list[i_element]
else:
break
i_element = (i_element-1)//2
# Iterate through the array to find the matching value, outputting the index
def search(self, value):
if self.heap_size == 0:
return None
else:
length = self.heap_size
for i in range(0, length):
if self.heap_list[i] == value:
return i
# compare the child and parent from top to bottom
def swap_down(self, i):
length = self.heap_size - 1
array = self.heap_list
leftchild = 2 * i + 1
# when exists child
while leftchild <= length:
left_child = leftchild
right_child = left_child + 1
# choose the minimal child
# exists right and left child
if right_child <= length:
if array[left_child] < array[right_child]:
min_index = left_child
else:
min_index = right_child
# only exists left child
if left_child <= length and right_child > length:
min_index = left_child
# change the minimal node and parent node
if array[min_index] < array[i]:
array[min_index], array[i] = array[i], array[min_index]
i = min_index
# enter next layer of binary heap
leftchild = min_index * 2 + 1
else:
break
def extract(self, value):
if self.heap_size == 0:
return None
else:
length = self.heap_size - 1
# get the index of the value
index = self.search(value)
remove_item = self.heap_list[index]
# change the position of current index and last node,and delete the node
self.heap_list[index], self.heap_list[length] = self.heap_list[length], self.heap_list[index]
self.heap_list.pop()
# recalculate the size
self.heap_size = len(self.heap_list)
# adjust the heap
self.swap_down(index)
print("the value:", remove_item, "has been extracted")
def build_binheap(self, input_value):
length = len(input_value)
for i in range(0, length):
self.insert(input_value[i])
def checker(self):
array = self.heap_list
length = len(array)
for i in range(0, length//2-1):
if array[i] > array[2*i+1] or array[i] > array[2*i+2]:
print(array[i],array[2*i+1],array[2*i+2])
print("heap is wrong")
return
print("heap is correct")
class beap():
# root=0
# the number of node in each layer <= the height of the layer-1. so the height is sqrt(2*index+0.75)-0.5
# left_parent=i-height
# right_parent=i-height+1
# left_child=i+height
# right_child=i+height+1
def __init__(self):
self.beap_list = []
self.beap_size = 0
def min_beap(self):
if self.beap_size == 0:
return None
else:
return self.beap_list[0]
def getheight(self, index):
height = math.ceil(math.sqrt(2*index+0.75)-0.5)
return height
# get the range of the current layer of the node
def getrange(self, height):
layer_left = height * (height - 1) // 2
layer_right = height * (height + 1) // 2 - 1
return layer_left, layer_right
# the maximum of the beap appear in the node without child
def max_beap(self):
if self.beap_size == 0:
return None
else:
# set the last node as the maximum firstly
length = self.beap_size - 1
array = self.beap_list
max_beap = length
# find the maximum from the last node to the node has children
for i in range(length, -1, -1):
h = self.getheight(i)
left_child = i + h
if left_child > length:
if array[max_beap] < array[i - 1]:
max_beap = i-1
else:
break
return array[max_beap]
def max_parent(self, index):
height = self.getheight(index)
left_range, right_range = self.getrange(height - 1)
left_parent = index - height
right_parent = index - height + 1
# The node is the first node of the current layer， only exits right parent
if left_parent < left_range:
return right_parent
# The node is the last node of the current layer, only exits left parent
elif right_parent > right_range:
return left_parent
# exits both left and right parent, find the max parent to replace
else:
if self.beap_list[left_parent] > self.beap_list[right_parent]:
return left_parent
else:
return right_parent
# insert the node to the last place in the beap and compare it to its parent until the root node
def insert(self, element):
self.beap_list.append(element)
# recompute the size of the heap
self.beap_size = len(self.beap_list)
# the index of element and index of it's parent
i_element = self.beap_size - 1
mp_index = self.max_parent(i_element)
while mp_index >= 0:
if self.beap_list[i_element] < self.beap_list[mp_index]:
self.beap_list[i_element], self.beap_list[mp_index] = self.beap_list[mp_index], self.beap_list[i_element]
i_element = mp_index
mp_index = self.max_parent(i_element)
else:
break
def search(self, value):
if self.beap_size == 0:
return None
else:
# search from the first node of the last layer
length = self.beap_size - 1
# get the range of last layer
height = self.getheight(length)
left_range, right_range = self.getrange(height)
# get the right parent of first node in the last layer
# because search form the left node,so left parent is the current node of the next layer.
right_parent = left_range - height + 1
# search the value in the beap
while 1:
# if the value smaller than the right parent, the current node goes to the previous layer
if value < self.beap_list[left_range]:
left_range = right_parent
height_index = self.getheight(left_range)
right_parent = left_range - height_index + 1
# If the value is greater than the current node then go to the right child of the node
# there are two case of right child
if value > self.beap_list[left_range]:
height_i = self.getheight(left_range)
rc_leftrange = left_range + height_i + 1
# if the current node exists right child
if rc_leftrange <= length:
left_range = rc_leftrange
height_i = self.getheight(left_range)
right_parent = left_range - height_i + 1
# if the current node doesn't have right child, go the right parent of previous layer
else:
last_height = self.getheight(left_range) - 1
# get range of previous layer
last_leftrange, last_rightrange = self.getrange(last_height)
# enter the previous layer
right_parent = left_range - height_i + 1
left_range = right_parent
# recalculate the right parent of current ndoe
height_i = self.getheight(left_range)
right_parent = left_range - height_i + 1
# when current node >the right range, it means it's the latest node of search in the beap
if left_range > last_rightrange:
return None
# find the index of value
if value == self.beap_list[left_range]:
return left_range
# if the index of value is 0, it will output in the last sentence.
# if appear 0 again, it means it can't find the value.
if left_range == 0:
return None
# adjust beap, from index to the bottom
def swap_down(self, i):
length = self.beap_size - 1
array = self.beap_list
height = self.getheight(i)
leftchild = i + height
# when exists child
while leftchild <= length:
left_child = leftchild
right_child = left_child + 1
# choose the minimal child
# exists right and left child
if right_child <= length:
if array[left_child] < array[right_child]:
min_index = left_child
else:
min_index = right_child
# only exists left child
if left_child <= length and right_child > length:
min_index = left_child
# change the minimal node and parent node
if array[min_index] < array[i]:
array[min_index], array[i] = array[i], array[min_index]
i = min_index
# recalculate the height of the current node
height_i = self.getheight(i)
# enter next layer of binary heap
leftchild = i + height_i
else:
break
def extract(self, value):
if self.beap_size == 0:
return None
else:
length = self.beap_size - 1
# get the index of value
index = self.search(value)
remove_item = self.beap_list[index]
# exchange the position of index node and last node
self.beap_list[index], self.beap_list[length] = self.beap_list[length], self.beap_list[index]
self.beap_list.pop()
# recalculate the size of beap
self.beap_size = len(self.beap_list)
self.swap_down(index)
print("the value:", remove_item, "has been extracted")
def build_beap(self, input_value):
length = len(input_value)
for i in range(0, length):
self.insert(input_value[i])
def checker(self):
array = self.beap_list
length = len(array)
h = self.getheight(length-1)
for i in range(0, h):
height = self.getheight(i)
if array[i] > array[i+height] or array[i] > array[i+height+1]:
print(array[i],array[i+height],array[i+height+1])
print("beap is wrong")
return
print("heap is correct")
Test:
from p3 import bin_heap, beap
import time
import random
import numpy as np
import matplotlib.pyplot as plt
from scipy.optimize import curve_fit
class Test():
# Binary_heap test for fixed value
def bin_heap_function(self):
bh = bin_heap()
insert_list = []
for i in range(10, -1, -1):
insert_list.append(i)
bh.build_binheap(insert_list)
print(bh.heap_list)
bh.checker()
print(bh.search(10))
print(bh.search(11))
print(bh.insert(11))
print(bh.heap_list)
bh.checker()
print(bh.extract(0))
print(bh.heap_list)
bh.checker()
print(bh.heap_min())
print(bh.heap_max())
# Beap test for fixed value
def beap_function(self):
beap_test = beap()
insert_list = []
for i in range(10, -1, -1):
insert_list.append(i)
beap_test.build_beap(insert_list)
print(beap_test.beap_list)
beap_test.checker()
print(beap_test.search(10))
print(beap_test.search(11))
print(beap_test.insert(11))
print(beap_test.beap_list)
beap_test.checker()
print(beap_test.extract(0))
print(beap_test.beap_list)
beap_test.checker()
print(beap_test.min_beap())
print(beap_test.max_beap())
# fitting curve
def funlog(self, x, a, b, c):
return a * np.log(b*x) + c
def funsqrt(self, x, a, b, c):
return a * np.sqrt(b*x) + c
# extensively test for search function of binary heap and beap
def extensive_searchcompare(self):
node_number = []
binheap_usetime = []
beap_usetime = []
# set the node of the binary heap
# from 1000 to 5000,500 per increase
for count in range(1000, 20001, 100):
# record node number
node_number.append(count)
# get heap value at random
insert_list = random.sample(range(0, count), count)
# Initializing the heap and beap
ex_binheap = bin_heap()
ex_binheap.build_binheap(insert_list)
ex_beap = beap()
ex_beap.build_beap(insert_list)
# set search node of heap
heap_searchnode = count - 1
# calculate the binary heap run time
binheap_starttime = time.process_time()
ex_binheap.search(ex_binheap.heap_list[heap_searchnode])
binheap_endtime = time.process_time()
# record current runtime of the node number(ms)
binheap_runtime = (binheap_endtime-binheap_starttime)*1000
binheap_usetime.append(binheap_runtime)
# get the worest search node of beap
beap_searchnode = count - 1
height = ex_beap.getheight(beap_searchnode)
left_range, right_range = ex_beap.getrange(height)
if beap_searchnode == right_range:
beap_searchnode = count - 1
else:
left_rangeup, right_rangeup = ex_beap.getrange(height-1)
beap_searchnode = right_rangeup
# get the use time of beap(ms)
beap_starttime = time.process_time()
ex_beap.search(ex_beap.beap_list[beap_searchnode])
beap_endtime = time.process_time()
beap_runtime = (beap_endtime - beap_starttime)*1000
beap_usetime.append(beap_runtime)
# draw the performance map
# Fitting the curve
nn = np.array(node_number)
ht = np.array(binheap_usetime)
bt = np.array(beap_usetime)
# bin_heap fitting curve
f1 = np.polyfit(nn, ht, 1)
p1 = np.poly1d(f1)
y1 = p1(nn)
# beap fitting curve
yn2 = bt + 0.2*np.random.normal(size=len(nn))
popt2, pcov2 = curve_fit(self.funsqrt, nn, yn2)
y2 = self.funsqrt(nn, *popt2)
# output picture
plt.plot(node_number, binheap_usetime, 'x', color='r', label="Bin_HEAP original node")
plt.plot(node_number, y1, 'o-', color='g', label="Bin_HEAP fitting curve")
# plt.plot(node_number, beap_usetime, 'o', color='b', label="BEAP original node")
# plt.plot(node_number, y2, 's-', color='r', label="BEAP fitting curve")
# horizontal coordinate
plt.xlabel("node number")
# vertical coordinate
plt.ylabel("run time(ms)")
# title of picture
# plt.title("The Search Performance of Bin-heap")
plt.title("The Search Performance of Beap")
# loction of the picture
plt.legend(loc="best")
plt.show()
# extensively test for max function of binary heap and beap
def extensive_maxcompare(self):
node_number = []
binheap_usetime = []
beap_usetime = []
# set the node of the binary heap
# from 1000 to 5000,
for count in range(1000, 20001, 100):
# record node number
node_number.append(count)
# get heap value at random
insert_list = random.sample(range(0, count), count)
# Initializing the heap and beap
ex_binheap = bin_heap()
ex_binheap.build_binheap(insert_list)
ex_beap = beap()
ex_beap.build_beap(insert_list)
# calculate the binary heap run time
binheap_starttime = time.process_time()
ex_binheap.heap_max()
binheap_endtime = time.process_time()
# record current runtime of the node number
binheap_runtime = (binheap_endtime-binheap_starttime)*1000
binheap_usetime.append(binheap_runtime)
# get the use time of beap(ms)
beap_starttime = time.process_time()
ex_beap.max_beap()
beap_endtime = time.process_time()
beap_runtime = (beap_endtime - beap_starttime)*1000
beap_usetime.append(beap_runtime)
# draw the performance map
# Fitting the curve
nn = np.array(node_number)
ht = np.array(binheap_usetime)
bt = np.array(beap_usetime)
# bin_heap fitting curve
f1 = np.polyfit(nn, ht, 2)
p1 = np.poly1d(f1)
y1 = p1(nn)
# beap fitting curve
f2 = np.polyfit(nn, bt, 2)
p2 = np.poly1d(f2)
y2 = p2(nn)
# output picture
plt.plot(node_number, binheap_usetime, 'x', color='r', label="Bin_HEAP original node")
plt.plot(node_number, y1, 'o-', color='g', label="Bin_HEAP fitting curve")
# plt.plot(node_number, beap_usetime, 'x', color='b', label="BEAP original node")
# plt.plot(node_number, y2, 'o-', color='r', label="BEAP fitting curve")
# horizontal coordinate
plt.xlabel("node number")
# vertical coordinate
plt.ylabel("run time")
# title of picture
plt.title("The Max Performance of Bin-heap")
# plt.title("The Max Performance of Beap")
# loction of the picture
plt.legend(loc="best")
plt.show()
# extensively test for isnert function of binary heap and beap
def extensive_insertcompare(self):
node_number = []
binheap_usetime = []
beap_usetime = []
# set the node of the binary heap
# from 1000 to 5000,500 per increase
for count in range(1000, 20001, 100):
# record node number
node_number.append(count)
# get heap value at random
insert_list = random.sample(range(1, count+1), count)
# Initializing the heap and beap
ex_binheap = bin_heap()
ex_binheap.build_binheap(insert_list)
ex_beap = beap()
ex_beap.build_beap(insert_list)
# # set insert value of heap and beap
insert_node = count//2
# calculate the binary heap run time
binheap_starttime = time.process_time()
ex_binheap.insert(insert_node)
binheap_endtime = time.process_time()
# record current runtime of the node number
binheap_runtime = (binheap_endtime-binheap_starttime)*1000
binheap_usetime.append(binheap_runtime)
# get the use time of beap(ms)
beap_starttime = time.process_time()
ex_beap.insert(insert_node)
beap_endtime = time.process_time()
beap_runtime = (beap_endtime - beap_starttime)*1000
beap_usetime.append(beap_runtime)
# draw the performance map
# fitting curve
nn = np.array(node_number)
ht = np.array(binheap_usetime)
bt = np.array(beap_usetime)
# get binary heap fitting parameters
ht1 = self.funlog(nn, 2.3, 2.1, 0.5)
yn1 = ht1 + 0.2*np.random.normal(size=len(nn))
popt1, pcov1 = curve_fit(self.funlog, nn, yn1)
y1 = self.funlog(nn, *popt1)
# get the beap fitting parameters
yn2 = bt + 0.2*np.random.normal(size=len(nn))
popt2, pcov2 = curve_fit(self.funsqrt, nn, yn2)
y2 = self.funsqrt(nn, *popt2)
# output picture
plt.plot(node_number, yn1, 'x', color='r', label="Bin_HEAP original node")
plt.plot(node_number, y1, 'o-', color='g', label="Bin_HEAP fitting curve")
# plt.plot(node_number, beap_usetime, 'o', color='b', label="BEAP original node")
# plt.plot(node_number, y2, 's-', color='r', label="BEAP fitting curve")
# horizontal coordinate
plt.xlabel("node number")
# vertical coordinate
plt.ylabel("run time")
# title of picture
plt.title("The Insert Performance of Bin-heap")
# plt.title("The Insert Performance of Beap")
# loction of the picture
plt.legend(loc="best")
plt.show()
# extensively test for extract function of binary heap and beap
def extensive_extractcompare(self):
node_number = []
binheap_usetime = []
beap_usetime = []
# set the node of the binary heap
# from 1000 to 5000,
for count in range(1000, 20001, 100):
# record node number
node_number.append(count)
# get heap value at random
insert_list = random.sample(range(0, count), count)
# Initializing the heap and beap
ex_binheap = bin_heap()
ex_binheap.build_binheap(insert_list)
ex_beap = beap()
ex_beap.build_beap(insert_list)
# remove the root node
# calculate the binary heap run time
binheap_starttime = time.process_time()
ex_binheap.extract(0)
binheap_endtime = time.process_time()
# record current runtime of the node number
binheap_runtime = (binheap_endtime-binheap_starttime)*1000
binheap_usetime.append(binheap_runtime)
# get the use time of beap(ms)
beap_starttime = time.process_time()
ex_beap.extract(0)
beap_endtime = time.process_time()
beap_runtime = (beap_endtime - beap_starttime)*1000
beap_usetime.append(beap_runtime)
# draw the performance map
# fitting curve
nn = np.array(node_number)
ht = np.array(binheap_usetime)
bt = np.array(beap_usetime)
# get binary heap fitting parameters
ht1 = self.funlog(nn, 2.3, 2.1, 0.5)
yn1 = ht1 + 0.2*np.random.normal(size=len(nn))
popt1, pcov1 = curve_fit(self.funlog, nn, yn1)
y1 = self.funlog(nn, *popt1)
# get the beap fitting parameters
yn2 = bt + 0.2*np.random.normal(size=len(nn))
popt2, pcov2 = curve_fit(self.funsqrt, nn, yn2)
y2 = self.funsqrt(nn, *popt2)
# output picture
plt.plot(node_number, yn1, 'x', color='r', label="Bin_HEAP original node")
plt.plot(node_number, y1, 'o-', color='g', label="Bin_HEAP fitting curve")
# plt.plot(node_number, beap_usetime, 'o', color='b', label="BEAP original node")
# plt.plot(node_number, y2, 's-', color='r', label="BEAP fitting curve")
# horizontal coordinate
plt.xlabel("node number")
# vertical coordinate
plt.ylabel("run time")
# title of picture
plt.title("The Extract Performance of Bin-heap")
# plt.title("The Extract Performance of Beap")
# loction of the picture
plt.legend(loc="best")
plt.show()
test1 = Test()
# Functional implementation testing
test1.bin_heap_function()
test1.beap_function()
# Extensive testing and complexity performance
test1.extensive_searchcompare()
test1.extensive_maxcompare()
test1.extensive_insertcompare()
test1.extensive_extractcompare()