[关闭]
@zqbinggong 2018-03-08T05:10:56.000000Z 字数 3248 阅读 549

chap6 堆排序

堆排序 算法导论

内容


  1. (二叉堆)是一个数组,可以被看成是一个近似的完全二叉树。
  2. 基本操作:

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

    Left(i)
    return 2i

    Right(i)
    return 2i + 1


最大堆和堆排序

  1. 除了根节点外的所有节点都要满足: ,类似的可以定义最小堆。前者用于排序,后者通常用于构建优先队列
  2. 堆排序在时间复杂度与归并排序相当,但他是原址排序的,因而优于前者
  3. 最大堆的基本过程

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

伪代码


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[+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)

优先队列

概念

优先队列是一种用来维护一组元素构成的集合的数据结构。集合中,每个元素都有一个相关的值,成为关键字(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. 问题:设计算法,时间复杂度为,能将k个有序链表合并成一个有序链表,这里n是总的元素的个数(提示:用最小堆)
  2. 基本思路:

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

6-1 用插入的方式建堆

Build-Max-Heap(A)

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

算法分析:会调用n-1次插入操作,因此时间上限时;其次,考虑原数组是递增数组的最坏情况下,此时每个插入操作运行时间是,计算可得,此时下界是,因而此时复杂度为


6-2 d叉堆(内部结点有d个孩子)

基本操作

D-Ary-Parent(i)
return

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


6-3 Young氏矩阵

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

Build-Young(Y)——

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.- 删除并返回最小值的算法,时间复杂度为

-
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]中,时间为
此处可以按照优先队列的才插入做法,先写一个类似的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矩阵中,时间为
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

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注