内容简介：不知道为啥，突然想水一篇很水的算法文章。今天整理 MySQL 的笔记，看到了这样一句话：MySQL 在执行
不知道为啥，突然想水一篇很水的算法文章。
今天整理 MySQL 的笔记，看到了这样一句话：
MySQL 在执行 ORDER BY x LIMIT n
这类语句，且 LIMIT
的数量有限时（比如只需要 3 条数据），MySQL 会尽量通过堆来构建优先队列，减少 排序 所需的时间。
这是堆的一个经典应用：从海量数据中找出最大（小）的 n 个数。
之前只用堆写过堆排，没有用堆处理过在线算法，所以就写了写。
用一句话概括这个算法：要找最小的数，就要构建大顶堆。
在处理数据时，我们会构建一个大顶堆 H
，那么 H[0]
的值也就是当前数据中 最小
的 N 个数中的 最大值
，也就是第 N 小的数。
当处理新的数时，如果这个数小于堆顶的数，那么就把它变成堆顶，然后再对堆进行维护，以保证有序。
此算法的时间复杂度为 O(MlogN)
，空间复杂度为 O(N)
。其中，M 是海量数据的数量，而要求出的最小数的数量。
最后上代码，使用 Python 语言编写。
import random
class HeapForMinN:
"""求最小的 N 个数"""
def __init__(self, size):
self.size = size
self.heap = []
def add(self, num):
if len(self.heap) < self.size:
# 数据太少
self.heap.append(num)
elif len(self.heap) + 1 == self.size:
# 数据数量够了，构建堆
self.heap.append(num)
self.build_heap()
elif num < self.heap[0]:
# 使用新数替换堆顶
self.heap[0] = num
self.max_heapify(0)
def build_heap(self):
length = len(self.heap)
for i in range((length + 1) // 2, -1, -1):
self.max_heapify(i)
def max_heapify(self, index):
length = len(self.heap)
while index < length:
maxi = index
i1, i2 = index * 2 + 1, index * 2 + 2
if i1 < length and self.heap[maxi] < self.heap[i1]:
maxi = i1
if i2 < length and self.heap[maxi] < self.heap[i2]:
maxi = i2
if maxi == index:
break
self.heap[index], self.heap[maxi] = self.heap[maxi], self.heap[index]
index = maxi
def min_n(self):
return self.heap
if __name__ == "__main__":
list_ = list(range(1, 10001)) * 2
random.shuffle(list_)
N = 10
hn = HeapForMinN(N)
for i in list_:
hn.add(i)
min_n = hn.min_n()
print(min_n) # [5, 4, 5, 4, 3, 3, 1, 1, 2, 2]
assert sorted(min_n) == sorted(list_)[:n]
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
猜你喜欢:
- 改进，从一个数组中找出 N 个数，其和为 M 的所有可能
- 从一个数组中找出 N 个数，其和为 M 的所有可能--最 nice 的解法
- swoole之协程channel元素个数
- leetcode.69.求一个数的平方根
- 统计两个IP地址之间的IP个数
- 效率比较：几种方法判断一个数是否是素数
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
Java性能优化权威指南
Charlie Hunt、Binu John / 柳飞、陆明刚 / 人民邮电出版社 / 2014-3 / 109.00 元
Java性能优化圣经！Java之父重磅推荐！ 本书由曾任职于Oracle/Sun的性能优化专家编写，系统而详细地讲解了性能优化的各个方面，帮助你学习Java虚拟机的基本原理、掌握一些监控Java程序性能的工具，从而快速找到程序中的性能瓶颈，并有效改善程序的运行性能。 Java性能优化的任何问题，都可以从本书中找到答案！一起来看看 《Java性能优化权威指南》 这本书的介绍吧!
