这一部分将带来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，所以第三个选项正确；用课件中红黑树的第一个例子可以说明第四项正确；显然第一个选项错误。

编程题

#定义堆
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)