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

Asked 2011-01-19T17:17:24.287

I'm using a priority queue as a scheduler with one extra requirement. I need to be able to cancel scheduled items. This equates to removing an item from the middle of the priority queue.

I can't use std::priority_queue as access to any element other than top is protected.

I'm trying to use the algorithm's heap functions. But I'm still missing the piece I need. When I remove an element I from the middle of the heap I want it to rebuild itself efficiently. C++ provides these heap functions:

std::make_heap O(3n)
std::push_heap O(lg(n))
std::pop_heap O(2 lg(n))

I want a new function like std::repair_heap with a big-O < 3n. I'd provide it with location of the hole where the canceled item used to reside and it would properly adjust the heap.

It seems to be a huge oversight to not to provide a std::repair_heap function. Am I missing something obvious?

Is there library that provides an stl-compliant std::repair_heap?

Is there a better data structure for modeling a scheduler?

NOTE:
I'm not using an std::map for a few reasons.

A heap has constant memory overhead.
A heap has awesome cache locality.

Edit Report

2 Answers

-1

It seems to me that removing from the middle of a heap might mean the entire heap has to be rebuilt: The reason there's no repair_heap is because it would have to do the same (big-oh) work as make_heap.

Are you able to do something like put std::pair<bool, Item> in the heap and just invalidate items instead of removing them? Then when they finally get to the top just ignore the item and move along.

answered 2011-01-19T17:32:49.953

-2

Here's a bit of delphi code i used to remove items from a heap. I don't know this C++ of which you speak and don't have a repair function, but hey..

first the pop, so you get an idea of how the thing works:

function THeap.Pop: HeapItem;
begin
  if fNextIndex > 1 then begin
    Dec(fNextIndex);
    Result:= fBuckets[1];   //no zero element
    fBuckets[1] := fBuckets[fNextIndex];
    fBuckets[fNextIndex] := nil;
    FixHeapDown;            //this has a param defaulting to 
    end
  else
    Result:= nil;
end;

now to contrast, the deletion:

procedure THeap.Delete(Item: HeapItem);
var
  i:integer;
begin
  for i:=1 to pred(fNextIndex) do
    if Item=fBuckets[i] then begin
      dec(fNextIndex);
      fBuckets[i] := fBuckets[fNextIndex];
      fBuckets[fNextIndex] := nil;
      FixHeapDown(i);
      break;
      end;
end;

its of course a no-no to even think about doing what we're doing here, but hey, costs do change sometimes and jobs do get canceled.

enjoy. i hope this helps.

answered 2011-01-27T19:02:35.560

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

2 Answers

Your Answer