Nic*_*ris 2 algorithm data-structures max-heap
我有一个MaxPQ堆使用数组来存储元素.我可以使用什么算法来查找堆中的给定元素？我当前使用的算法迭代遍历索引1的数组,直到添加到堆中的元素数.该算法具有O(N)的复杂度,是否存在复杂度为O(logN)的算法？
如果你只有一个表示堆的数组(最小值或最大值)而不是我害怕找不到最坏情况的对数算法,因为从树的顶部开始你将无法告诉一般哪个子树要搜索.如果你的root是100并且它的子节点是90和80,并且你正在寻找5,你必须(通常)探索两条路径.
现在,如果你保留一个辅助数据结构来跟踪你的键数组中的位置,你就可以进行恒定的时间查找.我在http://eclipse.wells.edu/badams/courses/cs322/notes/topics/tools/heap.html找到了以下描述
要查找任意元素,有助于维护由节点名称索引的附加数组,并通过它们在堆中的位置(指针或索引号)进行键控.这使得任意节点的查找在恒定时间内工作,并且维护数组中的数据仅需要针对每个冒泡操作执行固定数量的步骤,因此不会更改堆启动或关闭的渐近时间.
再说一次,只考虑堆,你的最坏情况将是线性的,但如果你遍历堆并进行一些修剪,你可能会在实践中获得一点加速.
| 归档时间： |
|
| 查看次数： |
7929 次 |
| 最近记录： |