C++ reverse a priority queue in place

Question

Hi I was wondering if given a std::priority_queue is there are a way to change the heap order from min heap to max heap and vice versa? And I'm not talking about defining a priority queue with greater, what I mean is we already have a priority_queue with some elements.

I would basically want to print elements in reversed order from priority queue while popping.

Now I'm aware that the elements could be loaded up to a stack for example, and then popped from it, that would change the order, but I would like to do it in-place, without using additional memory, or writing my own heap implementation for that matter.

Is there a way to do it?

Example:

std::priority_queue<int> pq{};

pq.push(1);
pq.push(2);
pq.push(3);

while(!pq.empty()){

   std::cout << pq.top();
   pq.pop(); //this would print 321, but I would simply like 123, reversed.
   //but don't change the declaration of the priority_queue. Reverse it when   it has its elements inside of it.

}

You can't do this in place. The order of the queue is set when you declare it and cannot be changed. — NathanOliver, Apr 25 '23 at 15:16
I don't mean changing the rules of it, I'm talking about popping it's elements — John_Cena, Apr 25 '23 at 15:16
Yes, it's possible. Maybe you show a [mcve], so SO users can offer a solution based on your code but not on your words. — 273K, Apr 25 '23 at 15:16
I don't see a compelling reason for making this harder than it needs to be. Declare the `priorirty_queue` with the ordering you actually want. — sweenish, Apr 25 '23 at 15:19
There is a reason in a specific problem I'm solving... I need to be able to pop the minimum element from the heap, but then after all the calculations are done on it I want to print elements from it from maximum to minimum. This can be achieved with stack, but I was wondering if it's possible without creating addtional memory, maybe move the priority queue or something. Is there no operation that would call heapify on all it's elements but with max heap rules for example? — John_Cena, Apr 25 '23 at 15:20
If that's the case, it sounds like you have the wrong data structure. — sweenish, Apr 25 '23 at 15:24
Yes, but I don't want to use multiset, because it's Red black tree, and binary heap just fits better. In theory if I was about to implement a binary heap on my own it would be possible, but doing that is an overkill... Unless You have better ideas.. — John_Cena, Apr 25 '23 at 15:25
std::priority_queue does not have API for this. Meaning it is impossible to do reliably. You need a feature that std::priority_queue doesn't support, ergo, use a different data structure. Red black tree may be complicated (depending on the flavour), but for example skip list is not. — freakish, Apr 25 '23 at 15:28
double ended priority queue sounds badass but is there a stl thing for it? — John_Cena, Apr 25 '23 at 15:46
https://stackoverflow.com/questions/29289974/what-does-the-operator-do — jxh, Apr 25 '23 at 16:58

score 3 · Accepted Answer · edited Apr 25 '23 at 15:46

3

You have tagged the question with heap. This a great hint, why don't use it instead of the priority queue?

std::vector<int> pq{};

pq.push_back(1);
pq.push_back(2);
pq.push_back(3);

// possibly first sort order
std::make_heap(pq.begin(), pq.end(), std::less<>{});

// ...

// Reorder
std::make_heap(pq.begin(), pq.end(), std::greater<>{});

while(!pq.empty()) {
  std::pop_heap(pq.begin(), pq.end(), std::greater<>{});
  std::cout << pq.back();
  pq.pop_back();
  // The loop will print 123
}

You can change a compare function in a heap with remaking it at any time.

edited Apr 25 '23 at 15:46

bitmask

32,434
14
99
159

answered Apr 25 '23 at 15:39

273K

29,503
10
41
64

Will this heapify in place? the make_heap function Well the reason would be that I wouldl have to make_heap everytime I insert a new element, because after inserting a new element I'm removing (popping) smallest one. and that repeats in a loop – John_Cena Apr 25 '23 at 15:49
2

Yes, of course, it works with a container elements. – 273K Apr 25 '23 at 15:51
2

No, you call make_heap only once with a dirty container. You call push_heap on each new element inserted with container's push_back. – 273K Apr 25 '23 at 15:53
1

@John_Cena If you need to reverse the heap order every time you interact with it, both heap and priority_queue are the wrong data structures. Consider `std::set` or a sorted `std::deque`. – bitmask Apr 25 '23 at 15:55
Okey, so If i have a heap that was made with std::make_heap as pq, at any point of time i can push an element like to priority queue and at any point of time I can heapify all it's contents in place with make_heap? What is the catch here? Why isn't this used instead of priority queue if it has more functionalities? Why am i hearing about this for the first time? – John_Cena Apr 25 '23 at 15:56
Not everytime, just once. But after it worked as min heap for a while for example. then turn it into max heap, but in place. – John_Cena Apr 25 '23 at 15:56
@John_Cena: `std::priority_queue` is just a wrapper around the `std::heap` apis to enforce that they're correctly used. The advantage is that you can't access the underlying `std::vector`, and therefore can't invalidate the heap. – Mooing Duck Apr 25 '23 at 15:59
1

@273K: `std::make_heap` changed in C++20, but has always existed since C++98 too. – Mooing Duck Apr 25 '23 at 15:59
@John_Cena: Yes. Exactly like `std::vector` is simply a wrapper around `new T[]`. – Mooing Duck Apr 25 '23 at 16:00
Does that mean all of you described here can be used with C++17? That's kind of what I'm limited to unfortunately. – John_Cena Apr 25 '23 at 16:00
1

Yes, what's described here works in every official version of C++, ever. – Mooing Duck Apr 25 '23 at 16:00
I mean make_heap, is it in c++17, because 273K said it's new algorithm since C++20 – John_Cena Apr 25 '23 at 16:01
1

@MooingDuck Thanks. I've confused it with ranges::make_heap manual. – 273K Apr 25 '23 at 16:04
1

@John_Cena: `ranges::make_heap` is new. `std::make_heap` is old. https://en.cppreference.com/w/cpp/algorithm/make_heap – Mooing Duck Apr 25 '23 at 16:05
Actually as I used it now, std::less<>{} will make a max heap, lol. weird – John_Cena Apr 25 '23 at 16:24

C++ reverse a priority queue in place

1 Answers1