Est*_*spi 8 c++ algorithm data-structures
在优化问题中,我在队列中保留了许多候选解决方案,我根据它们的优先级来检查.
每次我处理一个候选人时,它会从队列中删除,但它会产生几个新的候选人,使得候选人数呈指数级增长.为了处理这个问题,每当候选人被添加到队列中时,我就为每个候选人分配一个相关性,如果没有更多的空间可用,我用新的候选者替换(如果适当的话)队列中当前最不相关的候选人.
为了有效地做到这一点,我保留了一个大的(固定大小)数组与候选和两个链接的间接二进制堆:一个以递减的优先级顺序处理候选,另一个以递增的相关性处理候选.
这对我的目的来说足够有效,并且所需的补充空间大约是4个投注/候选人,这也是合理的.然而,编码很复杂,而且看起来并不是最佳的.
我的问题是,如果您知道更合适的数据结构或更自然的方式来执行此任务而不会降低效率.
这是一个有效的解决方案,不会改变正常堆的时间或空间复杂性:
在最小堆中,每个节点都少于其子节点.在max-heap中,每个节点都大于其子节点.让我们在每个级别的最小和最大属性之间交替进行:每个奇数行小于其子级及其孙级,以及偶数行的逆.然后找到最小的节点与通常相同,找到最大的节点需要我们查看根的子节点并取最大的节点.冒泡节点(用于插入)变得有点琐碎,但它仍然是相同的O(logN)复杂度.
跟踪容量并弹出最小(最不相关)的节点是很容易的部分.
编辑:这似乎是标准的最小 - 最大堆!请参阅此处以获取说明.有一个C实现:头,源和示例.这是一个示例图:
http://internet512.chonbuk.ac.kr/datastructure/heap/img/heap8.jpg
| 归档时间： |
|
| 查看次数： |
654 次 |
| 最近记录： |
