从堆中移除元素

Question

从堆中移除元素

3

我做了一个堆。我很好奇我的删除函数是否有什么微妙的问题：

int Heap::remove() {
    if (n == 0)
        exit(1);

    int temp = arr[0];
    arr[0] = arr[--n];
    heapDown(0);
    arr[n] = 0;

    return temp;
}

void Heap::heapDown(int i)
{
    int l = left(i);
    int r = right(i);
    // comparing parent to left/right child
    // each has an inner if to handle if the first swap causes a second swap
    //  ie    1   ->   3   ->   5
    //      3   5    1   5    1   3

    if (l < n && arr[i] < arr[l])
    {
        swap(arr[i], arr[l]);
        heapDown(l);

        if (r < n && arr[i] < arr[r])
        {
            swap(arr[i], arr[r]);
            heapDown(r);
        }
    }
    else if (r < n && arr[i] < arr[r]) 
    {
        swap(arr[i], arr[r]);
        heapDown(r);

        if (l < n && arr[i] < arr[l])
        {
            swap(arr[i], arr[l]);
            heapDown(l);
        }
    }
}

以下是我的输出

i1i2i3i4i5i6i7
p
Active heap: 7 4 6 1 3 2 5

r
Removed 7
r
Removed 6
p
Active heap: 5 3 4 1 2

这是我的老师的示例输出：

p
Active heap : 7 4 6 1 3 2 5
r   
Removed 7
r
Removed 6
p
Active heap : 5 4 2 1 3
s
Heapsorted : 1 2 3 4 5

尽管我们的输出完全不同，但我似乎持有最大堆原则，即将所有节点左对齐，并使所有节点父节点 > 子节点（在我尝试的每种情况下）。我尝试从头开始编写算法，所以可能我做了一些非常奇怪和错误的事情（如果它的时间复杂度 > O(lg n)，我才会考虑将其视为“错误”，因为删除操作是用于堆的）。我的删除方式有什么特别的“错误”吗？谢谢。 http://ideone.com/PPh4eQ

- 2c2c

1

+1 问题。您提供了代码、目标说明、您看到的现象、应该发生的情况，以及两者之间的差异。示例代码很直观，虽然它不是完整的可编译代码库，但您感知到的问题核心完整地呈现出来并且可以理解。感谢您提供一个好问题。 - WhozCraig

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- WhozCraig · Accepted Answer

首先，我假设你指的是除了我们在C++标准库中拥有整个堆管理函数集之外，你不需要它的事实，包括make_heap、push_heap、pop_heap甚至sort_heap。

话虽如此，我认为我知道你的问题所在。你的堆中存在不必要的元素移动。这涉及到堆下交换算法：左右两侧都存在同样的问题，因此我将展示第一个问题：

if (l < n && arr[i] < arr[l])
{
    swap(arr[i], arr[l]);
    heapDown(l);

    if (r < n && arr[i] < arr[r])
    {
        swap(arr[i], arr[r]);
        heapDown(r);
    }
}

这里的逻辑对于最小运动并不是最佳的。被推下去的“较小”元素必须落入两个基本类别中的一个，对于每个类别采取不同的操作：

该元素既不小于左侧也不小于右侧。什么也不做。
该元素小于左侧或右侧，仅与最大的交换，然后向只有该子树中驱动下降。

以上列表中的#2是您代码中的问题。如果item < left < right，则您将与较小的元素交换，然后才是较大的元素。希望这一点很清楚。如果您想要一个修正逻辑的建议，我可以提供一个，但我认为如果您理解了上面所述的内容，您可能已经掌握了它。

剧透

void Heap::heapDown(int i)
{
    int l = left(i);
    int r = right(i);
    int x = 0;

    if (l < n && arr[i] < arr[l])
    {
        x = l;
        if (r < n && arr[l] < arr[r])
            x = r;
    }

    else if (r < n && arr[i] < arr[r])
        x = r;

    if (x != 0)
    {
        swap(arr[i], arr[x]);
        heapDown(x);
    }
}

注意: 如果没有明显的表述，这就是尾递归的定义，并且可以轻松地转换为简单的迭代循环。