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