0

I am fairly new to C++ and I was trying to implement a Min Heap using Priority Queue STL in C++. I looked around the web and chanced upon a code, the link to which I have added at the bottom.

I understand how vectors work and I also understand what a functor is but I can't understand how 'return i>j' plays a part in arranging the elements from minimum to maximum.

I will post the code here.

#include <queue> #include <iostream> using namespace std; struct comparator { bool operator()(int i, int j) { return i > j; } }; int main(int argc, char const *argv[]) { priority_queue<int, std::vector<int>, comparator> minHeap; minHeap.push(10); minHeap.push(5); minHeap.push(12); minHeap.push(3); minHeap.push(3); minHeap.push(4); while (!minHeap.empty()) { cout << minHeap.top() << " "; minHeap.pop(); } return 0; }

Could someone please trace the program's execution? I have been trying to understand how this program works for the past couple of hours with no luck.

I got the code from here

Improve this question
3
  • Do you have a debugger you can use to trace the execution? Commented Apr 4, 2016 at 1:53
  • 1
    If you'd like to trace the program's execution, every compiler also has a related debugger, a tool that you, yourself, can use to step through the code, and see how it works, step by step. You will do yourself a big favor if you invest some time in learning how to use your debugger to step through the code you have compiled. A skill that, sadly, many posters to stackoverflow.com sorely lack. Commented Apr 4, 2016 at 1:54
  • I am a newbie to programming and have not learnt how to use a debugger yet. But I will learn it soon. Commented Apr 4, 2016 at 1:55

1 Answer 1

Reset to default
2

Priority queues first element is always the greatest of the elements it contains, according to a given criterion. This criterion is your functor comparator. In this case, it's defining that for a two given elements the minor one should be first.

Hence, in your code, if we extract all the elements the output will be the element ordered min to max:

while (!minHeap.empty()) { cout << minHeap.top() << " "; minHeap.pop(); } //output: 3,3,4,5,10,12

The algorithm to push an element is like a heap:

  1. Place the new element in the next available position in the array. (lower level of the tree)
  2. Compare the new element with its parent using the functor provided (comparator). In this case, you comparison is "if the new element is smaller", then swap it with its parent.
  3. Continue this process until either:
    • the new element’s parent is smaller than or equal to the new element, or
    • the new element reaches the root (index 0 of the array)

Maybe it is more clear to see how the algorithm works with a visual example: Imagine you have already pushed the numbers 6,3,5,9 and now you push 2. enter image description here

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

6 Comments

When I push 10, could you please tell me what the values of I and j would be?
Also could you tell me in which part of the code the parent of the current element is found/extracted for comparison?
As it is the first element no comparison will be made. You can check the trace of the functor by adding inside the function the line: std::cout << i << " " << j << std::endl
thank you for your answer. Could you also answer the other question?
When the function push is executed the comparison with the parent (step 2) is executed in a recursive like manner (step 3). To find the parent of a giving node there are various possibilities depending on how the structure is represented, the most common ones are: if represented with arrays have a math function that returns the parent idx or; if represented as a tree having a pointer to it.
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.