so I need to make a minHeap. I used a stl priority queue and set it up as a heap
ID: 3554848 • Letter: S
Question
so I need to make a minHeap. I used a stl priority queue and set it up as a heap >
std::priority_queue<List,std::vector<class>,std::greater<class> > Q;
bool operator> (const List &B) const
{
return distanceFromSource > B.distanceFromSource;
}
I also defined this function in the class that will be the elements of the queue so that it knows how to compare the elements, but it does not seem to maintain the heap properties as values are changed and elements are poped. the elements values change, but its spot in the heap does not reflect this. Do I need to call another function such as build heap to maintain the heap or is this just not possible to use this implementation of a heap in this way
Explanation / Answer
From what I understand of what you're trying to do, you are attemping to change the value of the priority while the data is still inside of the data structure. If I am incorrect in this interpretation, then ignore the rest of what I say.
Otherwise, this is not possible. In terms of computation time, if you were to change the priority after every single insertion, then the data structure would need to completely rebuild itself every single time an insertion was made. This is because the data structure cannot really know which data points have been affected or not, so all of them have to be checked. This is very bad in terms of computation as it is very resource heavy and slow.
In any type of data structure, once inserted into the data structure it should never change. The only data structure in STL that could possibly be used to even build a heap would be vector, but that is only because it has random access. Basically, you can build a heap with an array, or as a binary tree. However, you cannot depend on the behavior of other data structures to find your solution.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.