C++ standard template library priority queue throws exception with message "Invalid Heap"

Question

Using the STL's priority_queue I get the error "invalid heap" as soon as I try to use pop(). I can push my values into the queue, the top() of the queue is what I would expect and accessible. pop(), when it goes to re-heap, seems to have a problem.

I am storing pointers to a templated class in the queue. I have the comparision overloaded:

template <class type>
class vertexPriorityCompare
{
public:
   bool operator()(Vertex<type>* leftVertex, Vertex<type>* rightVertex) const
   {
      if(leftVertex->getDistanceFromSource() < 0 && rightVertex->getDistanceFromSource() < 0)
      {
         return false;
      }
      else if(leftVertex->getDistanceFromSource() < 0)
      {
         return true;
      }
      else if(rightVertex->getDistanceFromSource() < 0)
      {
         return false;
      }
      else
      {
         return leftVertex->getDistanceFromSource() > rightVertex->getDistanceFromSource();
      }
   }
};

The priority_queue is a private member of a class:

priority_queue< Vertex<type>*, vector< Vertex<type>* >, vertexPriorityCompare<type> > Q;

The overload works in the fashion it does, because a negative distance is considered infinity, always larger than whatever else; to represent infinity, distances are initialized to -1. The queue needs to keep the smallest, but non-negative at the top.

I dereference the pointers in the overload, is what I'm doing there allowable? And, is there another operator I need to overload?

I would attach code, but it seems if I do, it scares people away. Request to see more and I'll attach to another message.

I dynamically declare an array of pointers to pointers, these are what get pushed, because I assume priority_queue stores by reference, so if I just put a pointer declared in the loop into the queue, that pointer goes out of scope. These pointers point to the proper Vertex<type>, and exist throughout the function.

Visual Studio 2008 debugger takes me into 'stdthrow.cpp' line 24.

Answer 1

Where are you calling this function from?

My guess is that the invalid heap is a pointer that you're passing into the function from "this function caller's" code. Or maybe you're going out of bounds when you are taking the vertex out of your vector.

I don't see anything wrong with that function.

Please supply the stack trace

Answer 2

Without the callstack, it will be a bit difficult to determine what the problem is, but you are either not allocating the Vertex<...> correctly, attempting to free Vertex<...> from the stack, or not initializing the Vertex<...>* to valid values.

MSN

Answer 3

It's probably your comparison function. To test, replace it with a simple version that just compares pointers:

bool operator()(...)
{
  return leftVertex<rightVertex;
}

If the problem no longer occurs then the problem was your comparison function was invalid. Your comparator must define a "strict-weak ordering". I'm not man enough to show it doesn't, but I bet that's it.

Answer 4

The comparison function looks fine, if the value of an objects getDistanceFromSource() doesn't change, while that object is in the queue. Is that ensured? Or are there maybe changes made to the objects, that influence getDistanceFromSource(), while they are in the queue or while the queue is initially filled?

Answer 5

This bit scares me:

I dynamically declare an array of pointers to pointers, these are what get pushed, because I assume priority_queue stores by reference, so if i just put a pointer declared in the loop into the queue, that pointer goes out of scope. These pointers point to the proper Vertex, and exist throughout the function.

It's not clear quite how you are populating the queue. You must create Vertex objects and they must remain in memory and return the same distance the entire time they are in the queue.

The queue doesn't store by reference, it stores copies - but in this case what you are putting in are pointers, so it copies the pointer, which will still point to the original objects you allocated.

I think we'll need a short complete example in order to get any further.