SPL=Surpass Python Language
2 回帖  •  29 浏览  • 
待解决      ...

求助: 集算器能否实现小顶堆

 
优先队列(1) 小顶堆(1)

大佬们，早上好😄

请问集算器能否实现小顶堆 (优先队列) 这样的数据结构及其方法？比如，

方法 "创建"，可以定义小顶堆；
方法 "转换"，可以把普通对象转换成小顶堆；
方法 "弹出"，返回当前最小的值，同时，更改源数据。
方法……

最近碰到了几次要用小顶堆的情况，当然，不是说非他不行，有的话会方便高效一些。目前是这样处理的:

方法 1：维护一个有序序列，用 "A.insert(,value)" 缺省第一参数的用法让他自行升序排列且去重，然后用 A.delete@n(1) 返回序列的第一个值，同时 A 也更改了状态。这个样不停地有序插入，时间复杂度应该不止 O(n) 吧？

方法 2：不用维护有序，每次在序列的最后添加元素，然后用 "pos=A.ptop@1(1)" 返回最值所处的位置，再用 A.delete@n(pos) 得到最值的同时更改源序列。但这个方法不会去重，涉及到处理不重复的场景时，需另外维护一个有序序列，用于二分法快速判断。

这两种方法都能满足简单的需求，但方法略显复杂，不直接，且数据量变大时，insert 的效率会变的很慢。比如以下例子：

集合 S 定义如下：
(1) 1 属于 S；
(2) 如果 x 属于 S，那么 2x + 1 和 3x + 1 也属于 S；
(3) 除此之外没有其他元素属于 S。
集合S的前几项：1, 3, 4, 7, 9, 10, 13, 15, 19, 21, 22, 27...
将集合 S 中的元素按递增顺序排序后，求第 N 项。
N=100，结果=418
N=1930，结果=18909
N=1137，结果=9490

以下代码片段可直接复制到 IDE：

方法 1，模拟小顶堆

=N=100		
=now()		
=h=[1]		
=cnt=0		
for cnt<N		
	>p=h.delete@n(1)	
	>cnt+=1	
	if cnt==N	=p
	>h.insert(,[2*p+1,3*p+1])	
=interval@ms(A2,now())

方法 2：递归

=N=100		
=now()		
func fx(x)		
	if x>N*20	return x
	return conj(x,fx(2*x+1),fx(3*x+1))	
=fx(1)		
=A6.id()(N)		
=interval@ms(A2,now())

上述两个方法当 N 较小时，方法 1 会比方法 2 效率高，当 N 较大时，比如 N=500000，方法 1 中的 insert 就会变得很慢，会比方法 2 的递归慢很多。但方法 2 递归有一个不怎么好的地方，判断递归结束需预估一个阙值，x>N*20，把 N 放大一定的倍数，以保证出现需要的值。

恳请大佬们得闲时看看，能否实现小顶堆 (优先队列) 这样的数据结构和方法，谢谢！

优先队列(1) 小顶堆(1)