#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# 堆排序
"""
    Topic: sample
    Desc : 堆排序
        堆排序的时间复杂度是O(nlg(n))，并且具有空间原址性
        二叉堆heap是一种数据结构，可用来实现优先队列
        给定一个节点的下标i(下标从0开始)，则其父节点、坐孩子、右孩子坐标：
        parent(i) = floor((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]

        在堆排序中，我们使用最大堆
        在优先队列算法中，使用最小堆
"""
__author__ = 'Xiong Neng'


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为下标的元素，都是叶子节点，
    那么可从下标floor((i+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__':
    iSeq = [9, 7, 8, 10, 16, 3, 14, 2, 1, 4]
    heapSort(iSeq)
    print(iSeq)