c++ - 从堆中移除元素

Question

我做了一堆。我很好奇我的删除功能是否有什么微妙的错误:

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

虽然我们的输出完全不同，但我似乎确实持有 maxheap 原则，即让一切都面向左，并且对于所有节点父>子节点(在我尝试过的每种情况下)。我尝试从头开始做这样的 algs，所以也许我只是在做一些非常奇怪和错误的事情(如果它是 >O(lg n)，我只会认为它是“错误的”，因为移除是为了堆)。我的删除有什么特别“错误”的地方吗？谢谢，

http://ideone.com/PPh4eQ

Answer 1

首先，我假设你的意思是除了你不需要它之外，因为我们在 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);
    }
}

这里的逻辑不是最小运动的最佳选择。被下推的元素的“较小”状态必须属于两个基本类别之一，并且对每个类别采取不同的操作:

1. 元素不小于左侧或右侧。什么都不做。
2. 该元素小于左侧或右侧，仅与最大交换，然后仅该子树。

该列表中上面的 #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);
    }
}

注:;如果不是很明显，这就是尾递归的定义，因此可以很容易地转换为简单的迭代循环。