python 通过数组来进行堆排序

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。 堆通常是一个可以被看做一棵树的数组对象。 堆总是满足下列性质：

1. 堆中某个节点的值总是不大于（最大堆）或不小于（最小堆）其父节点的值；
2. 堆总是一棵完全二叉树。

上图为一个典型的最大堆。每一个子节点都小于或者等于它的父节点，由于堆是完全二叉树，所以处理堆最简单的方式就是数组。python里面可以用list队列来处理。

#数组处理完全最大堆
def add(list):
    for i in range(len(list)):
        if i ==0:
            continue

        while i>0:
            j = (i-1)//2
            k = (i-2)//2
            if i%2!=0 and list[i]>list[j]:
                n = list[i]
                list[i] =  list[j]
                list[j] = n
                i = j
                continue
            if i%2==0 and list[i]>list[k]:
                n = list[i]
                list[i] =  list[k]
                list[k] = n
                i = k
                continue
            break
    return list

def sort(list,n = 0):
    list2 = []
    n = len(list)-n
    while len(list)>n:
        list2.append(list[0])
        if len(list)==1:
            break
        list[0] = list.pop()
        i = 0
        while (2*i+2)<=len(list):
            #防止最后一个树节点为单个
            try:
                if list[2*i+1]>list[2*i+2]:
                    m = 2 * i + 1
                else:
                    m = 2 * i + 2
            except IndexError:
                m = 2 * i + 1

            if list[i]<list[m]:
                k = list[m]
                list[m] = list[i]
                list[i] = k
                i = m
            else:
                break
    return list2

if __name__ == '__main__':
    '主函数'

    list = [10,3,6,12,7,8,5,18,2,6,9,12,32,17,25,20]
    print('原始列表',list)
    list = add(list)
    print('初始最大堆列表',list)
    # list_sort = sort(list)
    # print('堆排序后的列表',list_sort)
    list_sort = sort(list,5)
    print('利用堆排序获取最大的5个数',list_sort)

原始列表 [10, 3, 6, 12, 7, 8, 5, 18]
初始最大堆列表 [18, 12, 8, 10, 7, 6, 5, 3]
堆排序后的列表 [18, 12, 10, 8, 7, 6, 5, 3]
利用堆排序获取最大的5个数 [32, 25, 20, 18, 17]

堆排序最简单的一个应用，获取数列中最大/最小的 k个数，不需要对整个数列进行排序即可找出，更高效 时间复杂度为 o(klogn)

堆排序