织梦网站做图床,wordpress采集模块,自建网站和租用空间网站,西安长安网站建设制作文章出处#xff1a;极客时间《数据结构和算法之美》-作者#xff1a;王争。该系列文章是本人的学习笔记。 堆比较适合动态数据的场景。
1 应用一#xff1a;优先级队列
一个优先级队列就是一个堆。
1.1 合并小文件
假设我们有100个小文件。每个文件中的字符串按照从小到…文章出处极客时间《数据结构和算法之美》-作者王争。该系列文章是本人的学习笔记。 堆比较适合动态数据的场景。
1 应用一优先级队列
一个优先级队列就是一个堆。
1.1 合并小文件
假设我们有100个小文件。每个文件中的字符串按照从小到大排序好了。现在需要把这100个小文件合并为1个大文件并且还要按照字符串从小到大排序。 这和归并排序算法的合并操作有点类似。我们从每个文件读取一条数据形成一个长度为100的数组。然后排序数组将最小的文本写入最终合并的文件中并且从最小文本所在的文件读取一条数据再次形成长度100的数组。这里有个排序操作按照快排的时间复杂度O(nlogn)。我们可以对这一步做改进。 使用最小堆来存放这100条数据。在堆顶的元素就是最小元素。 1 我们从100个小文件分别读一条数据插入最小堆。 2 删除堆顶元素写入最终合并的文件中。 3 从从最小文本所在的文件读取一条数据插入最小堆。重复步骤2。 插入数据、删除数据的时间复杂度都是O(logn)比原来的排序优化了。
1.2 高性能定时器
对于定时器一般的做法是每个一秒一定时间检查任务队列的中的任务是不是到了执行时间。到了就执行。 优化的做法是按照定时器的开始执行时间建一个最小堆。在堆顶任务开始执行之前都不需要检查其他任务。
2 应用二求Top k
求top k可以分为两种场景。一种是静态场景数据不会发生变化另一类是动态场景数据在实时变化。 静态场景下的解决方法是排序数组然后返回前k个元素。 动态场景下如果每次都排序时间复杂度高。我们建一个容量为k的最小堆。当遇到比堆顶元素大的数据则删除堆顶元素插入新数据。这样在某个时刻堆中的所有元素就是top k 元素。
3 应用三求中位数
中位数如果数组长度n是奇数下标等于n2\dfrac{n}{2}2n的元素是中位数。如果n是偶数则下标等于n2−1\dfrac{n}{2}-12n−1和n2\dfrac{n}{2}2n两个元素都是中位数我们可以取下标n2\dfrac{n}{2}2n的元素。 我们可以利用两个堆一个最大堆一个最小堆。最大堆中所有的元素都小于最小堆。我们将数组中的前n2\dfrac{n}{2}2n个元素放入最大堆后面的元素放入最小堆。这样最大堆的堆顶就是中位数。
