擅长:python、mysql、java
<p>我总是最终实现我自己版本的堆类型,原因正是您不能在堆中实际搜索,而所有有效的方法都需要“指向元素的指针”作为输入。在</p>
<p>通常,我将堆实现为非结构化项容器和指向项的指针(或索引)堆的组合。如果在项中保留指向堆位置的指针,则会有一个即时双向链接:
a) 给定一个堆元素(例如,由extractMin返回,或者在比较过程中):取消对指针的引用,就得到了你的项。
b) 给定一个项(例如,通过一个图算法的邻接列表):将指针传递到您想要的任何更新函数。在</p>
<p>当然,这会造成空间开销(每个项目2个额外的指针/整数),但这使得堆重组非常便宜(交换一些指针而不是交换整个项目),这反过来也会使向项目添加一些额外的卫星数据变得不那么痛苦。在</p>