algorithm_lab/binary_heap.py at master · Yumingyuan/algorithm_lab · GitHub

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
def left(search_data,i):
	set_length=len(search_data)
	if i==0 or 2*i>set_length-1:
		return
	else:
		return 2*i
def right(search_data,i):
	set_length=len(search_data)
	if i==0 or 2*i+1>set_length-1:
		return
	else:
		return 2*i+1
def parent(search_data,i):
	if i==1:
		print("Root Node!")
		result=search_data[i]
	elif i>len(search_data)-1:
		print("too huge")
		result=0
	elif i/2>=1:
		result=search_data[int(i/2)]
	return result
def height(search_data,i):
	count=0
	start=i
	while left(search_data,start) is not None:
		start=start*2
		count=count+1
	return count
def heapify(search_data,i):
	left_num=left(search_data,i)
	right_num=right(search_data,i)
	largest=0
	if left_num is None:
		return
	elif right_num is not None and left_num is not None:
		if left_num<len(search_data) and search_data[left_num]>search_data[i]:
			largest=left_num
		else:
			largest=i
		if left_num<len(search_data) and search_data[right_num]>search_data[largest]:
			largest=right_num
		if largest!=i:#need exchange
			temp=search_data[i]
			search_data[i]=search_data[largest]
			search_data[largest]=temp
			print("heapify1:",i,search_data)
			heapify(search_data,largest)#when exchange occur you need heapify
	elif right_num is None and left_num is not None:
		if left_num<len(search_data) and search_data[left_num]>search_data[i]:
			largest=left_num
		else:
			largest=i
		if largest!=i:#need exchange
			temp=search_data[i]
			search_data[i]=search_data[largest]
			search_data[largest]=temp
			print("heapify2:",i,search_data)
			heapify(search_data,largest)#when exchange occur you need heapify
#build function,to build up a big heap
def build_heap(search_data):
	length=len(search_data)
	mid=length/2
	mid=int(mid+1)
	for i in range(mid,0,-1):
		heapify(search_data,i)
def extract_heap_max(search_data):
	length=len(search_data)
	if length<1:
		return
	max_num=search_data[1]
	search_data[1]=search_data.pop()#get the last item of search_data and  make the list length minor 1
	heapify(search_data,1)
	return max_num
if __name__=="__main__":
	test_data=[0,16,14,10,8,7,9,3,2,4,1]
	test_data1=[0,4,5,3,2,7,9,1,11,8,12]
	test_data2=[0,4,5,3,2,7,9,1,11,8,12]
	print("5's left son:",left(test_data,5))
	print("6's left son:",left(test_data,6))
	print("3's right son:",right(test_data,3))
	print("6's right son:",right(test_data,6))
	print("1's parent:",parent(test_data,1))
	print("11's parent:",parent(test_data,11))
	print("5's parent:",parent(test_data,5))
	print("test_data tree's heigth:",height(test_data,2))
	print("begin heapify the node 1:",test_data1)
	heapify(test_data1,1)
	print("begin build heap:",test_data2)
	build_heap(test_data2)
	print('After build heap:',test_data2)
	print("begin extract the max num from heap!")
	print("Extract heap:",extract_heap_max(test_data2))