从堆中删除随机元素

Question

我读了一些文章说,在堆中,只能删除根元素.但是,为什么我们不能使用以下方法删除元素？

1. 找到要删除的键元素的索引
2. 将该元素与最后一个元素交换,因此该键成为最后一个元素
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或-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 

显然需要筛选.