3

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.

Improve this question
1
  • The Visual Studio debugger should also give you a callstack. That might be helpful too. Commented Jan 23, 2009 at 22:24

5 Answers 5

Reset to default
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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

+1 Part of "strict weak ordering" says that if Compare(x,y) is true, Compare(y,x) must be false. This function does not handle that situation if both distance values are -1.
In addition, the link to the SGI page points out where the issue is occurring - in the *_heap operations that are used on the vector to maintain the nature of the priority_queue. Internally, make_heap, push_heap, and pop_heap are called - since strict weak ordering isn't maintained, they fail.
Doesn't the first if ensure that -1,-1 returns false both ways round?
@Douglas Leeder: exactly, and that's a Bad Thing(TM) for strict weak ordering.
@Harper Shelby not it seems OK in this respect: for this Compare when both distances are -1, Compare(x,y) = Compare(y,x) = false so the requirement is not broken. This comparison implements the following "All negative distances are equivalent and strictly lower than any non-negative distance." No problem with that.
3

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?

Improve this answer

1 Comment

I've accidentally run into this exact problem before, and this was the reason.
0

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

Improve this answer

Comments

0

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.