rock 算法
遇到一次两难的境地:使用堆实现rock聚类算法的情况下,在查找删除最大值对应的对象时,可以在常数时间进行操作,但是在以id(对象的某个非入堆比较属性)进行删除或者更新的时候,问题就来了
- 如果使用二叉堆实现的话,那么直接使用id为索引的数组存放树节点的引用,可以直接实现删除操作,但是需要重新实现二叉平衡堆,而且删除该树节点的时候需要进行堆调整,而且需要进行平衡调整,这样的话实现起来需要重新考虑
- 使用heapq模块,查找对应的id的对象需要的时间复杂度为O(n),使用heapq模块的底层函数进行堆调整复杂度为O(logN)
- 之后改进的方案可以从方法一进行改进,即关键就是删除某个节点后进行堆调整的同时能够保持树的平衡
现在还是使用heapq实现再说吧