[HEAP] - 删除节点后，您是否应该对所有节点进行筛选或仅此根？
我已经看到了二进制堆的实现，其中删除节点后，hepifydown/siftdown（作者命名为什么）仅在根上运行以重新占用树，而有些则在所有项目上迭代地运行了从底部进行筛选直到根。
我认为，在删除节点之前，n个项目的树已经已经建立/堆积并满足最小或最大 - 高位属性。如果这是真的 - 试图在节点上进行筛选（n // 2）-1 [第一个非叶子节点带有索引从0]和向上有什么意义？这是一个糟糕的实施，还是我错过了什么？
*额外的问题：是否有任何理由从最小值或最高壁的中间删除节点？我认为提取根或最后一个元素是最重要的。当将堆用作数据结构时，在实践中是否曾经完成它？
I have seen implementations of binary heap where after removal of a node, heapifyDown/siftDown (whatever the author names it) is run only on the root to re-heapify the tree, and some where siftDown is run iteratively on all items from the bottom up to the root.
I assume that before one would remove a node, the tree of N items is already built/heapified and satisfies min- or max-heap property. If that's true - what's the point of trying to run siftDown on nodes (N//2)-1 [first non-leaf node with indexing from 0] and up, let alone ALL nodes from the end- instead of sifting only the root? Is that a poor implementation, or am I missing something?
*Extra question: are there any reasons for removing nodes from the middle of a min- or max-heap? I would think extracting the root, or maybe the last element, is most important. Is it ever being done in practice when heap is used as data structure?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
删除最小值后，无需在所有元素上运行HeapifyDown /筛选。这确实可以修复堆，但是要这样做需要时间o（n），这很慢，并且打败了拥有二进制堆的目的。相反，传统算法是将堆的最后一个元素交换到顶部，然后在其上调用HeapifyDown / SiftDown。这需要时间O（log n），这比重建整个堆的速度要快得多。
至于从堆中间删除节点 - 这并不罕见，但并非闻所未闻。更常见的是，对于诸如Dijkstra的最短路径算法或PRIM的最小跨越树算法之类的图形算法，可以在堆中获取一个元素，并减少其优先级（以分钟为单位）或增加它（在最大堆中）。这可以通过在堆中找到元素，降低其优先级，然后在其上调用heapifyup / siftup来恢复堆属性。
There’s no need to run heapifyDown / siftDown on all elements after removing the minimum. That will indeed fix the heap, but it takes time O(n) to do this, which is pretty slow and defeats the purpose of having a binary heap. Instead, the traditional algorithm is to swap the last element of the heap to the top, then call heapifyDown / siftDown on it. This takes time O(log n), which is much faster than rebuilding the whole heap.
As for removing nodes from the middle of the heap - that’s fairly uncommon but not unheard of. What’s more common is, for graph algorithms like Dijkstra’s shortest paths algorithm or Prim’s minimum spanning tree algorithm, to take an element in the heap and reduce its priority (in a min heap) or increase it (in a max heap). This can be done by locating the element in the heap, reducing its priority, and then calling heapifyUp / siftUp on it to restore the heap property.