堆排序

堆排序的时间复杂度是O(nlg(n))，并且具有空间原址性

二叉堆heap是一种数据结构，可用来实现优先队列

给定一个节点的下标i(下标从0开始)，则其父节点、坐孩子、右孩子坐标：
parent(i) = (i+1)//2 - 1 = ((i + 1) >> 1) - 1
left(i) = 2*i + 1 = (i << 1) + 1
right(i) = 2*i + 2 = (i + 1) << 1

最小堆定义： 任意 i 满足 A[parent(i)] <= A[i]
最大堆定义： 任意 i 满足 A[parent(i)] >= A[i]

在堆排序中，使用最大堆
在优先队列算法中，使用最小堆

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

class Heap():
    def __init__(self, seq, heapSize, length):
        """
        seq: 存放待排序的序列
        heapSize: 堆的大小
        lenght: 整个序列大小
        """
        self.seq = seq
        self.heapSize = heapSize
        self.length = length


def heapSort(seq):
    """
    堆排序算法
    """
    heap = Heap(seq, len(seq), len(seq))
    __buildMaxHeap(heap)
    s = heap.seq
    for i in range(heap.length - 1, 0, -1):
        s[0], s[i] = s[i], s[0]
        heap.heapSize -= 1
        __maxHeapify(heap, 0)


def __maxHeapify(heap, i):
    """
    前提是 i 的两棵子树 left(i) 和 right(i) 的二叉树都是最大堆了
    现在加入 i 节点后，要保持这个二叉树为最大堆的性质
    heap: Heap 数据结构
    """
    seq = heap.seq
    slen = heap.heapSize

    while True:
        left = (i << 1) + 1
        right = (i + 1) << 1
        if left < slen and seq[left] > seq[i]:
            largest = left
        else:
            largest = i
        if right < slen and seq[right] > seq[largest]:
            largest = right
        if largest != i:
            seq[largest], seq[i] = seq[i], seq[largest]
            i = largest
        else:
            break


def __buildMaxHeap(heap):
    """
    由完全二叉树的性质可知：对于 n//2..n-1 为下标的元素，都是叶子节点，
    那么可从下标 (n+1)//2 - 1 开始往前到 0 的元素调用 maxHeapify
    heap: Heap数据结构
    """
    slen = heap.heapSize
    for i in range(((slen + 1) >> 1) - 1, -1, -1):
        __maxHeapify(heap, i)


if __name__ == '__main__':
    seq = [9, 7, 8, 10, 16, 3, 14, 2, 1, 4]
    heapSort(seq)
    print(seq)