java - 有人可以向我解释间接堆/间接优先级队列的概念吗？

Question

我必须为一个项目构建一个间接堆，我不太明白这意味着什么。如果您正在从数组中构建堆，那么实现间接寻址是否只是添加某种映射数据结构来将每个项目与其索引相关联？还是比这更复杂？

Answer 1

间接堆是一种堆，其中存储的数据项是保存实际项的列表、数组或其他数据结构的索引。

假设您有一个姓名列表:["jim","joe","bob","sam","susan","kelly","jessica"]，其中你想建立一个堆。直接堆将具有:

         bob
    joe        jessica
sam   susan  jim    kelly

间接堆将用列表中的索引替换堆中的名称:

         2
    1        6
 3     4   0   5

你的比较函数必须改变。您最终不是将 heap[0] 与 heap[1] 进行比较，而是将 list[heap[0]] 与 list 进行比较[堆[1]]。

有些人称之为半间接堆。用他们的话说，直接堆包含从名称到索引的附加映射。