斯坦福算法专项课程Course2 week3习题解析

这一部分将带来Course2 week3的习题解析。

选择题

选择题 1

假设您使用排好序的数组(例如,从最大到最小)实现优先级队列的功能。

Insert和Extract-Min的最差运行时间分别是多少?(假设您有足够大的数组来容纳您所面临的插入。)

  • $\Theta(1)$和$\Theta(\log n)$
  • $\Theta(n)$和$\Theta(1)$
  • $\Theta(n)$和$\Theta( n)$
  • $\Theta(1)$和$\Theta(n)$

Insert需要移动后续的元素,最坏时间复杂度为$\Theta(n)$,Extract-Min直接弹出最后一个元素即可,最坏时间复杂度为$\Theta(1)$

选择题 2

假设您使用未排序的数组实现优先级队列的功能。

Insert和Extract-Min的最差运行时间分别是多少?(假设您有足够大的数组来容纳您所面临的插入。)

  • $\Theta(1)$和$\Theta(\log n)$
  • $\Theta(n)$和$\Theta(1)$
  • $\Theta(n)$和$\Theta( n)$
  • $\Theta(1)$和$\Theta(n)$

因为没有排序,所以插入只要插入队尾即可,最坏时间复杂度为$\Theta(1)$,但是Extract-Min需要遍历所有元素,最坏时间复杂度为$\Theta(n)$

选择题 3

你有一个$n$个元素的Heap,它支持Insert和Extract-Min操作。以下哪项任务可以在$O(\log n)$时间内完成?

  • 都不是。
  • 找到存储在堆中的最大元素。
  • 找到存储在堆中的元素的中位数。
  • 找到存储在堆中的第五小元素。

找到第五小的元素可以在$O(\log n)$时间内完成,直接弹出$5$次即可。关于中位数,课件中需要size这个量,这里没有提到,所以应该是没有选择这项的原因。

选择题 4

假设你有$n$个节点的二叉树,按讲座中计算size,计算每个节点的size需要多少时间?

  • $\Theta(n\log n)$
  • $\Theta(height)$
  • $\Theta(n)$
  • $\Theta(n^2)$

从根节点一层一层往上计算即可,时间复杂度为$\Theta(n)$

选择题 5

假设我们将红黑树的第三个不变量放松到连续三个红色的属性。也就是说,如果一个节点及其父节点都是红色,那么它的子节点都必须是黑色的。称其relaxed red-black。以下哪项陈述不正确?

  • 每个二叉搜索树都可以变成一个relaxed red-black(通过节点的一些着色为黑色或红色)。
  • $n$个节点的relaxed red-black高度为$O(\log n)$
  • 每棵红黑树也是一棵relaxed red-black
  • 存在一棵relaxed red-black不是红黑树

由课件中讨论可知,第二个选项正确;显然red-black一定是relaxed red-black,所以第三个选项正确;用课件中红黑树的第一个例子可以说明第四项正确;显然第一个选项错误。

编程题

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#定义堆
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

filename = 'data.txt'
#构造堆
max_heap = Heap(0)
min_heap = Heap(1)
#计数
cnt = 1
#结果
Sum = 0

with open(filename) as f:
for i in f.readlines():
num = int(i)
#处理第一个元素
if (cnt == 1):
Sum += num
max_heap.insert(num)
cnt += 1
continue
#最大堆的元素
n0 = max_heap.peek()
if (num < n0):
max_heap.insert(num)
else:
min_heap.insert(num)
#判断是否平衡
if (max_heap.len - min_heap.len == 2):
n1 = max_heap.extract()
min_heap.insert(n1)
elif (min_heap.len - max_heap.len == 2):
n1 = min_heap.extract()
max_heap.insert(n1)
#计算中位数
if (max_heap.len >= min_heap.len):
Sum += max_heap.peek()
else:
Sum += min_heap.peek()

print(Sum % 10000)