如何删除堆数据结构？

我知道如何从最大堆中删除根节点，但是是从中间删除一个节点以删除并重复replace根，直到删除所需节点的过程？

实际上，你可以毫不费力地从堆中取出物品。

这个想法是把堆中的最后一个项目，从当前位置（即持有删除的项目的位置）开始，如果新项目大于旧项目的父项目，则将其筛选。如果它不大于父母，则将其筛选。

这是最大堆的程序。当然，对于一个小堆，你会扭转越来越less的情况。

在堆中查找项目是一个O（n）操作，但是如果您已经知道它在堆中的位置，则删除它是O（log n）。

几年前，我为DevSource发布了一个基于堆的优先队列。请参阅C＃中的优先级队列实现。它有一个RemoveAt方法，正是我所描述的。

完整的源代码位于pubs/priqueue.zip

从堆中删除任意元素的问题是，您无法find它。

在一个堆中，寻找一个任意元素是O(n) ，因此删除一个元素[如果给定值]也是O(n) 。

如果从数据结构中删除任意元素很重要，那么堆可能不是最佳select，您应该考虑完全sorting的数据结构，而不是平衡BST或跳过列表。

如果你的元素是通过引用给出的，但是可以通过简单地用最后一个叶代替它来在O(logn)删除它[记住一个堆被实现为一个完整的二叉树，所以有一个最后一个叶，你确切知道它在哪里]，删除这些元素，并重新heapify相关的子堆。

如果你有一个最大的堆，你可以通过赋值大于任何其他的值（例如int.MaxValue或inf ，无论使用哪种语言），将其删除，然后重新heapify成为新的根。然后执行定期删除根节点。

这会导致另一个重新堆积，但我看不到一个明显的方法来避免两次。这表明，如果您需要经常从中间拉取节点，那么可能堆不适合您的使用情况。

（对于一个小堆，你显然可以使用int.MinValue或-inf或其他）

你想实现的不是一个典型的堆操作，在我看来，一旦你引入了“删除中间元素”作为一种方法，其他二叉树（例如红黑或AVL树）是一个更好的select。你有一些用某种语言实现的红黑树（例如map和c ++中的set）。

否则，按照rejj的回答，中间元素删除的方法是：给元素分配一个大值（对于最大堆）或者小值（对于最小堆），筛选它直到它为根，然后将其删除。

这种方法仍然保持中等元素删除的O（log（n））复杂度，但是您提出的方法却是这样。它将具有复杂性O（n * log（n）），因此不是很好。希望有所帮助。