Priority queue in python and C++

Priority queue is an important data structure as it has the O(1) time complexity to get the maximum (max heap)or minimum value (min heap). There is some slightly different between Python and C++ commonly used implementations. In this article, I’d like to have a quick comparison.

Python priority queue

By default python is a min heap.

import heapq
pq = [1, 4, 0, 5, 6]
heapq.heapify(pq)
for item in pq:print(item)

The above simple code can output the following: The first one is the minimum value.

0
4
1
5
6

C++ priority queue

Code 1: does not work

By default it is Max heap. We can change it to min heap by changing the default Compare from less to greater [1].

// This code is NOT working.
#include <vector>
#include <queue>
#include <iostream>
int main(){
    const std::vector<int> data{1, 4, 0, 5, 6};
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq(data.begin(), data.end());
    // This line has problem.
    for (auto item : pq) std::cout << item << std::endl;
    std::cout << std::endl;
    return 0;
}

The above code has problem and will get the following error

hq_test.cpp:7:20: error: invalid range expression of type 'std::__1::priority_queue<int, std::__1::vector<int, std::__1::allocator<int> >,
std::__1::greater<int> >'; no viable 'begin' function available
for (auto item : pq) std::cout << item << std::endl;
^ ~~
/Library/Developer/CommandLineTools/usr/bin/../include/c++/v1/initializer_list:99:1: note: candidate template ignored: could not match
'initializer_list' against 'priority_queue'
begin(initializer_list<_Ep> __il) _NOEXCEPT
^
/Library/Developer/CommandLineTools/usr/bin/../include/c++/v1/iterator:1753:1: note: candidate template ignored: could not match '_Tp [_Np]' against
'std::__1::priority_queue<int, std::__1::vector<int, std::__1::allocator<int> >, std::__1::greater<int> >'
begin(_Tp (&__array)[_Np])
^
/Library/Developer/CommandLineTools/usr/bin/../include/c++/v1/iterator:1771:1: note: candidate template ignored: substitution failure [with _Cp =
std::__1::priority_queue<int, std::__1::vector<int, std::__1::allocator<int> >, std::__1::greater<int> >]: no member named 'begin' in
'std::__1::priority_queue<int, std::__1::vector<int, std::__1::allocator<int> >, std::__1::greater<int> >'
begin(_Cp& __c) -> decltype(__c.begin())
^                               ~~~~~
/Library/Developer/CommandLineTools/usr/bin/../include/c++/v1/iterator:1779:1: note: candidate template ignored: substitution failure [with _Cp =
std::__1::priority_queue<int, std::__1::vector<int, std::__1::allocator<int> >, std::__1::greater<int> >]: no member named 'begin' in
'std::__1::priority_queue<int, std::__1::vector<int, std::__1::allocator<int> >, std::__1::greater<int> >'
begin(const _Cp& __c) -> decltype(__c.begin())

Yes, from the error message, we know that the priority_queue does not have the begin() function which makes the range not working. If you want to know why, pls read this article.

Code 2: does work

The code

#include <vector>
#include <queue>
#include <iostream>
int main(){
    const std::vector<int> data{1, 4, 0, 5, 6};
    std::priority_queue<int, std::vector<int>, std::greater<int>> pq(data.begin(), data.end());
    while (!pq.empty()){
        std::cout << pq.top() << std::endl;
        pq.pop();
    }
    return 0;
}

The output

0
1
4
5
6

Reference

[1] https://en.cppreference.com/w/cpp/container/priority_queue