Skip to content

Instantly share code, notes, and snippets.

@Naetmul

Naetmul/algorithms.cpp

Last active November 12, 2025 17:33
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Naetmul/1befc68b8cfeb4549dc7d2465c1dc281 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Naetmul/1befc68b8cfeb4549dc7d2465c1dc281 to your computer and use it in GitHub Desktop.
Download ZIP
C++ Algorithms
Raw
algorithms.cpp
template<typename T>
void swap(T& a, T& b) {
T t = static_cast<T&&>(a);
a = static_cast<T&&>(b);
b = static_cast<T&&>(t);
}
template<typename T>
void quicksort(T* a, int left, int right) {
if (left >= right) return;
T pivot = a[(left + right) / 2];
int i = left;
int j = right;
while (i <= j) {
while (a[i] < pivot) i++;
while (a[j] > pivot) j--;
if (i <= j) {
swap(a[i], a[j]);
i++;
j--;
}
}
quicksort(a, left, j);
quicksort(a, i, right);
}
template<typename T>
class Vector {
T* data;
unsigned n, cap;
void grow(unsigned m) {
if (m <= cap) return;
unsigned newCap = cap ? cap : 1;
while (newCap < m) newCap <<= 1;
T* p = new T[newCap];
for (unsigned i = 0; i < n; i++) {
// move-assign if T has a move assignment; otherwise falls back to copy
p[i] = static_cast<T&&>(data[i]);
}
delete[] data;
data = p;
cap = newCap;
}
public:
Vector() : data(nullptr), n(0), cap(0) {}
~Vector() { delete[] data; }
Vector(const Vector&) = delete;
Vector& operator=(const Vector&) = delete;
void pushBack(const T& v) {
grow(n + 1);
data[n++] = v;
}
void popBack() {
if (n) n--;
}
T& operator[](unsigned i) { return data[i]; }
unsigned size() const { return n; }
void reserve(unsigned m) { grow(m); }
};
// Max-heap
template<typename T>
class Heap {
Vector<T> v; // v[0] is dummy
void siftUp(unsigned i) {
while (i > 1) {
unsigned p = i >> 1;
if (v[p] >= v[i]) break;
swap(v[p], v[i]);
i = p;
}
}
void siftDown(unsigned i) {
unsigned n = v.size() - 1; // last valid index
for (;;) {
unsigned l = i << 1;
unsigned r = l + 1;
unsigned b = i;
if (l <= n && v[b] < v[l]) b = l;
if (r <= n && v[b] < v[r]) b = r;
if (b == i) break;
swap(v[i], v[b]);
i = b;
}
}
public:
Heap() { v.pushBack(T()); } // put dummy at index 0
void push(const T& x) {
v.pushBack(x);
siftUp(v.size() - 1);
}
void pop() {
unsigned n = v.size() - 1;
if (!n) return;
v[1] = static_cast<T&&>(v[n]);
v.popBack();
if (n > 1) siftDown(1);
}
T& top() { return v[1]; }
bool empty() const { return v.size() == 1; }
unsigned size() const { return v.size() - 1; }
};
template<typename T>
class Stack {
Vector<T> v;
public:
void push(const T& x) { v.pushBack(x); }
void pop() { v.popBack(); }
T& top() { return v[v.size() - 1]; }
bool empty() const { return v.size() == 0; }
unsigned size() const { return v.size(); }
};
template<typename T>
class Queue {
Vector<T> in, out; // two-stack queue
void refillOut() {
// Move all items from 'in' to 'out' (reverses order)
while (!in.empty()) {
T x = static_cast<T&&>(in[in.size() - 1]);
in.popBack();
out.pushBack(x);
}
}
public:
void push(const T& x) { in.pushBack(x); } // enqueue
void pop() { // dequeue
if (out.empty()) refillOut();
if (!out.empty()) out.popBack();
}
T& front() { // peek front
if (out.empty()) refillOut();
return out[out.size() - 1];
}
T& back() { // optional: last pushed
if (!in.empty()) return in[in.size() - 1];
// if 'in' is empty, the newest is at bottom of 'out'
return out[0];
}
bool empty() const { return in.size() + out.size() == 0; }
unsigned size() const { return in.size() + out.size(); }
};
// ---------------- global RNG (xorshift32) ----------------
unsigned rng() {
static unsigned s = 2463534242u;
s ^= s << 13;
s ^= s >> 17;
s ^= s << 5;
if (!s) s = 2463534242u;
return s;
}
template<typename K>
class TreapRotate {
struct Node {
K key;
unsigned pri;
Node* l, * r;
Node(const K& k, unsigned p) : key(k), pri(p), l(nullptr), r(nullptr) {}
};
Node* root;
static void rotate_left(Node*& t) {
// t is updated to point to new root of subtree after rotation (r)
// t R
// A R -> t F
// . . E F A E
// . .
Node* R = t->r;
t->r = R->l;
R->l = t;
t = R;
}
static void rotate_right(Node*& t) {
// t is updated to point to new root of subtree after rotation (l)
// t L
// L B -> C t
// C D . . D B
// . .
Node* L = t->l;
t->l = L->r;
L->r = t;
t = L;
}
static void insert(Node*& t, const K& k) {
if (!t) { t = new Node(k, rng()); return; }
if (k < t->key) {
insert(t->l, k);
if (t->l && t->l->pri > t->pri) rotate_right(t);
} else if (t->key < k) {
insert(t->r, k);
if (t->r && t->r->pri > t->pri) rotate_left(t);
} else {
// duplicate key: do nothing (or update payload if you add one)
}
}
static void erase(Node*& t, const K& k) {
if (!t) return;
if (k < t->key) {
erase(t->l, k);
} else if (t->key < k) {
erase(t->r, k);
} else {
// found
if (!t->l) {
Node* q = t;
t = t->r;
delete q;
} else if (!t->r) {
Node* q = t;
t = t->l;
delete q;
} else {
// rotate the higher-priority child up, then continue
if (t->l->pri > t->r->pri) {
rotate_right(t); // t now points to what was t->l
erase(t, k);
} else {
rotate_left(t); // t now points to what was t->r
erase(t, k);
}
}
}
}
static bool contains(Node* t, const K& k) {
while (t) {
if (k < t->key) t = t->l;
else if (t->key < k) t = t->r;
else return true;
}
return false;
}
// returns pointer to first key >= k; nullptr if none
static Node* lower_bound(Node* t, const K& k) {
Node* ans = nullptr;
while (t) {
if (!(t->key < k)) {
ans = t;
t = t->l;
} else t = t->r;
}
return ans;
}
static void clear(Node* t) {
if (!t) return;
clear(t->l);
clear(t->r);
delete t;
}
public:
TreapRotate() : root(nullptr) {}
~TreapRotate() { clear(root); }
void insert(const K& k) { insert(root, k); }
void erase(const K& k) { erase(root, k); }
bool contains(const K& k) const { return contains(root, k); }
// PRE: there exists an element >= k
const K& lower_bound(const K& k) const {
Node* n = lower_bound(root, k);
return n->key; // UB if no such element; check with hasLowerBound() if you want
}
bool hasLowerBound(const K& k) const {
return lower_bound(root, k) != nullptr;
}
bool empty() const { return root == nullptr; }
};
template<typename K>
class TreapSplit {
struct Node {
K key;
unsigned pri;
Node *l, *r;
Node(const K& k, unsigned p) : key(k), pri(p), l(nullptr), r(nullptr) {}
};
struct Split { Node* less; Node* equal; Node* greater; };
Node* root;
// merge two treaps
// PRE: all keys in 'a' < all keys in 'b'
// returns new root
static Node* merge(Node* a, Node* b) {
if (!a) return b;
if (!b) return a;
if (a->pri > b->pri) {
a->r = merge(a->r, b);
return a;
} else {
b->l = merge(a, b->l);
return b;
}
}
// split into: less(<key), equal(==key or null), greater(>key)
static Split split3(Node* t, const K& key) {
if (!t) return {nullptr, nullptr, nullptr};
if (t->key < key) {
Split s = split3(t->r, key);
t->r = s.less; // keep <key on the right
return {t, s.equal, s.greater};
} else if (key < t->key) {
Split s = split3(t->l, key);
t->l = s.greater; // keep >key on the left
return {s.less, s.equal, t};
} else {
Node* L = t->l;
Node* R = t->r;
t->l = t->r = nullptr;
return {L, t, R};
}
}
static bool contains(Node* t, const K& k) {
while (t) {
if (k < t->key) t = t->l;
else if (t->key < k) t = t->r;
else return true;
}
return false;
}
static Node* lower_bound_node(Node* t, const K& k) {
Node* ans = nullptr;
while (t) {
if (!(t->key < k)) {
ans = t;
t = t->l;
} else {
t = t->r;
}
}
return ans;
}
static void clear(Node* t) {
if (!t) return;
clear(t->l);
clear(t->r);
delete t;
}
public:
TreapSplit() : root(nullptr) {}
~TreapSplit() { clear(root); }
void insert(const K& x) {
Split s = split3(root, x);
if (!s.equal) s.equal = new Node(x, rng());
root = merge(merge(s.less, s.equal), s.greater);
}
void erase(const K& x) {
Split s = split3(root, x);
if (s.equal) {
delete s.equal;
s.equal = nullptr;
}
root = merge(s.less, s.greater);
}
bool contains(const K& x) const { return contains(root, x); }
// PRE: only deref return of lower_bound() if hasLowerBound(k) is true
const K& lower_bound(const K& k) const {
Node* n = lower_bound_node(root, k);
return n->key;
}
bool hasLowerBound(const K& k) const { return lower_bound_node(root, k) != nullptr; }
bool empty() const { return root == nullptr; }
};
class UnionFind {
unsigned *par, *sz;
unsigned n;
public:
UnionFind(unsigned m) : n(m) {
par = new unsigned[n];
sz = new unsigned[n];
for (unsigned i = 0; i < n; i++) {
par[i] = i;
sz[i] = 1;
}
}
~UnionFind() {
delete[] par;
delete[] sz;
}
unsigned find(unsigned x) {
while (x != par[x]) {
par[x] = par[par[x]];
x = par[x];
}
return x;
}
bool unite(unsigned a, unsigned b) {
a = find(a);
b = find(b);
if (a == b) return false;
if (sz[a] < sz[b]) { // swap so a is bigger
swap(a, b);
}
// Assert: sz[a] >= sz[b]
// Attach b to a in order to keep tree shallow
par[b] = a;
sz[a] += sz[b];
return true;
}
bool connected(unsigned a, unsigned b) {
return find(a) == find(b);
}
unsigned size(unsigned x) {
return sz[find(x)];
}
};
int main() {
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment