C++ Heaps Pairs Sorting

default priority queue

max heap

declare max heap

priority_queue<int> pq;

declare min heap

priority_queue<int, vector<int>, greater<int>> pq;

push heap

pq.push(x);

top heap

pq.top();

pop heap

pq.pop();

heap push time

O(log n)

heap pop time

O(log n)

declare pair

pair<int, int> p;

create pair

{a, b} or make_pair(a, b)

access pair first

p.first

access pair second

p.second

declare vector of pairs

vector<pair<int, int>> v;

sort pairs default

sort(v.begin(), v.end());

sort by second value

sort(v.begin(), v.end(), [](auto& a, auto& b){ return a.second < b.second; });

sort descending custom

sort(v.begin(), v.end(), [](auto& a, auto& b){ return a > b; });

binary search function

binary_search(v.begin(), v.end(), x)

lower bound meaning

first element not less than x

upper bound meaning

first element greater than x

lower bound code

lower_bound(v.begin(), v.end(), x)

upper bound code

upper_bound(v.begin(), v.end(), x)

get index from iterator

it - v.begin()

include everything

#include <bits/stdc++.h>

standard namespace

using namespace std;