|
解决思路： ?
????????????????取列表前k个元素，建立一个小根堆，堆顶就是这k个里面最小的数
????????????????依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；
????????????????如果大于堆顶，这表示现在堆顶的元素肯定不是前k大的，直接扔掉，将堆顶更换为新元素，并重新建堆
????????????????遍历整个列表结束后，这个小根堆里的数就是前n大的数，此时倒序弹出堆顶即可
1、建小根堆（只需把前面代码中的两个>号换成<号即可）
# 建小根堆
def sift(li, low, high): # 将二叉树或部分二叉树变成一个堆的过程，所以在正式排序时是从下往上遍历的
'''
low 是堆顶的位置
high 是堆底的位置，防止越界
'''
i = low # i最开始是根节点
j = 2 * i + 1 # j是左子节点
tmp = li[low] # 把堆顶存起来
while j <= high : # 只要j位置有节点，就可以一直循环
if j + 1 <= high and li[j] > li[j+1]: # 左子节点和右子节点先比较，如果右更大就把j指向右子节点
j += 1
if li[j] < tmp: # 如果j位置更大，那么要把j上的放到i上
li[i] = li[j]
i = j # 接着往下看一层，新的i变到j原来j的位置上，即把i和j互换
j = 2 * i + 1 # 新的j是新的i的子节点
else: # tmp更大，tmp就放在这个i的位置
li[i] = tmp
break
else: # 如果遍历到了堆底，则直接把tmp放在这个i位置上就好了
li[i] = tmp
2、topk：?
def topk(li, k):
heap = li[0:k]
for i in range((k-2)//2, -1, -1):
sift(heap, i, k-1)
# 这个循环结束后第一个堆就建好了，接着依次遍历后面的元素，和堆顶比较
for i in range(k, len(li)-1):
if li[i] > heap[0]: # 如果新来的数比堆顶（堆中最小的数）大，那么把现在的堆顶扔掉
heap[0] = li[i] # 扔掉堆顶，加入新数
sift(heap, 0, k-1) # 重新建堆，即重新排列顺序
# 这个循环结束之后前k大数的堆就建好了，接着输出堆中排序的数即可
for i in range(k-1, -1, -1):
heap[0], heap[i] = heap[i], heap[0]
sift(heap, 0, i-1)
return heap
|