## 中位数和顺序统计量

选择和顺序统计量问题

顺序统计量：一个包含n个元素的集合中第i和顺序统计量指的是集合中第i小的元素

若=1，第i个顺序统计量为集合中的最小值(minimum)。

若i=n，第i个顺序统计量为集合中的最大值(maximum)。

若n为奇数，$i=(1+n)/2$，第i个顺序统计量为集合中的中位数(median)。

若n为偶数，$i=\lfloor (1+n)/2 \rfloor$，第i个顺序统计量为集合中的下中位数(lower
median).

若n为偶数，$i=\lceil (1+n)/2 \rceil=n/2+1$，第i个顺序统计量为集合中的上中位数(upper median).

为了简化问题，本书中统一取第$\lfloor (1+n)/2\rfloor$个顺序统计量作为集合中的中位数。

假设集合中所有元素均不相同，可以将中位数问题推广到一般选择问题

输入：一个包含 n 个互不相同元素的集合 A ，整数$ 1≤i≤n$ 。

输出： x∈A ，且 A 中恰好有 i−1 个元素小于 x 。



### 堆

堆数据结构是一种数组对象，它可以被视为一棵完全二叉树

通过下标决定它的父节点，左孩子和右孩子

堆排序的应用：最大/最小优先级队列

作业调度

优先级队列通过堆实现

INSERT(S,x)

MAXIMUM(S):

Extract-max(S):

INCREASE-KEY(s,x,k)

HEAP-INCREASE-KEY实现了INCREASE-KEYCAOZUO 

 **二叉堆(binary heap)**可以用数组表示，这个数组对应一棵[完全二叉树](https://zhida.zhihu.com/search?content_id=209680208&content_type=Article&match_order=1&q=完全二叉树&zhida_source=entity)。根据层序遍历顺序对完全二叉树结点进行编号，其中根结点下标为 1 

堆可以分为：

[最大堆](https://zhida.zhihu.com/search?content_id=209680208&content_type=Article&match_order=1&q=最大堆&zhida_source=entity)**(max-heap)**：也被翻译成大顶堆或大根堆，堆顶元素即二叉堆根结点元素最大，除根结点外，有 A[PARENT(i)]≥A[i] 。

[最小堆](https://zhida.zhihu.com/search?content_id=209680208&content_type=Article&match_order=1&q=最小堆&zhida_source=entity)**(max-heap)**：也被翻译成小顶堆或小根堆，堆顶元素即二叉堆根结点元素最小，除根结点外，有 A[PARENT(i)]≤A[i] 。

堆排序既可以使用最大堆也可以使用最小堆，堆排序从小到大排序可以借助最大堆，堆排序从大到小排序可以借助最小堆。

优先队列既可以使用最小堆也可以使用最大堆。

维护堆的性质

我们要检查数组 A 下标 i 的元素，根据堆的性质，将其调整到合理的位置。

在堆中下标 i 的元素发生变化的时，我们要对堆进行维护，将其重新调整为一个堆，使得堆的性质不变。

我们使用[MAX-HEAPIFY](https://zhida.zhihu.com/search?content_id=209707906&content_type=Article&match_order=1&q=MAX-HEAPIFY&zhida_source=entity)对元素进行调整，伪代码如下：

```
MAX-HEAPIFY(A, i)

  l = LEFT(i)

  r **=** RIGHT(i)

  **if** l ≤ A.heap**-**size and A[l] **>** A[i]

​    largest **=** l

  **else** largest **=** i

  **if** r ≤ A.heap**-**size and A[r] **>** A[largest]

​    largest **=** r

  **if** largest ≠ i

​    exchange A[i] with A[largest]

​    MAX**-**HEAPIFY(A, largest)

```

就是检查下标 i 的结点，和其左右孩子进行比对，如果不是三者中最大的，就说明不符合大顶堆性质，该结点和三个结点中最大的结点进行交换，递归执行。

评：MAX-HEAPIFY只调整了堆中下标为 i 的这一个结点，并非所有结点，一些教材把这个方法命名为DOWN-ADJUST或者HEAP-ADJUST，意思为向下调整或者调整堆，的确非常生动。

就是某子树根结点和其左子树或者右子树发生元素交换，检查和交换的代价为 Θ(1) ，设子树规模为 n ，左子树或者右子树最大规模为 2n/3 （详见练习6.2-2）。

MAX-HEAPIFY的递归式为：(6.1)T(n)≤T(2n/3)+Θ(1)

根据[主定理](https://zhida.zhihu.com/search?content_id=209707906&content_type=Article&match_order=1&q=主定理&zhida_source=entity)解得： T(n)=O(lg⁡n)

如果某结点的高度为 h ，对该结点进行MAX-HEAPIFY操作的运行时间为 O(h) 。

所以BUILD-MAX-HEAP的运行时间渐近上界为 O(n) 。

建堆

同理，我们可以用BUILD-MIN-HEAP构建小顶堆，每次调整调用[MIN-HEAPIFY](https://zhida.zhihu.com/search?content_id=209759438&content_type=Article&match_order=1&q=MIN-HEAPIFY&zhida_source=entity)（详见练习6.2-3），建堆过程的伪代码如下：

```

BUILD**-**MIN**-**HEAP(A, n)

  A.heap**-**size **=** n

  **for** i **=** floor(n**/**2) down to 1

​    MIN**-**HEAPIFY(A, i)
```



BUILD-MIN-HEAP的运行时间渐近上界为 O(n) 。

堆排序算法

利用[BUILD-MAX-HEAP](https://zhida.zhihu.com/search?content_id=209857835&content_type=Article&match_order=1&q=BUILD-MAX-HEAP&zhida_source=entity)对数组 A[1:n] 转化为大根堆，因为数组元素的最大元素位于根结点 A[1] 中，与 A[n] 进行互换，最大元素就被放到了正确的位置。除去元素 A[n] ，数组A[1:n−1]转化为大根堆，根结点 A[1] 中，与 A[n−1] 进行互换，第二大的元素被就放到了正确的位置。不断重复这一过程，直到堆的大小降为 2 ，这时候数组 A[1:n] 排序完成。

堆排序HEAPSORT伪代码如下：

```
HEAPSORT(A, n)

  BUILD**-**MAX**-**HEAP(A, n)

  **for** i **=** n downto 2

​    swap(A[1], A[i])

​    A.heap**-**size **=** A.heap**-**size **-** 1

​    MAX**-**HEAPIFY(A, 1)


```

HEAPSORT过程的运行时间为 O(nlg⁡n) ，调用BUILD-MAX-HEAP的运行时间为 O(n) ， n−1 次调用[MAX-HEAPIFY](https://zhida.zhihu.com/search?content_id=209857835&content_type=Article&match_order=1&q=MAX-HEAPIFY&zhida_source=entity)，每次时间为 O(lg⁡n) 。



###  优先队列(priority queue)

一组包含关键字(key)的元素的集合 S ，分为以下两种类型：

每次取出的是具有最高优先权的元素（最大、最小堆），并不是个队列，实际上是个二叉树。

判断是否为空

查询队列大小

加入元素

删除元素

返回优先权最高的元素

[最大优先队列](https://zhida.zhihu.com/search?content_id=209962097&content_type=Article&match_order=1&q=最大优先队列&zhida_source=entity)**(max-priority queue)**：

- INSERT(S,x,k) ：向集合 S 中插入关键字为 k 的元素 x ， S=S∪x 。
- MAXIMUM(S) ：返回集合 S 中关键字最大的元素。
- EXTRACT-MAX(S) ：移除并返回集合 S 中关键字最大的元素。
- INCREASE-KEY(S,x,k) ：将元素 x 的关键字值增加到 k ，设元素 x 的关键字值原为 k0 ，则 k≥k0 。

最大优先队列可以应用于基于优先级的作业调度算法，作业对应的关键字越大，该作业的优先级越高。

评：最大优先队列用于可用于元素按照关键字从大到小排序的在线算法。

[最小优先队列](https://zhida.zhihu.com/search?content_id=209962097&content_type=Article&match_order=1&q=最小优先队列&zhida_source=entity)**(min-priority queue)**：

- INSERT(S,x,k) ：向集合 S 中插入关键字为 k 的元素 x ， S=S∪x 。
- MINIMUM(S) ：返回集合 S 中关键字最小的元素。
- EXTRACT-MIN(S) ：移除并返回集合 S 中关键字最小的元素。
- DECREASE-KEY(S,x,k) ：将元素 x 的关键字值减小到 k ，设元素 x 的关键字值原为 k0 ，则 k≤k0 。

```
MAX-HEAP-MAXIMUM(A)
    if A.heap-size < 1
        error "heap underflow"
    return A[1]

MAX-HEAP-EXTRACT-MAX(A)
    max = MAX-HEAP-MAXIMUM(A)
    A[1] = A[A.heap-size]
    A.heap-size = A.heap-size - 1
    MAX-HEAPIFY(A, 1)
    return max

MAX-HEAP-INCREASE-KEY(A, x, k)
    if k < x.key
        error "new key is smaller than current key"
    x.key = k
    find the index i in array A where object x occurs
    while i > 1 and A[PARENT(i)].key < A[i].key
        exchange A[i] with A[PARENT(i)], updating the information that maps priority queue objects to array indices
        i = PARENT(i)

MAX-HEAP-INSERT(A, x, n)
    if A.heap-size == n
        error "heap overflow"
    A.heap-size = A.heap-size + 1
    k = x.key
    x.key = -∞
    A[A.heap-size] = x
    map x to index heap-size in the array
    MAX-HEAP-INCREASE-KEY(A, x, k)


```

一个N*M的矩形监狱，起始点在b。拯救过程中，上下左右四个方向需要一个单位时间，杀死一个守卫额外需要一个单位时间，计算拯救a需要的时间。

优先队列和普通的广度搜索的思路是一样的。

从起点到每个点都有时间，



传统的bfs局限在于并不是层次递增的，希望多花时间的结点在队列中向后推迟一层出队。




### 线性排序

#### 计数排序

设由 n 个元素组成的输入序列每个元素都是 0 到 k 区间内的一个整数，计数排序的运行时间为 Θ(n+k) ，当 k=O(n) 时，计数排序的运行时间为 Θ(n) 。

设输入序列为 A[1:n] ，输出序列为 B[1:n] ，临时存储空间为 C[0:k] ，计数排序伪代码如下：

```
COUNTING-SORT(A, n, k)

  let B[1:n], C[0:k] be new arrays

  **for** i **=** 0 to k

​    C[i] **=** 0

  **for** j **=** 1 to n

​    C[A[j]] **=** C[A[j]] **+** 1 

  *// C[i] now contains the number of elements equal to i.*

  **for** i **=** 1 to k

​    C[i] **=** C[i] **+** C[i **-** 1] 

  *// C[i] now contains the number of elements less than or equal to i.*

  *// Copy A to B, starting from the end of A*

  **for** j **=** n downto 1

​    B[C[A[j]]] **=** A[j]

​    C[A[j]] **=** C[A[j]] **-** 1 *// to handle duplicate values*
```



评：计数排序运用了[哈希表](https://zhida.zhihu.com/search?content_id=210358387&content_type=Article&match_order=1&q=哈希表&zhida_source=entity)与[前缀和](https://zhida.zhihu.com/search?content_id=210358387&content_type=Article&match_order=1&q=前缀和&zhida_source=entity)思想，第一次 C[0:k] 作为一个哈希表或 count 数组统计每个元素的出现次数，第二次 C[0:k] 通过前缀和计算出每个不同元素在数组中的排序位置，可以视为 rank 数组，最后将元素放到输出数组中，也是一个收集元素过程，注意此过程中要排除已放到输出数组中的元素，动态维护每个未放到输出数组中的不同元素在数组中的排序位置。

设数组 A[1:n] 中的每个元素有 d 位，第 1 位最低，第 d 位最低，RADIX-SORT伪代码如下：

 ```

RADIX**-**SORT(A, n, d)

  **for** i **=** 1 to d

​    use a stable sort to sort array A[1**:**n] on digit i
 ```



RADIX-SORT并没有指明其中使用的[稳定排序](https://zhida.zhihu.com/search?content_id=210433744&content_type=Article&match_order=1&q=稳定排序&zhida_source=entity)是什么，一般使用[COUNTING-SORT](https://zhida.zhihu.com/search?content_id=210433744&content_type=Article&match_order=1&q=COUNTING-SORT&zhida_source=entity)。

#### **桶排序(Bucket sort)**

桶排序假设输入数据服从均匀分布**(uniform distribution)**，平均运行时间为 O(n) 。

假设输入数据均匀独立分布在区间 [0,1) 上，桶排序将区间 [0,1) 分成 n 个大小相等的子区间，称这些子区间为**桶(bucket)。**

设输入数组 A[1:n] ，数组中每个元素 0≤A[i]<1 ，开辟一个辅助数组 B[0:n−1] 表示 n 个桶，每个桶为一个**链表(linked list)**，BUCKET-SORT伪代码如下：

```

BUCKET**-**SORT(A, n)

  let B[0 **:** n **-** 1] be a **new** array

  **for** i **=** 0 to n **-** 1

​    make B[i] an empty list

  **for** i **=** 1 to n

​    insert A[i] into list B[⌊n · A[i]⌋]

  **for** i **=** 0 to n **-** 1

​    sort list B[i] with insertion sort

  concatenate the lists B[0], B[1], ... , B[n **-** 1] together in order

  **return** the concatenated lists
```