堆排序

数据结构堆

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)