priority queue
· 2 min read
lucene 搜索的结果搜索经过soccer算出分数之后，还需要topK取前几个数据，所以需要使用到topk的算法。 一般用优先队列实现。
介绍
下面都是描述最大优先队列
优先队列分为两个，一个是最小优先，一个是最大优先。其实就是方向改变而已。
我们先介绍他的性质：
组成 : 优先队列是item集合S 。每个item 包含两个内容：element 和key
操作：
- insert(S , item)
- maxnum(S)
- extract_max(S)
- increase_key (S,element,key) 将优先队列里面
证明
对于一个非空满二叉树，第一个节点编号是index=1 则对每个节点index :
- 他的左节点left=index *2
- right = index *2 +1
证明：
归纳法
init:
当index= 1 时， left = 2 ， 满足left = index*2
当index=1 时，right = 3 ， 满足 right = index*2 +1
deduction: n+1 元素： 如果他是左节点 ， 则他的前一个节点满足 n = (pre_parent *2 +1) 对于n+1 个元素 ， n+1 = (pre_parent *2 +1) +1 = (pre_parent +1 )*2 即满足递推公式
同理右节点同理
所以证明完毕