文章目录
  1. 1. 堆排序

堆排序

思想
首先来认识什么是堆,堆是一种数据结构,具有完全二叉树的性质。堆又分大顶堆和小顶堆。在数组arr[0, …n-1]中,对于某个结点i,
parent = (i-1) / 2
lchild = 2i + 1
rchild = 2i + 2
大顶堆:每个结点的值大于或等于其左右孩子结点值。
小顶堆:每个结点的值小于或等于其左右孩子结点值。
在堆排序中采用的是大顶堆排序。最大的结点在根结点。
堆的调整
如何让一个组数据保持大顶堆的性质呢?也就是调整一组数据使其保持和具有大顶堆得性质。
假设某个结点的左右孩子都是最大堆,但是该节点却不是最大堆。则需要在该节点arr[i]、arr[lchild]、和arr[rchild]中选择出一个最大值为arr[max]。如果最arr[i]最大则是最大堆,无需调整。如果不是,则需要交换arr[i]和arr[max],交换后,可能孩子结点不是最大堆,则需要重新建立堆。

def adjustHeap(arr, i, length):
lchild = 2*i + 1
rchild = 2*i + 2
max = i
if i < length/2:
if lchild < length and arr[lchild] > arr[max]:
max = lchild
if rchild < length and arr[rchild] > arr[max]:
max = rchild
if max is not i:
arr[max], arr[i] = arr[i], arr[max]
adjustHeap(arr, max, length)

注意调用此函数的前提条件,i的左右孩子都是最大堆。
建立堆
为了保证堆得建立,反复调整最后得到完整的堆,我们只需要从最下面的非叶子结点开始调整,直到根结点成为最大的堆。
由二叉树的性质有,如果i>1,则其双亲结点是小于等于i/2
由于数组下标从零开始,即n个结点则从n/2 -1,n/2 -2 …0。

def buildHeap(arr, length):
for i in range(0, length/2)[::-1]:
adjustHeap(arr, i, length)

堆排序
为了进行排序,我们只需将排好序的堆中最大堆与未经排序的子序列最后一个交换。length为数组长度,heapSize为堆的大小,arr[0, length-1]为数组,arr[0, heapsize-1]为堆,arr[heapSize, length-1]为排好序的堆。

  • 令heapSize = length,建立完整的堆,bulidHeap(arr, heapSize)
  • i = length-1,交换arr[0]和arr[lenght-1],heapSize–,i–
  • 交换后,左后孩子仍为最大堆,但是结点不满足最大堆,则需要重新调整大小。adjustHeap(arr, 0, heapSize)
  • 重复以上两步骤,直至排好序。
def heapSort(arr):
length = len(arr)
heapSize = length
buildHeap(arr, heapSize)
for i in range(0, length-1)[::-1]:
arr[0], arr[i] = arr[i], arr[0]
adjustHeap(arr, 0, heapSize-1)

完整程序

def adjustHeap(arr, i, length):
lchild = 2*i + 1
rchild = 2*i + 2
max = i
if i < length/2:
if lchild < length and arr[lchild] > arr[max]:
max = lchild
if rchild < length and arr[rchild] > arr[max]:
max = rchild
if max is not i:
arr[max], arr[i] = arr[i], arr[max]
adjustHeap(arr, max, length)

def buildHeap(arr, length):
for i in range(0, length/2)[::-1]:
adjustHeap(arr, i, length)

def heapSort(arr):
length = len(arr)
heapSize = length
buildHeap(arr, heapSize)
for i in range(0, length-1)[::-1]:
arr[0], arr[i] = arr[i], arr[0]
adjustHeap(arr, 0, heapSize-1)
return arr

应用
堆的时间主要消耗在堆的建立和调整上。对于每个非终端结点来说,只需要进行两次比较和互换,构建堆的时间复杂度为O(n),由于完全二叉树的某个结点到根结点的距离为小于等于logi + 1,需要你时间logi,并且需要n-1次,故时间复杂度为O(nlogn)。总体时间复杂度为O(n) + O(nlogn),即O(nlogn).性能要比冒泡,选择、直接插入(时间复杂度O(n^2))要好。
空间复杂度上,只有一个交换暂存单元。交换和比较是跳跃式的,故堆排序不稳定。
不适合待排序列个数较少的情况。
补充
关于调整堆,可以换成非递归形式。

  • 对于某一个结点i,如果有孩子结点,它左孩子结点一定为2i+1,右孩子结点为2i+2,
  • 调整一个非叶子结点arr[i]为最大堆,实质是调整n/2 -1,n/2-2…0为最大堆。
  1. 假设temp = arr[i]。
  2. 比较arr[2i+1]和arr[2i+2]的大小,记录最大一个孩子结点arr[j]。
  3. 比较temp 和arr[j]的大小,如果temp > arr[j]该结点本来就是最大堆不用交换,结束循环。反之,将arr[j]赋给arr[i],同时将j赋给 i,这可能使得arr[j]不是最大堆,则重复步骤2和3,重新调整使其孩子结点满足最大堆。最后arr[i] = temp。
    #非递归实现
    def adjustHeap(arr, i, length):
    temp = arr[i]
    j = 2*i + 1
    while j < length: #沿着较大的左右孩子结点筛选
    if j+1 < length and arr[j] < arr[j+1]:
    j = j + 1 #记录孩子结点中较大的标号
    if temp > arr[j]:
    break
    arr[i] = arr[j]
    i = j
    j = 2*j + 1
    arr[i] = temp

    def heapSort(arr):
    length = len(arr)
    for i in range(0, length/2)[::-1]:
    adjustHeap(arr, i, length)#建立堆
    for j in range(0,length)[::-1]:
    arr[i], arr[0] = arr[0], arr[i]
    adjustHeap(arr, 0, j-1)
    return arr
文章目录
  1. 1. 堆排序