堆排序找n个最大数
时间: 2023-07-26 08:09:55 浏览: 49
堆排序可以用来找n个最大数,具体实现步骤如下:
1. 构建一个大小为n的小根堆(也就是堆顶元素最小),把待排序数组的前n个元素依次插入堆中,堆中的元素个数一直为n。
2. 从第n+1个元素开始,依次与堆顶元素进行比较。如果当前元素大于堆顶元素,则用当前元素替换堆顶元素,并对堆进行一次向下调整(保证堆的性质)。否则就不做处理,继续比较下一个元素。
3. 最终堆中的n个元素就是原数组中的n个最大数,且它们已经按照从大到小的顺序排好了。
下面是一个示例代码(假设待排序数组为arr,n为要找的最大数的个数):
```python
def heap_sort_topn(arr, n):
def sift_down(lst, start, end):
root = start
while True:
child = root * 2 + 1
if child > end:
break
if child + 1 <= end and lst[child] > lst[child + 1]:
child += 1
if lst[root] > lst[child]:
lst[root], lst[child] = lst[child], lst[root]
root = child
else:
break
heap = arr[:n]
for i in range(n // 2 - 1, -1, -1):
sift_down(heap, i, n - 1)
for i in range(n, len(arr)):
if arr[i] > heap[0]:
heap[0] = arr[i]
sift_down(heap, 0, n - 1)
return sorted(heap, reverse=True)
```
这个算法的时间复杂度是O(nlogn),空间复杂度是O(n)。