如何实现支持快速查找的堆？双数组堆实现方法是什么？

传统单数组实现的二叉堆没有额外索引结构，查找任意元素必须遍历全量存储，时间复杂度稳定为O(n)，做指定元素删除、优先级更新这类操作时效率瓶颈非常明显。你提到的双数组结构本质是带反向位置索引的增强堆（也常称可索引堆），两个数组分工明确，没有复杂的结构改动，就能把查找效率降到O(1)：

• 第一个数组是常规堆存储数组，一般命名为heap[]：完全遵循普通二叉堆的结构规则，存储实际的节点值，父子节点下标计算逻辑和传统堆完全一致：左子节点下标为2*i+1、右子节点下标为2*i+2、父节点下标为(i-1)//2，堆的上浮、下沉、堆化逻辑都在这个数组上执行。
• 第二个数组是反向位置映射数组，一般命名为pos_map[]：数组下标和堆内存储的元素值一一对应（如果元素是非整数类型，可替换为哈希表实现相同映射逻辑），pos_map[val]存储的是值为val的元素当前在heap[]数组中的具体下标。

双数组堆的核心维护规则非常简单：所有会改动元素在heap[]中位置的操作（插入、弹出堆顶、上浮、下沉），都必须同步更新pos_map中的映射记录，保证两个数组的对应关系始终一致。

最核心的改动只出现在节点交换逻辑里，传统堆交换i、j两个位置的节点只需要做值互换：

# 传统单数组堆的节点交换
temp = heap[i]
heap[i] = heap[j]
heap[j] = temp

双数组堆的交换逻辑只需要额外补两步索引更新，其他堆化流程和传统堆完全一致：

# 双数组堆的节点交换
# 先更新反向索引
pos_map[heap[i]] = j
pos_map[heap[j]] = i
# 再做值交换
temp = heap[i]
heap[i] = heap[j]
heap[j] = temp

基于pos_map的O(1)查找能力，你可以直接在O(logn)时间复杂度内完成指定元素删除、指定元素优先级调整这类传统堆很难高效实现的操作，非常适配Dijkstra最短路径计算、定时任务调度、动态优先级队列这类场景。

实现时需要注意几个容易出问题的点：

• 如果你的业务场景允许堆内存在重复元素，pos_map不能直接存储单个下标，需要存储对应值的下标集合，避免索引覆盖导致映射错乱
• 上浮、下沉流程中只要发生元素位置变动，必须第一时间同步更新pos_map，只要漏一次更新就会出现索引错位，后续所有操作都会失效
• 如果存储的是复杂对象，不要直接用对象本身作为pos_map的键，要给每个对象分配全局唯一ID作为映射键，避免哈希冲突或者对象属性变动导致映射失效

内容的提问来源于stack exchange，提问作者user56202