今日是今日毕

今天需要学习内容

1. 手写快速选择算法
2. 手写最大堆数据结构

A. 快速选择算法

A.1 对应问题

前k大/小数字，第k大/小数字。

A.2 算法原理及步骤

举例：
输入对于未知顺序的数组arr{0,2,...,n-1}
输出第k小数字

1. 初始化l=0,r=arr.length-1,index=k-1
2. 对arr[l~r]数组进行随机划分，返回索引q,满足arr[l~q-1]<=a[q]<=arr[q+1~r]
3. 对返回值q进行判断：
   若q=index,执行步骤4
   若q>index,说明第k小数字在l~q-1中，更新r=q-1,重复步骤2
   若q<index,说明第k小数字在q+1~r中，更新l=q+1,重复步骤2
4. 输出arr[index]

A.3 伪代码

• quickSelect()

  Input data arrayarr{},intleft,intright,intindex
Outputdataarr[index]

  1. get initial: left=arr.begin, right=arr.end(), index=k // only for the first function call
  2. index_r $\leftarrow$ randomPartition(arr{},left,right)
  3. if index_r $\leq$ index,then: right $\leftarrow$ index_r - 1
     return quickSelect(arr{},left,right,index)
     else if index_r $\leq$ index, then
     left $\leftarrow$ index_r + 1
     return quickSelect(arr{},left,right,index)
     else if index_r $=$ index, then
     return arr[index]
• randomPartition()
输入数组arr{},左索引left,右索引right
输出数值arr[index]
• partition()

A.4 复杂度计算

期望复杂度为O(n),空间复杂度O(log(n))

A.5 C++代码

B. 最大堆数据结构

B.1 对应问题

前k大/小数字，第k大/小数字。

B.2 算法原理及实现

B.3 伪代码

B.4 复杂度计算

B.5 C++代码