大根堆和小根堆在海量数据的top N问题中,时间复杂度O(nlogN)

发布时间 2023-06-22 22:08:01作者: sangern

堆可视化操作演示:https://visualgo.net/zh/heap

堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:
小根堆:Key[i]<=key[2i+1]&&Key[i]<=key[2i+2] 或者 大根堆 Key[i]>=Key[2i+1]&&key>=key[2i+2]

即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。


堆分为大根堆和小根堆:
满足Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大根堆(Max-heap),
满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小根堆(Min-heap)。
由上述性质可知大根堆的堆顶的关键字肯定是所有关键字中最大的,小根堆的堆顶的关键字是所有关键字中最小的。

 

其中,大根堆和小根堆在海量数据的top N问题中,有着很好的时间复杂度。

利用小根堆解决获取大量数据中最大的N个值
利用大根堆解决获取大量数据中最小的N个值

调整一次的时间复杂度是O(logN)。所以,通过堆来解决top N 问题的时间复杂度是O(nlogN)
其中,n为数据的个数,N为堆维护的数据的个数。
==================

实现堆,最关键的是对元素的移动(上移/下移)。所有函数都是基于这两种操作完成的。

binary heap的定义在维基百科中, sift-up 也称为 up-heap 操作,sift-down 称为 down-heap。
sift筛选
heapq.py中,
down指的是从堆底到堆顶的过程,指的是元素的索引小了,down了。反过来,up就是堆顶到堆底的过程,索引大了,up了。
_siftdown函数:将元素向堆顶移动到符合条件为止