Py008-01-10堆排序之topk问题

topk问题

  • 现在有n个数，设计算法得到前k大的数。 (k<n)
  • 解决思路：
1
2
3
4
5
6
- 1.排序后切片 O(nlogn) + k

- 2.排序lowB三人组 O(kn) 
    如果是冒泡只需要k趟就可以

- 3.堆排序思路  O(nlogk)

堆排序解决思路

  • 取列表前k个元素建立一个小根堆。堆顶就是目前第k大的数。
  • 依次向后遍历原列表，对于列表中的元素，如果小于堆顶，则忽略该元素；如果大于堆顶，则将堆顶更换为该元素，并且对堆进行一次调整；
  • 遍历列表所有元素后，倒序弹出堆顶

如假设一个长度为10的列表,取最大的前5个数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
[6,8,1,9,3,0,7,2,4,5]
思路
step001 
从列表里取出前5个数[6,8,1,9,3]
step002 将这5个数变成一个小根堆
      1
  3       6
9   8
step003 循环剩余列表[0,7,2,4,5]依次跟堆顶比较

0 < 1 不换 [7,2,4,5]

7 > 1 换 [2,4,5]
      7
  3       6
9   8
此时向上调整
      3
  7       6
9   8
2 < 3 不换 [4,5]
4 > 3 换 [5]
      4
  7       6
9   8
无需调整继续循环
5 > 4 换 []
      5
  7       6
9   8
  • 此时时间复杂度是O(nlogk)

topk实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#!/usr/bin/env python
#-*- encoding:utf-8 -*-

# 原地排序，所以 大根堆 堆顶下来的元素会放到列表的末尾
# high则标记 堆的最后一个元素
def sift(li,low,high):
    '''

    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素的位置
    :return:
    '''

    i = low # i最开始指向根节点
    j = 2 * i + 1 # j就是i的左孩子
    tmp = li[low] # 把堆顶存起来
    while j <= high: # 只要j位置有数
        if j + 1 <= high and li[j+1] < li[j]: # 如果有右孩子而且 右孩子比左孩子小
            j = j + 1 # 指向右孩子

        if li[j] < tmp: # 要么是左孩子  要么是右孩子
            li[i] = li[j]
            i = j    # 往下看一层
            j = 2 * i + 1

        else: # tmp最大，把tmp放到i的位置上
            li[i] = tmp # 把tmp放到某一级领导位置上
            break
    else:
        li[i] = tmp # 把tmp放到叶子节点上


#
def topk(li,k):
    heap = li[0:k];
    for i in range((k-2)//2,-1,-1):
        sift(heap,i,k-1)
    # 1。建堆
    # 循环 k到 len(li)-1
    for i in range(k,len(li)-1):
        if li[i] > heap[0]:
            heap[0] = li[i]
            sift(heap,0,k-1)
    # 2。遍历
    for i in range(k-1,-1,-1):
        heap[0],heap[i] = heap[i],heap[0]
        sift(heap,0,i-1)

    # 3。出数
    return heap

import random
li = list(range(1000))
random.shuffle(li)

print(topk(li,10))