斯坦福算法专项课程Course2 week3算法实现

这次回顾Course2 week3的算法。

课程地址:https://www.coursera.org/specializations/algorithms

Heap

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
class Heap():
def __init__(self, Type):
'''
type定义堆类型,x=1表示最小堆, x=0表示最大堆
'''
#堆的索引从1开始,堆守存放一个无用的元素
self.heap = [-1]
self.len = 0
#type定义堆类型,x=1表示最小堆, x=0表示最大堆
self.type = Type

def insert(self, x):
'''
插入
'''
#进入数组
self.heap.append(x)
#更新长度
self.len += 1
#索引
i = self.len
#最小堆
if self.type == 1:
while (i >= 2):
#不满足最小堆的定义时交换父子
if self.heap[i] < self.heap[i // 2]:
self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]
i = i // 2
else:
break
#最大堆
elif self.type == 0:
while (i >= 2):
#不满足最大堆的定义时交换父子
if self.heap[i] > self.heap[i // 2]:
self.heap[i], self.heap[i // 2] = self.heap[i // 2], self.heap[i]
i = i // 2
else:
break

def peek(self):
#返回最小值(最大值),不删除
return self.heap[1]

def extract(self):
'''
弹出最小值(最大值)
'''
#交换元素
self.heap[1], self.heap[-1] = self.heap[-1], self.heap[1]
#目标元素
a = self.heap[-1]
#删除元素
del self.heap[-1]
#索引
i = 1
#更新长度
self.len -= 1
n = self.len
#最小堆
if self.type == 1:
while (i <= n / 2):
#左节点的位置
j = 2 * i
#找到更小的子节点
if (j + 1 <= n and self.heap[j + 1] < self.heap[j]):
j += 1
#不满足最小堆的定义时交换父子
if self.heap[i] > self.heap[j]:
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
i = j
else:
break
#最大堆
elif self.type == 0:
while (i <= n / 2):
#左节点的位置
j = 2 * i
#找到更小的子节点
if (j + 1 <= n and self.heap[j + 1] > self.heap[j]):
j += 1
#不满足最大堆的定义时交换父子
if self.heap[i] < self.heap[j]:
self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
i = j
else:
break
return a

Binary Search Tree

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
import numpy as np

class BST():
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None

def search(self, data):
if (self.data == data):
return data
elif (data < self.data):
if (self.lchild != None):
return self.lchild.search(data)
else:
return None
else:
if (self.rchild != None):
return self.rchild.search(data)
else:
return None

def insert(self, data):
if (data < self.data):
if (self.lchild != None):
self.lchild.insert(data)
else:
self.lchild = BST(data)
else:
if (self.rchild != None):
self.rchild.insert(data)
else:
self.rchild = BST(data)

def in_order(self):
if (self.lchild != None):
self.lchild.in_order()
print(self.data)
if (self.rchild != None):
self.rchild.in_order()

####测试
lst = np.random.randint(0, 100, 30)
Bst = BST(0)
for i in lst:
Bst.insert(i)
Bst.in_order()

lst = np.random.randint(0, 100, 5)
for i in lst:
print(i, Bst.search(i))