STLs 2

Priority Queue

A priority queue is like a heap. By default, it’s a max-heap (the largest element is always at the top).

priority_queue<int> pq; // Max-heap

pq.push(10);
pq.push(30);
pq.push(20);

cout << pq.top(); // 30
pq.pop(); // Remove 30
cout << pq.top(); // 20

Min-Heap

To make it a min-heap:

priority_queue<int, vector<int>, greater<int>> pq; // Min-heap

Deque (Double-Ended Queue)

A deque allows insertion and deletion from both ends in

O(1)

deque<int> dq;
dq.push_back(10);
dq.push_front(20);

cout << dq.front(); // 20
cout << dq.back(); // 10

dq.pop_front();
dq.pop_back();

Lower Bound and Upper Bound

Very useful for binary search on sorted containers.

lower_bound: Returns an iterator to the first element $\ge$ value.
upper_bound: Returns an iterator to the first element $>$ value.

vector<int> v = {1, 3, 3, 5, 7};
auto it1 = lower_bound(v.begin(), v.end(), 3); // points to first 3
auto it2 = upper_bound(v.begin(), v.end(), 3); // points to 5

Custom Sorting with STL

You can use std::sort with custom comparators or use std::greater<T>().

sort(v.begin(), v.end(), greater<int>()); // Sort descending

Practice

Sheet 6: STLs 2

Practice problems for this tutorial.

Level 0 Training

Practice Sheets

Priority Queue

Min-Heap

Deque (Double-Ended Queue)

Lower Bound and Upper Bound

Custom Sorting with STL

Practice

Sheet 6: STLs 2

​Priority Queue

​Min-Heap

​Deque (Double-Ended Queue)

​Lower Bound and Upper Bound

​Custom Sorting with STL

​Practice

Sheet 6: STLs 2

Priority Queue

Min-Heap

Deque (Double-Ended Queue)

Lower Bound and Upper Bound

Custom Sorting with STL

Practice