程序员

堆排序

数据结构堆

  1. 是一颗完全二叉树。完全二叉树:设二叉树的深度为h,除了第h层以外,前面的每一层的节点数都达到最大,并且第h层的叶子都集中在最左边。
  2. 所有非终端(有叶子)节点的值均不小于(或不大于)其左、右孩子的值。前者叫大顶堆,后者叫小顶堆。

堆排序思想

利用堆数据结构的堆顶肯定是最大值(或最小值),则可以取出堆顶元素,然后对剩下的元素重新构造大顶堆(或小顶堆)后,继续取出堆顶元素,知道所有元素被取完。则取出的元素会按照顺序排列。

图解堆排序过程

alist = [16,7,3,20,17,8]为例

  1. 首先根据列表构造一个完全二叉树

    来自百度百科.png
  2. 构造初始堆,从叶子节点往上层调整

    来自百度百科.png
  3. 发现20和16交换位置后,不满足堆的性质,所以重新调整

    来自百度百科.png
  4. 这样就得到了大顶堆,让堆顶元素和最后一个叶子节点交换位置

    来自百度百科.png
  5. 排除元素20后,重新构造堆结构。直到所有元素排除完。

    来自百度百科.png

    来自百度百科.png

python实现

#!/usr/bin/python
# encoding: utf-8

# 从start到end的位置构造一个大顶堆
def siftAdjust(alist, start, end):
    # start位置作为堆顶
    root = start
    # 左叶子
    while True:
        # child初始为左边的子节点
        child = root * 2 + 1

        if child >= end:
            break

        # 比较左右叶子节点的大小,找出最大的那一个
        if child + 1 <= len(alist) - 1 and alist[child] < alist[child + 1]:
            child = child + 1

        # 把最大的子节点和根节点交换位置
        if alist[root] < alist[child]:
            alist[root], alist[child] = alist[child], alist[root]
            # 调整过后,需要更新根节点,以防交换位置后,子树不再是堆结构
            root = child
        # 若没有调整,则直接退出
        else:
            break


def heapSort(alist):
    # 从最后一个有子节点的位置开始调整大顶堆
    first = (len(alist) - 2) // 2
    # 初始化一个大顶堆
    for i in range(first, -1, -1):
        siftAdjust(alist, i, len(alist) - 1)
    # 第i趟排序
    for i in range(len(alist)-1,0,-1):
        # 把第一个位置堆顶与最后一个位置交换
        alist[0],alist[i] = alist[i],alist[0]
        # 调整堆结构
        siftAdjust(alist,0,i-1);


if __name__ == '__main__':
    a = [4,10,7,9,5,3,1,2,8,6]
    heapSort(a)
    print(a)