java - 从堆中删除一个随机元素

Question

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

1. 找到要删除的关键元素的索引
2. 把这个元素和最后一个元素交换，这样key就变成了最后一个元素
3. 从键的原始索引开始重新堆化（您现在已与最后一个元素交换）
4. 将堆大小减少 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 或 sift-down 操作从堆中删除元素。（同样可以更改堆中任何项目的键并使用 sift-up 或 -down 操作来恢复堆属性。）

棘手的一点是您一开始就快速陈述的内容：“查找索引。” 一个简单的实现需要 O(n) 才能做到这一点，这会降低堆效率。当人们说“你不能删除”时，他们的意思是，如果使用幼稚的实现，你就不能有效地删除。

幸运的是，找到索引 O(1) 并不难。只需维护与堆数组并行的“反向映射”，例如从对象到堆数组索引的哈希映射。更新此映射很容易，而无需向任何堆操作添加渐近复杂性，并且正如您所指出的那样，删除的复杂性为 O(log n)。向上/向下筛选主导地图查找以查找索引。

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

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

编辑

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

          1
    20          2 
 30    40    3     4

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

          1
    20          2 
 4     40    3 

显然需要进行筛选。

Answer 2

如果是Minheap，

• 将要删除的元素存储在变量中。
• 用最小整数替换元素。Heapify上到根。
• 删除根以Heapify保持堆属性。
• 返回存储的变量。来源 - GeeksforGeeks。

Answer 3

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