从长度为M的无序数组中找出N个最大的数

1、将数组前N个数调整成最小堆

2、堆顶元素值依次与第N个元素以后的每个元素进行比较

3、若堆顶元素值小，则将堆顶元素重新赋值为新元素的值，并且将前N个数重新调整为最小堆；否则判断下一个元素

4、直到遍历完原数组的最后一个元素后，则最小堆中的元素即为待求的数组中的N个最大的数

复杂度为O(M*log(N))

python代码：

# -*- coding: utf-8 -*-
'''
堆排序
'''

# 从上往下调整堆
def filter_down(array, beg, end):
    current, child = beg, 2*beg + 1
    temp = array[current]

    while child <= end:
        if child < end and array[child] > array[child + 1]:
            child += 1

        if array[child] < temp:
            array[current] = array[child]
            current, child = child, 2*child + 1
        else:
            break

    array[current] = temp

def find_N_max(array, N):
    res = array[:N]
    for i in range(int((N - 2)/2), -1, -1):
        filter_down(res, i, N - 1)

    for j in range(N, len(array) - 1):
        if array[j] > res[0]:
            res[0] = array[j]
            filter_down(res, 0, N - 1)

    return res