Heaps

`__gnu_pbds::priority_queue`

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

Template Parameters

T: Type of stored elements.
Compare: Type providing strict weak ordering comparison.
Tag: One of the five different heap types provided by __gnu_pbds. The default Tag is pairing_heap_tag. The five types are:
- pairing_heap_tag: Pairing heap. Official documentation suggests that pairing heap performs best with non‑primitive elements (e.g., custom structs, std::string, pair).
- binary_heap_tag: Binary heap. Official documentation suggests that binary heap performs best with primitive elements, but the author's tests did not show such good performance.
- binomial_heap_tag: Binomial heap. Binomial heap outperforms binary heap in merge operations, but its top‑element access has higher complexity than binary heap.
- rc_binomial_heap_tag: Redundant‑counter binomial heap.
- thin_heap_tag: A tag whose complexities are the same as Fibonacci heap except for merging.
Allocator: Memory allocator. Rarely used in OI, so not explained here.

Since this article is intended for competitive programming learners, only the first tag will be described in detail (member functions and usage), while the latter four will only have their complexities briefly mentioned.

Tests on the author's machine (Core i5 @3.1 GHz, macOS) on basic heap operations, combined with GNU's official complexity tests and Dijkstra tests, all indicate: At least for OIers, the other four tags besides pairing heap are either useless or have constants so large that they are worse than std's, and may even cause MLE. Therefore, only the default pairing heap is recommended here. Also, pairing heap outperforms make_heap() from the algorithm library.

Construction

The namespace must be specified because the class name conflicts with 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; usage will be explained in detail below.
id = q.push(1);

Member Functions

push(): Pushes an element into the heap, returns an iterator to its position.
pop(): Pops the top element.
top(): Returns the top element.
size(): Returns the number of elements.
empty(): Returns whether the heap is empty.
modify(point_iterator, const key): Modifies the key at the iterator's position to the given key and reorders the underlying storage.
erase(point_iterator): Erases the key‑value at the iterator's position from the heap.
join(__gnu_pbds::priority_queue &other): Merges other into *this and clears other.

The chosen tag determines the time complexity of each operation:

	push	pop	modify	erase	Join
`pairing_heap_tag`	\(O(1)\)	worst \(\Theta(n)\) amortized \(\Theta(\log(n))\)	worst \(\Theta(n)\) amortized \(\Theta(\log(n))\)	worst \(\Theta(n)\) amortized \(\Theta(\log(n))\)	\(O(1)\)
`binary_heap_tag`	worst \(\Theta(n)\) amortized \(\Theta(\log(n))\)	worst \(\Theta(n)\) amortized \(\Theta(\log(n))\)	\(\Theta(n)\)	\(\Theta(n)\)	\(\Theta(n)\)
`binomial_heap_tag`	worst \(\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 \(\Theta(n)\) amortized \(\Theta(\log(n))\)	worst \(\Theta(\log(n))\) amortized \(O(1)\)	worst \(\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;
// Since this article targets OIers, the commonly used heap : pairing_heap_tag is used as an example.
// For better readability, define a 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);
  // Heap elements: [1];
  for (int i = 2; i <= 5; i++) q1.push(i);
  // Heap elements: [1, 2, 3, 4, 5];
  std::cout << q1.top() << std::endl;
  // Output: 5;
  q1.pop();
  // Heap elements: [1, 2, 3, 4];
  id = q1.push(10);
  // Heap elements: [1, 2, 3, 4, 10];
  q1.modify(id, 1);
  // Heap elements: [1, 1, 2, 3, 4];
  std::cout << q1.top() << std::endl;
  // Output: 4;
  q1.pop();
  // Heap elements: [1, 1, 2, 3];
  id = q1.push(7);
  // Heap elements: [1, 1, 2, 3, 7];
  q1.erase(id);
  // Heap elements: [1, 1, 2, 3];
  q2.push(1), q2.push(3), q2.push(5);
  // q1 elements: [1, 1, 2, 3], q2 elements: [1, 3, 5];
  q2.join(q1);
  // q1 is empty, q2 elements: [1, 1, 1, 2, 3, 3, 5];
}

__gnu_pbds Iterator Invalidation Guarantee (invalidation_guarantee)

In the above example and in some practical uses (e.g., using the pb‑ds heap in this chapter to implement single‑source shortest path algorithms), it is often necessary to save and use heap iterators (such as __gnu_pbds::priority_queue<int>::point_iterator).

However, for different Tag parameters of __gnu_pbds::priority_queue, the underlying implementations differ, and the conditions for iterator invalidation also vary. According to the design of the __gnu_pbds library, there are three derived cases 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 modifying the container, point‑type iterators (point_iterator), pointers, and references (key/value) remain valid as long as the corresponding element has not been deleted from the container.
Range invalidation guarantee (range_invalidation_guarantee): After modifying the container, in addition to the property (2), any range‑type iterators (including the return values of begin() and end()) are correct. Tags with range invalidation guarantee are rb_tree_tag and splay_tree_tag (for __gnu_pbds::tree), and pat_trie_tag (for __gnu_pbds::trie).

Running the code below shows that except for binary_heap_tag, which has basic_invalidation_guarantee (iterators become invalid after modification), all others 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;
}

本页面最近更新：，更新历史
发现错误？想一起完善？在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用