堆排序学习总结

在学习《算法》一书中了解到:
优先队列是一种抽象的数据类型,优先队列最重要的操作就是删除最大元素和插入元素。
实现优先队列可以用数组,链表,最好的方式还是用堆。

我们可以把任意优先队列变成一种排序方法。将所有元素插入一个查找最小化元素的优先队列,然后再重复调用删除最小元素的操作将它们按顺序删去。用无序数组实现的优先队列这么做相当于进行一次选择排序。用基于堆得优先队列这样做等同于堆排序!

要了解堆首先得了解一下二叉树,在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。

二叉树又分为满二叉树(full binary tree) 和 完全二叉树(complete binary tree)

满二叉树:一棵深度为 k,且有 2k - 1 个节点称之为满二叉树

Sample Image Added via Markdown

完全二叉树则满足序号和满二叉树的完全对应。

Sample Image Added via Markdown

如下图,是一个堆和数组的相互关系
Sample Image Added via Markdown

对于给定的某个结点的下标 i,可以很容易的计算出这个结点的父结点、孩子结点的下标:

  • Parent(i) = floor(i/2),i 的父节点下标
  • Left(i) = 2i,i 的左子节点下标
  • Right(i) = 2i + 1,i 的右子节点下标

堆排序原理

堆排序就是把最大堆堆顶的最大数取出,将剩余的堆继续调整为最大堆,再次将堆顶的最大数取出,这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作:

最大堆调整(Max-Heapify):将堆的末端子节点作调整,使得子节点永远小于父节点(左子树不一定大于右子树)
创建最大堆(Build-Max-Heap):将堆所有数据重新排序,使其成为最大堆
堆排序(Heap-Sort):移除位在第一个数据的根节点,并做最大堆调整的递归运算

继续进行下面的讨论前,需要注意的一个问题是:数组都是 Zero-Based,这就意味着我们的堆数据结构模型要发生改变

相应的,几个计算公式也要作出相应调整:

Parent(i) = floor((i-1)/2),i 的父节点下标
Left(i) = 2i + 1,i 的左子节点下标
Right(i) = 2(i + 1),i 的右子节点下标

最大堆调整(MAX‐HEAPIFY)的作用是保持最大堆的性质,是创建最大堆的核心子程序,作用过程如图所示:

Sample Image Added via Markdown

源码如下:

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
def heapsort(arr):
def max_heapify(arr, index, heap_size):
"""
# 最大堆调整(MAX‐HEAPIFY)的作用是保持最大堆的性质。 将堆的末端子节点作调整,使得子节点永远小于父节点
# 意思就是要让index这元素去到它该去的位置
《算法》P200
由上至下的对有序化(下沉)
如果我们把堆想象成一个严密的黑色会组织,每个子节点都表示一个下属(父节点则表示它的直接上级),name这些操作就可以得到很有趣的解释。
max_hepify这个方法就相当于一个领导,如果占着老大的位置,但如果自己下属有比自己厉害的就要退位让贤。自己去到该去的层次
注意的是:这方法是有惰性的。调用一次该方法仍然不行。如果该index的左右子树都小于自己的话,它就不会递归了。
这个方法只是让index尽量下沉下去。如果是堆有序的话,那么执行该方法后index位置就是该位置最大的值
"""
while True:
imax = index
ileft = 2 * index + 1
iright = 2 * index + 2
if ileft < heap_size and arr[index] < arr[ileft]:
imax = ileft
if iright < heap_size and arr[imax] < arr[iright]:
imax = iright
if imax != index:
arr[imax], arr[index] = arr[index], arr[imax]
index = imax
else:
break
def build_maxheap(arr):
"""
# 将堆所有数据重新排序,使其成为最大堆
创建最大堆(Build-Max-Heap)的作用是将一个数组改造成一个最大堆,接受数组和堆大小两个参数,Build-Max-Heap 将自下而上的调用 Max-Heapify 来改造数组,建立最大堆。
因为 Max-Heapify 能够保证下标 i 的结点之后结点都满足最大堆的性质,所以自下而上的调用 Max-Heapify 能够在改造过程中保持这一性质。
如果最大堆的数量元素是 n,那么 Build-Max-Heap 从 Parent(n) 开始,往上依次调用 Max-Heapify。
"""
iparent = len(arr) // 2 - 1 # 最后一个节点的父节点
for i in range(iparent, -1, -1):
max_heapify(arr, i, len(arr))
def sort(arr):
build_maxheap(arr) # build后左子树 还是可能大于 右子树的.所以这并不是一个有序数组
print(arr)
for i in range(len(arr)-1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
max_heapify(arr, 0, i) # 这里这个i 相当于比当前的length - 1;第i个元素为当前最大的元素,就被固定死了。不再访问它
return arr
return sort(arr)
if __name__ == '__main__':
print(heapsort([5,4,7,3,8,2,11,15,17,16,13,10,9,12,1]))