chap6 堆排序

堆排序 算法导论

内容

堆

1. （二叉堆）是一个数组，可以被看成是一个近似的完全二叉树。

2. 基本操作：

   Parent(i)
   return i/2#向下取整

   Left(i)
   return 2i

   Right(i)
   return 2i + 1

最大堆和堆排序

1. 除了根节点外的所有节点$i$都要满足: $A[parent(i)]\geq A[i]$,类似的可以定义最小堆。前者用于排序，后者通常用于构建优先队列
2. 堆排序在时间复杂度与归并排序相当，但他是原址排序的，因而优于前者

3. 最大堆的基本过程

   Max-Heapify ——$O(\lg n)$,维护最大堆的性质
   Build-Max-Heap——$O(n)$，建堆
   HeapSort——$O(n \lg n)$，排序
   Max-Heap-Insert,Heap-Extract-Max,Heap-Increase-Key,Heap-Maximum——$O(\lg n)$，用于实现一个优先队列

伪代码

Max-Heapify

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 <= heap_size and A[r > A[i]
    largest = r
 if largest != i
    exchange A[i] with A[largest]
    Max-Heapify(A,largest)

Build-Max-Heap

由于子数组A[$\lfloor n/2\rfloor$+1...n]的元素都是叶节点，因而不需要维护堆性质

Build-Max-Heap(A)
 A.heap_size = A.length
 for i = A.length/2 downto 1 #向下取整
     Max-Heapify(A,i)

HeapSort

不断取出堆中的第一个元素，再进行维护

HeapSort(A)
 Build-Max_Heap(A)
 for i = A.length downto 2
    exchange A[i] with A[1]
    A.heap_size = A.heap_size - 1
    Max_Heapify(A,1)

优先队列

概念

优先队列是一种用来维护一组元素构成的集合$S$的数据结构。集合中，每个元素都有一个相关的值，成为关键字(key)，

最大优先队列

支持一下操作

Inset(S,x)——$O(\lg n)$,将x插入到S中
Maximumn(S)——$O(1)$,,返回S中具有最大关键字的元素
Extract-Max(S)——$O(\lg n)$,去掉并返回S中具有最大关键字的元素
Increase-Key(S,x,k)——$O(\lg n)$,将元素x的关键字增加至k(k>x)

Heap-Maximum

Heap-Maximum(A)
    return A[1]

Heap-Extract-Max

Heap-Extract-Max(A)

if A.heap_size < 1
    error"heap underflow"
max = A[1]
A[1] = A[A.heap_size]
A.heap_size = A.heap_size - 1
Max-Heapify(A,1)
 return max

Heap-Increase-Key

Heap-Increase-Key(A,i,key)

if key < A[i]
    error "new key is smaller than current key"
A[i] = key
while i > 1 and A[Parent(i)] < A[i]
    exchange A[i] with A[Parent(i)]
    i = Parent(i)

对exchange操作的改进

while i > 1 and A[Parent(i)] < key
    A[i] = A[Parent(i)]
    i = Parent(i)
A[i] = key

Max-Heap-Insert

注意到Max-Heapify(A,i),是将以i为根节点的子树变成最大堆，而上面的Heap-Increase-key 是从当前节点往上进行操作；另一方面如果是将A1设置为无穷大再进行increase操作的话，需要对根节点进行最大堆的维护

Max-Heap-Insert(A,key)

A.heap_size = A.heap_size + 1
A[A.heap_size] = -00
Heap-Increase-Key(A,A.heap_size,key)

习题中的算法

6.5-9 k路归并

1. 问题：设计算法，时间复杂度为$O(n\lg k)$,能将k个有序链表合并成一个有序链表，这里n是总的元素的个数（提示：用最小堆）

2. 基本思路：

   1. 从k个链表中取出各自的最小元素，并将这些元素建成一个最小堆——$O(k)$
   2. 从该最小堆中取出最小元素，放在最终的链表中，再从取出元素原先所在的链表中取出最小元素，放入最小堆中，并维护最小堆性质——$O(\lg k)$
   3. 重复步骤2 $n-k$次，得到最终链表

6-1 用插入的方式建堆

Build-Max-Heap(A)

A.heap_size = 1
for i = 2 to A.length
    Max-Heap-Insert(A,A[i])

算法分析：会调用n-1次插入操作，因此时间上限时$O(n \lg n)$;其次，考虑原数组是递增数组的最坏情况下，此时每个插入操作运行时间是$\Theta (lg i)$,计算可得，此时下界是$\Omega (n\lg n)$,因而此时复杂度为$\Theta (nlg n)$

6-2 d叉堆（内部结点有d个孩子）

基本操作

D-Ary-Parent(i)
return $\lfloor (i-2)/d +1 \rfloor$

D-Ary-Child(i,j)
return d(i-1) + j + 1

6-3 Young氏矩阵 $m*n$

1. 性质：每一行都是从左到右排序的，每一列都是从上到下排序的

Build-Young(Y)——$O(mn(m+n)) \leftarrow \sum_{i,j=1}^{m-1,n}(i+j))$

m,n = Y.size  #得到A的维度
InsertSort(Y[m])  #先将最后一行排序
#再从倒数第二行最后一个元素开始逐行从右到左维护最小堆的性质
for i = m-1 downto 1
    for j = n downto 1
        Min-Heapify(Y,i,j)

2.- 删除并返回最小值的算法，时间复杂度为 $O(m+n)$

-
Extract-Min(Y,m,n)

min = Y[1,1]
Y[1,1] = Y[m,n]
Min-Heapify(Y,1,1)

-

Min-Heapify(Y,i,j)

if i < m and Y[i,j] > Y[i+1,j]
    samllest = (i+1,j)
else
    smallest = (i,j)
if j < n and Y[samllest] > Y[i,j+1]
    samllest = (i,j+1)
if (i,j) != smallest
    exchange Y[i,j] with Y[smallest]
    Min-Heapify(Y,samllest)

3.-将一个新元素插入到未满的Y[m,n]中，时间为$O(m+n)$
此处可以按照优先队列的才插入做法，先写一个类似的increase过程。这里我直接利用最小堆的维护来达到同样效果

Young-Insert(Y,key)

(m,n) = Y.size #返回Y矩阵的维度
if Y[m,n] < oo
    error "unempty"
#寻找一个周围有元素的空位置，以放置这个新加入的元素
i = m
j = n
while true
     if Y[i-1,j] < 00 or Y[i,j-1] < 00
        left = i
        right = j
        break
    esle
        if i > 1
            i = i - 1
        else 
            j = j - 1
Y[i,j] = key
#将key交换到开头位置，并进行维护
exchange Y[i,j] with Y[1,1]
Min-Heapify(Y,1,1)

4.- 判断一个数是否在young矩阵中，时间为$O(m+n)$
Is-In(Y,key)

(m,n) = Y.size
i = m
j = 1
while i >= 1 or j >= 1
    if key < Y[i,j]
        i = i - 1
    else if key > Y[i,j]
        j = j + 1
    else
        return true
return false

注意此处初始位置的选取，如果一开始就在矩阵的最末端，则while中的条件判断没法写

代码实现

java