从堆中删除随机元素

Question

看了几篇文章说，在堆中，只能删除根元素。但是，为什么我们不能使用以下方法删除元素？

找到要删除的关键元素的索引
将此元素与最后一个元素交换，因此键成为最后一个元素
从键的原始索引开始重新堆化（您现在已与最后一个元素交换）
将堆大小减少 1

所以，代码看起来像

static void delete(int[] a, int key)
    {
        int i = 0;
        for(i = 0;i<a.length;i++)
        {
            if(a[i] == key)
                break;
        }
        swap(a, i, a.length-1);

        max_heapify_forheapsort(a, i, a.length-2);
    }

static void max_heapify_forheapsort(int[] a, int i, int limit)
    {
        int left = (2*i)+1;
        int right = (2*i) + 2;
        int next = i;

        if(left <= limit && a[left] > a[i])
            next = left;
        if(right <= limit && a[right] > a[next] )
            next = right;

        if(next!=i)
        {
            swap(a, next, i);
            max_heapify_forheapsort(a, next, limit);
        }
    }

Answer 1

当然可以按照您的建议通过向上筛选或向下筛选操作从堆中删除元素。（同样可以更改堆中任何项的键并使用 sift-up 或 -down 操作来恢复堆属性。）

棘手的一点是您一开始就快速陈述的内容："Find the index." 天真的实现需要 O(n) 才能完成此操作，这会降低堆效率。当人们说 "you can't delete" 时，他们的意思是使用天真的实现无法有效地删除。

幸运的是，找到索引 O(1) 并不难。只需维护一个与堆数组并行的 "reverse map"，例如从对象到堆数组索引的哈希映射。更新此映射很容易，而无需向任何堆操作添加渐近复杂性，并且正如您所指出的那样，删除的复杂性为 O(log n)。 sift up/down 支配地图查找以查找索引。

如果您对经过测试的实现感兴趣，here's one 其中堆包含指向另一个对象数组的索引。因此反向映射被实现为数组 q->locs[k]，它是包含 k 的堆元素的索引（这是对象 table 的索引）。

计算机科学中的许多问题都可以通过添加一个间接级别来解决！

编辑

由于 OP 询问为什么可能需要筛选才能删除，请考虑最小堆

          1
    20          2 
 30    40    3     4

我们要删除 30，所以将 4（最后一个数组元素）移到它的位置：

          1
    20          2 
 4     40    3

显然需要进行筛选。

Answer 2

堆的根有一个属性，它与所有其他元素相关。当根被删除时，只有一个其他元素会满足该条件，它（可能）不是您要删除的那个。因此，交换元素将使堆无效，结果不确定。

Answer 3

如果是Minheap,

将要删除的元素存储在变量中。
用最小整数替换中的元素。 Heapify 向上到根。
移除根到Heapify下来维护堆属性.
Return 存储的变量。来源- GeeksforGeeks。

从堆中删除随机元素

Deleting a random element from a heap

java

algorithm

heap

clrs

data-structures