# 剑指Offer40.最小的k个数
# 解题思路
使用堆, 堆这种数据结构有一种典型的应用,优先队列。
普通队列:遵循先进先出、后进后出的原则 优先队列:出队的顺序和入队的顺序无关,和优先级相关
问题抽象: 在N个元素中选出前M个元素
堆这种数据结构可以是一种树形结构,有两个特点:
- 堆中某个节点的值总是不大于其父亲节点的值
- 堆总是一颗完全二叉树 除了最后一层节点外,其他层的节点必须填满了。最后一层必须集中在最左侧。(最大堆)
可以用数组存储二叉堆
我们可以使用一个大根堆实施维护数组的前k小的值,首先讲前k个数插入到大根堆中,随后从k+1个数开始遍历,如果当前遍历到的数比堆顶的数要小,就把堆顶数弹出再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。