量化投资学习笔记43——基本数据结构算法总结2

发表于 | 分类于
| 字数统计: 703 | 阅读时长 ≈ 2

拉钩教育的《300分钟搞定数据结构与算法》课程笔记。
第二讲 高级数据结构
优先队列:能保证每次取出的元素都是队列中优先级别最高的。优先级别可以是自定义的。
应用场景，从一堆杂乱的数据中按照一定的顺序逐步地筛选出部分乃至全部数据。
实现:优先队列本质是一个二叉堆结构，是一个用数组来实现的完全二叉树。
优先队列的三个重要性质:①数组里第一个元素拥有最大的优先级;②给定一个下标，对于元素array[i]而言，其父节点的下标为:(i-1)/2，其左孩子对应的下标为2i+1，右孩子对应的下标为2i+2;③数组里每个元素的优先级别都要高于其两个子孩子的优先级别。
两个基本操作:①向上筛选，新元素加入时，先放在二叉堆底部，再根据优先级不断向上筛选，即与父节点交换，直至无法交换。时间复杂度logk;②当删除元素时，需要更新堆，将堆底的元素放至堆顶，再根据优先级逐步筛选。复杂度一样。
初始化一个优先队列，时间复杂度为O(n)
例子:任意一个数组，找出前k大的数。
python有现成的库的，就直接用了。

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
# coding:utf-8
# 优先队列
from queue import PriorityQueue

def kthelem(data, k):
    pq = PriorityQueue()
    for i in data:
        pq.put(i)
    for i in range(k):
        result = pq.get()
    return result

if __name__ == "__main__":
    # 测试优先队列的使用
    pq = PriorityQueue()
    for i in range(3, 0, -1):
        pq.put(i)
    while not pq.empty():
        print(pq.get())

    # 找出序列中第k大的元素
    data = [8, 9, 3, 6, 7, 5, 54, 33, 65, 90]
    k = 5
    result = kthelem(data, k)
    print(data)
    print("第{}大的数为:{}".format(k, result))

另一个例子，力扣347题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# 力扣347题，找出给定序列中出现频率最高的前k个元素
def kthfreq(nums, k):
    # 用哈希表存储数据出现的频率
    freq = dict()
    for i in nums:
        freq[i] = 0
    for i in nums:
        freq[i] += 1
    # 用优先队列找出频率前k的数据
    pq = PriorityQueue()
    for key in freq.keys():
        pq.put([-freq[key], key])
    results = [0]*k
    for i in range(k):
        results[i] = pq.get()[1]
    return results

其它高级数据结构略了。看来还是要系统看书。排序也pass了。这个课程好像是针对面试的，看书吧。

我发文章的三个地方，欢迎大家在朋友圈等地方分享，欢迎点“在看”。
我的个人博客地址：https://zwdnet.github.io
我的知乎文章地址： https://www.zhihu.com/people/zhao-you-min/posts
我的微信个人订阅号：赵瑜敏的口腔医学学习园地

欢迎打赏！感谢支持！