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

时间:2022-05-16 10:49:24

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