How to Remove an Arbitrary Element from a Standard Heap in C++

Remove an element from the middle of an std::heap

Unfortunately, the standard is missing this (fairly important) function. With g++, you can use the non-standard function std::__adjust_heap to do this, but there's no easy portable way of doing it -- and __adjust_heap is slightly different in different versions of g++, so you can't even do it portably over g++ versions.

c++ heap with removing any element method

When you need to remove (or change the priority of) other objects than the root, a d-heap isn't necessarily the ideal data structure: the nodes keep changing their position and you need to keep track of various moves. It is doable, however. To use a heap like this you would return a handle to the newly inserted object which identifies some sort of node which stays put. Since the d-heap algorithm relies on the tree being a perfectly balanced tree, you effectively need to implement it using an array. Since these two requirements (using an array and having nodes stay put) are mutually exclusive you need to do both and have an index from the nodes into the array (so you can find the position of the object in the array) and a pointer from the array to the node (so you can update the node when the position changes). Almost certainly you don't want to move your nodes a lot, i.e. you rather accept finding the proper direction to move a nodes by searching multiple nodes, i.e. you want to use a d > 2.

There are alternative approach to implement a heap which are inherently nodes based. In particular Fibonacci heaps which yield for certain usage patterns a better amortized complexity than the usual O(ln(n)) complexity. However, they are somewhat harder to implement and the actual efficiency only pays off if you either need to change the priority of a node frequently or you have fairly large data sets.

How to delete in a heap data structure?

Actually, you can remove an item from the middle of a heap without trouble.

The idea is to take the last item in the heap and, starting from the current position (i.e. the position that held the item you deleted), sift it up if the new item is greater than the parent of the old item. If it's not greater than the parent, then sift it down.

That's the procedure for a max heap. For a min heap, of course, you'd reverse the greater and less cases.

Finding an item in a heap is an O(n) operation, but if you already know where it is in the heap, removing it is O(log n).

I published a heap-based priority queue for DevSource a few years back. The full source is at http://www.mischel.com/pubs/priqueue.zip

Update

Several have asked if it's possible to move up after moving the last node in the heap to replace the deleted node. Consider this heap:

        1
    6       2
  7   8   3

If you delete the node with value 7, the value 3 replaces it:

        1
    6       2
  3   8

You now have to move it up to make a valid heap:

        1
    3       2
  6   8

The key here is that if the item you're replacing is in a different subtree than the last item in the heap, it's possible that the replacement node will be smaller than the parent of the replaced node.

Removing elements from heap

First, I assume you mean besides the fact that you don't need it, since we have an entire heap management function set in the C++ standard library, including make_heap, push_heap, pop_heap, and even sort_heap.

That said, I think I know what your problem is. You have unnecessary movement of elements in your heap. It deals with the swapping algorithm on the heap-down: the same problem is notable on both left and right sides, so I'll show the first one:

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);
    }
}

The logic here is not optimal for minimum motion. The "lesser" state of the element being pushed down must fall into one of two basic categories, and different actions are taken for each:

1. The element is not less than either left or right. Do nothing.
2. The element is less than either left or right, swap only with the largest, then drive down into only that subtree.

The #2 above in that list is the problem in your code. you swap with the smaller, then the larger, if item < left < right. I hope that is clear. If you want a proposal to fix your logic I can provide one, but I think you may have a handle on it if you understand what I described above.

---

Spoiler

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);
    }
}

Note:; In case it wasn't obvious, this is the very definition of tail-recursive, and as such could easily be transformed into a simple iterative loop.

Deleting the topmost element in the binary heap

Your fixheap2 fails to consider the case where both children are valid but have keys smaller than the parent's. In that situation, the heap property has been restored, and you should stop swapping with children (or you'll re-invalidate it).

---

Related Topics