为什么堆的 'delete' 操作（不是最大或最小）需要 O(n)？
Why does 'delete' operation(Not max or min) of heap take O(n)?
众所周知，对堆进行删除操作需要 O(n)（注意：不是最大值或最小值）。我知道堆不适合删除或更新，但有点好奇。
我认为如果我想删除某个元素，我认为只需 percDown(element) 和 heapSize-- 就可以完成....所以我认为需要 O(logn)?
我是不是漏掉了什么？
我假设您正在谈论基于标准数组的完整二叉树实现。
简短的回答是不需要。如果您维护从堆中的对象到存储它们的索引的并行映射，那么您可以使用筛选操作在 O(log n) 中删除以将堆 属性 恢复为 "fill the hole"删除。
朴素的实现需要 O(n)，因为它们从搜索堆数组开始。堆 属性 没有什么比 O(n) 更有效的了。
如果您有兴趣，here is an implementation 将索引堆保存到一个对象数组中（而不是将对象保存在堆节点中）和一个反向索引 - 只是一个整数数组 - 它需要对象数组中的索引到它在堆数组中的索引。此反向映射不会更改任何其他操作的渐近 运行 时间，但它提供了 O(log n) 删除。
众所周知，对堆进行删除操作需要 O(n)（注意：不是最大值或最小值）。我知道堆不适合删除或更新，但有点好奇。
我认为如果我想删除某个元素，我认为只需 percDown(element) 和 heapSize-- 就可以完成....所以我认为需要 O(logn)?
我是不是漏掉了什么？
我假设您正在谈论基于标准数组的完整二叉树实现。
简短的回答是不需要。如果您维护从堆中的对象到存储它们的索引的并行映射，那么您可以使用筛选操作在 O(log n) 中删除以将堆 属性 恢复为 "fill the hole"删除。
朴素的实现需要 O(n)，因为它们从搜索堆数组开始。堆 属性 没有什么比 O(n) 更有效的了。
如果您有兴趣，here is an implementation 将索引堆保存到一个对象数组中（而不是将对象保存在堆节点中）和一个反向索引 - 只是一个整数数组 - 它需要对象数组中的索引到它在堆数组中的索引。此反向映射不会更改任何其他操作的渐近 运行 时间，但它提供了 O(log n) 删除。