算法导论打卡3，主要内容：堆排序

第六章 堆排序

堆

  • 二叉堆是一个数组，它可以被看成一个近似的完全二叉树。树上的每一个结点对应数组中的一个元素。除了最底层外，该树是完全充满的，而且是从左向右填充。
  • 表示堆的数组A包括两个属性：A.length(通常)给出数组元素的个数，A.heap-size表示有多少个堆元素存储在该数组中。也就是说虽然A[1..A.length]可能都存有数据，但只有A[1..A.heap-size]中存放的是堆的有效元素，这里0≤A.heap-size≤A.length。树的根节点是A[1]，这样给定一个结点的下标i，我们很容易计算得到它的父结点，左孩子和右孩子的下标：
1
2
3
4
5
6
def parent(i):
	return i//2
def left(i):
	return 2*i
def right(i):
	return 2*i+1
  • Ko9IoQ.md.png
  • 二叉堆可以分为两种形式：最大堆和最小堆。在这两种堆中，结点的值都要满足堆的性质。区别在于：
    • 最大堆中，最大堆性质是指除了根以外的所有结点i都要满足：A[PARENT(i)]≥A[i]，即在任一子树中，该子树所包含的所有结点的值都不大于该子树根节点的值。
    • 最小堆中，最小堆性质是指除了根以外的所有结点i都要满足：A[PARENT(i)]≤A[i]
  • 在堆排序算法中，我们使用最大堆。最小堆通常用于构造优先队列。
  • 如果把堆看成一棵树，我们定义一个堆中的结点的高度是该节点到叶结点最长简单路径上边的数目。既然一个包含n个元素的堆可以看作是一颗完全二叉树，那么该堆的高度是O(lgn)
  • 堆结构上的一些基本操作的运行时间至多与树的高度成正比，即时间复杂度为O(lgn).

维护堆的性质

  • 通过让A[i]的值在最大堆中“逐级下降”，从而使得以下标i为根结点的子树重新遵循最大堆的性质：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
def max_heapify(A,i):
    l,r=2*i,2*i+1
    heap_size=len(A)-1
    if(l<=heap_size and A[l]>A[i]):
        largest=l
    else:
        largest=i
    if(r<=heap_size and A[r]>A[largest]):
        largest=r
    if(largest!=i):
        temp=A[i]
        A[i]=A[largest]
        A[largest]=temp
        max_heapify(A,largest)
  • 对于一个高为h的结点来说，max_heapify的时间复杂度是O(h)。

建堆

1
2
3
4
def build_max_heap(A):
	#A[0]存储堆元数个数
    for i in range(1,A[0]//2+1)[::-1]:
        max_heapify(A,i)
  • 完整代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
def max_heapify(A,i):
    l,r=2*i,2*i+1
    heap_size=A[0]
    if(l<=heap_size and A[l]>A[i]):
        largest=l
    else:
        largest=i
    if(r<=heap_size and A[r]>A[largest]):
        largest=r
    if(largest!=i):
        temp=A[i]
        A[i]=A[largest]
        A[largest]=temp
        max_heapify(A,largest)

def build_max_heap(A):
	#A[0]存储堆元数个数
    for i in range(1,A[0]//2+1)[::-1]:
        max_heapify(A,i)

if __name__ == "__main__":
	#数组的第一个位置存储堆元素个数，并用于占位
    A=[9,50, 16, 30, 10, 60,  90,  2, 80, 70]
    build_max_heap(A)
    for i in range(1,A[0]+1):
        print(A[i])

堆排序算法

  • 因为数组的最大元素总是在根结点A[1]中，通过把它与A[n]进行互换，我们可以把该元素放到正确的位置上(如从小到大排列)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def max_heapify(A,i):
    l,r=2*i,2*i+1
    heap_size=A[0]
    if(l<=heap_size and A[l]>A[i]):
        largest=l
    else:
        largest=i
    if(r<=heap_size and A[r]>A[largest]):
        largest=r
    if(largest!=i):
        temp=A[i]
        A[i]=A[largest]
        A[largest]=temp
        max_heapify(A,largest)

def build_max_heap(A):
	#A[0]存储堆元数个数
    for i in range(1,A[0]//2+1)[::-1]:
        max_heapify(A,i)

def heapsort(A):
	build_max_heap(A)
	n=A[0]
	for i in range(2,n+1)[::-1]:
		temp=A[1]
		A[1]=A[i]
		A[i]=temp
		A[0]-=1
		max_heapify(A,1)
	A[0]=n

if __name__=="__main__":
	#数组的第一个位置存储堆元素个数，并用于占位
    A=[9,50, 16, 30, 10, 60,  90,  2, 80, 70]
    heapsort(A)
    for i in range(1,A[0]+1):
        print(A[i])
  • heapsort的时间复杂度是O(nlgn),因为每次调用build_max_heap的时间复杂度是O(n)，而n-1次调用max_heapify，每次的时间是O(lgn)。

优先队列

  • 优先队列是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字。
  • 一个最大优先队列支持以下操作：
    • insert(S,x)：把元素x插入集合S中。
    • maximum(S)：返回S中具有最大关键字的元素。
    • extract-max(S)：去掉并返回S中具有最大关键字的元素。
    • increase-key(S,x,k)：将元素x的关键字值增加到k，这里假设k的值不小于x的原关键字值。
  • 最小优先队列同理
  • 实现：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def heap_maximum(A):
    return A[1]

def heap_extract_max(A):
    heap_size=len(A)-1
    if(heap_size<1):
        raise IndexError("heap underflow")
    Max=A[1]
    A[1]=A[heap_size]
    heap_size-=1
    max_heapify(A,1)
    return Max

def heap_increase_key(A,i,key):
    if(key<A[i]):
        raise Exception,"new key is small than current key"
    A[i]=key
    while(i>1 and A[parent[i]]<A[i]):
        temp=A[i]
        A[i]=A[parent[i]]
        A[parent[i]]=temp
        i=parent[i]

def max_heap_insert(A,key):
    heap_size+=1
    A[heap_size]=float('-inf')
    heap_increase_key(A,heap_size,key)