题目链接
https://leetcode-cn.com/problems/smallest-k-lcci/
其他练习
https://leetcode-cn.com/problems/last-stone-weight/
参考链接
https://blog.csdn.net/varyall/article/details/81099681
https://blog.csdn.net/genios/article/details/8157031
https://blog.csdn.net/jamfiy/article/details/88185512
堆、栈
堆和栈的区别：
一、堆栈空间分配区别：
1、栈（操作系统）：由操作系统自动分配释放 ，存放函数的参数值，局部变量的值等。其操作方式类似于数据结构中的栈；
2、堆（操作系统）： 一般由程序员分配释放， 若程序员不释放，程序结束时可能由OS回收，分配方式倒是类似于链表。
二、堆栈缓存方式区别：
1、栈使用的是一级缓存， 他们通常都是被调用时处于存储空间中，调用完毕立即释放；
2、堆是存放在二级缓存中，生命周期由虚拟机的垃圾回收算法来决定（并不是一旦成为孤儿对象就能被回收）。所以调用这些对象的速度要相对来得低一些。
三、堆栈数据结构区别：
堆（数据结构）：堆可以被看成是一棵树，如：堆排序；
栈（数据结构）：一种先进后出的数据结构。
一种著名的数据结构是堆（heap），它是一种优先队列。优先队列让你能够以任意顺序添加对象，并随时（可能是在两次添加对象之间）找出（并删除）最小的元素。相比于列表方法min，这样做的效率要高得多。
实际上，Python没有独立的堆类型，而只有一个包含一些堆操作函数的模块。这个模块名为heapq（其中的q表示队列），它包含6个函数，其中前4个与堆操作直接相关。必须使用列表来表示堆对象本身。
python heapq模块
堆特征（heap property）:
元素的排列顺序并不像看起来那么随意。它们虽然不是严格排序的，但必须保证一点：位置i处的元素总是大于位置i // 2处的元素（反过来说就是小于位置2 * i和2 * i + 1处的元素）。这是底层堆算法的基础，称为堆特征（heap property）。
创建 堆：
时间复杂度
https://www.cnblogs.com/zuotongbin/p/10702001.html
1.heappush 将list元素压入
from heapq import *
from random import shuffle
data = list(range(10))
shuffle(data)
heap = []
for n in data:
heappush(heap, n)
heap
#[0, 1, 3, 6, 2, 8, 4, 7, 9, 5]
2.对list元素使用 heapify函数
heap = [5, 8, 0, 3, 6, 7, 9, 1, 4, 2]
heapify(heap)
解题代码
def smallestK(self, arr: List[int], k: int) -> List[int]:
out=[-i for i in arr[:k]]
if not out:
return out
import heapq
heapq.heapify(out)
for i in arr[k:]:
if (-i)>out[0]:
heapq.heapreplace(out,-i)
else:
continue
return [-i for i in out]
求maximumK 不使用负号即可
