AIOJ

`__gnu_pbds::priority_queue`

Appendix: Official documentation—complexity and constant-factor tests

#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
__gnu_pbds::priority_queue<T, Compare, Tag, Allocator>

Template Parameters

T: The type of the stored elements
Compare: A type providing strict weak ordering
Tag: One of the five different heaps provided by __gnu_pbds. The Tag parameter defaults to pairing_heap_tag. The five tags are:
- pairing_heap_tag: Pairing heap
  The official documentation considers pairing heaps to perform best for non-native elements (such as custom structs/std::string/pair).
- binary_heap_tag: Binary heap
  The official documentation considers binary heaps to perform best for native elements, although the author's tests did not show such good performance.
- binomial_heap_tag: Binomial heap
  A binomial heap performs better than a binary heap for merge operations, but its complexity for retrieving the top element is higher than that of a binary heap.
- rc_binomial_heap_tag: Redundant-counter binomial heap
- thin_heap_tag: A tag whose complexities are the same as those of a Fibonacci heap except for merging
Allocator: The allocator. Since it rarely occurs in OI, it is not explained here.

Since this article is intended only for students learning algorithm competitions, the last four tags will only receive a brief introduction to their complexities, while the first will have its member functions and usage introduced.

Tests of the heap's basic operations on the author's local Core i5 @3.1 GHz Mac, combined with GNU's official complexity tests and Dijkstra tests, all show that: At least for OIers, the four tags other than the pairing heap are useless: either they are of no use, or their constants are so large that they are worse than std, and they may cause MLE. Therefore, only the default pairing heap is recommended here. Similarly, pairing heaps are also better than make_heap() in the algorithm library.

Construction

The namespace must be specified because its class name is the same as one in std.

// __gnu_pbds::priority_queue<int>;
// __gnu_pbds::priority_queue<int, greater<int>>;
// __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag>;
__gnu_pbds::priority_queue<int>::point_iterator id;  // point-type iterator
// Both modify and push return a point_iterator; the usage is described in detail below.
id = q.push(1);

Member Functions

push(): Push an element into the heap and return an iterator to the position of that element.
pop(): Pop the top element from the heap.
top(): Return the top element of the heap.
size(): Return the number of elements.
empty(): Return whether the heap is non-empty.
modify(point_iterator, const key): Change the key at the iterator's position to the passed key and sort the underlying storage structure.
erase(point_iterator): Erase the key at the iterator's position from the heap.
join(__gnu_pbds::priority_queue &other): Merge other into *this and clear other.

The time complexity of each operation is determined by the tag used:

	push	pop	modify	erase	Join
`pairing_heap_tag`	$O(1)$	worst-case $\Theta(n)$ amortized $\Theta(\log(n))$	worst-case $\Theta(n)$ amortized $\Theta(\log(n))$	worst-case $\Theta(n)$ amortized $\Theta(\log(n))$	$O(1)$
`binary_heap_tag`	worst-case $\Theta(n)$ amortized $\Theta(\log(n))$	worst-case $\Theta(n)$ amortized $\Theta(\log(n))$	$\Theta(n)$	$\Theta(n)$	$\Theta(n)$
`binomial_heap_tag`	worst-case $\Theta(\log(n))$ amortized $O(1)$	$\Theta(\log(n))$	$\Theta(\log(n))$	$\Theta(\log(n))$	$\Theta(\log(n))$
`rc_binomial_heap_tag`	$O(1)$	$\Theta(\log(n))$	$\Theta(\log(n))$	$\Theta(\log(n))$	$\Theta(\log(n))$
`thin_heap_tag`	$O(1)$	worst-case $\Theta(n)$ amortized $\Theta(\log(n))$	worst-case $\Theta(\log(n))$ amortized $O(1)$	worst-case $\Theta(n)$ amortized $\Theta(\log(n))$	$\Theta(n)$

Example

#include <algorithm>
#include <cstdio>
#include <ext/pb_ds/priority_queue.hpp>
#include <iostream>
using namespace __gnu_pbds;
// For OIers, this article uses the commonly used pairing_heap_tag as an example.
// For better readability, define the macro as follows:
using pair_heap = __gnu_pbds::priority_queue<int>;
pair_heap q1;  // max-heap, pairing heap
pair_heap q2;
pair_heap::point_iterator id;  // an iterator

int main() {
  id = q1.push(1);
  // Elements in the heap: [1];
  for (int i = 2; i <= 5; i++) q1.push(i);
  // Elements in the heap: [1, 2, 3, 4, 5];
  std::cout << q1.top() << std::endl;
  // Output: 5;
  q1.pop();
  // Elements in the heap: [1, 2, 3, 4];
  id = q1.push(10);
  // Elements in the heap: [1, 2, 3, 4, 10];
  q1.modify(id, 1);
  // Elements in the heap: [1, 1, 2, 3, 4];
  std::cout << q1.top() << std::endl;
  // Output: 4;
  q1.pop();
  // Elements in the heap: [1, 1, 2, 3];
  id = q1.push(7);
  // Elements in the heap: [1, 1, 2, 3, 7];
  q1.erase(id);
  // Elements in the heap: [1, 1, 2, 3];
  q2.push(1), q2.push(3), q2.push(5);
  // Elements in q1: [1, 1, 2, 3], elements in q2: [1, 3, 5];
  q2.join(q1);
  // q1 is empty; elements in q2: [1, 1, 1, 2, 3, 3, 5];
}

Invalidation Guarantee of __gnu_pbds Iterators

In the example above and some practical applications (such as using the pb-ds heap in this chapter to write a single-source shortest-path algorithm), it is often necessary to save and use heap iterators (such as __gnu_pbds::priority_queue<int>::point_iterator).

However, for example, the underlying implementations of different Tag parameters in __gnu_pbds::priority_queue are not the same, and their iterator invalidation conditions also differ. According to the design of the __gnu_pbds library, there are the following three cases, derived from top to bottom:

Basic invalidation guarantee (basic_invalidation_guarantee): when the container is not modified, point-type iterators (point_iterator), pointers, and references (key/value) remain valid.
Point invalidation guarantee (point_invalidation_guarantee): after the container is modified, point-type iterators (point_iterator), pointers, and references (key/value) remain valid as long as the corresponding elements have not been deleted from the container.
Range invalidation guarantee (range_invalidation_guarantee): after the container is modified, in addition to the properties in (2), any range-type iterator (including the return values of begin() and end()) is correct. Tags with the range invalidation guarantee include rb_tree_tag, splay_tree_tag for __gnu_pbds::tree, and pat_trie_tag for __gnu_pbds::trie.

As can be seen from running the code below, binary_heap_tag has basic_invalidation_guarantee and its iterators are invalidated after modification, while all the other tags have point_invalidation_guarantee, satisfying the requirement that point-type iterators (point_iterator) remain valid after modification.

#include <iostream>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
#include <cxxabi.h>

template <typename T>
void print_invalidation_guarantee() {
  using gute = __gnu_pbds::container_traits<T>::invalidation_guarantee;
  cout << abi::__cxa_demangle(typeid(gute).name(), 0, 0, 0) << endl;
}

int main() {
  using pairing =
      __gnu_pbds::priority_queue<int, greater<int>, pairing_heap_tag>;
  using binary = __gnu_pbds::priority_queue<int, greater<int>, binary_heap_tag>;
  using binomial =
      __gnu_pbds::priority_queue<int, greater<int>, binomial_heap_tag>;
  using rc_binomial =
      __gnu_pbds::priority_queue<int, greater<int>, rc_binomial_heap_tag>;
  using thin = __gnu_pbds::priority_queue<int, greater<int>, thin_heap_tag>;
  print_invalidation_guarantee<pairing>();
  print_invalidation_guarantee<binary>();
  print_invalidation_guarantee<binomial>();
  print_invalidation_guarantee<rc_binomial>();
  print_invalidation_guarantee<thin>();
  return 0;
}

Heap

__gnu_pbds::priority_queue