Algorithm and Data Structure Class Header Collection

November 12, 2023 by Yohandi

Unlike the previous blogs, this space is dedicated purely to my algorithm and data structure class headers. This ongoing project is an extension of my old archive, which can be found here. Pretty much I will keep updating both the old archive and this showcase every time I make a new class header.

Dijkstra

An implemented Dijkstra's algorithm in the form of a class. This class is designed with the intention of simplicity for its user when constructing a Dijkstra's algorithm

The class is recommended for C++11 or later.

Constructor

Syntax	Complexity	Description
$Dijkstra ()$	$O (1)$	Initializes a new empty graph of size $0$ .
$Dijkstra (n)$	$O (n)$	Initializes a new empty graph of size $n$ .

Methods

Syntax	Complexity	Description
$addEdge (u, v, w)$	$O (1)$	Adds an edge between node $u$ and $v$ with a weight $w$ .
$distance (source)$	$O (V + E lo g V)$	Returns a vector of distances between the $source$ and all nodes.
$getInfinite ()$	$O (1)$	Returns the infinite value.
$getZero ()$	$O (1)$	Returns the zero value.
$resize (n)$	$O (n)$	Resizes the current graph size to $n$ .
$setInfinite (val)$	$O (1)$	Sets an infinite value.
$setZero (val)$	$O (1)$	Sets a zero value.
$size ()$	$O (1)$	Returns the number of nodes in class.

dijkstra.hpp:

#ifndef DIJKSTRA_HPP
#define DIJKSTRA_HPP

#include <assert.h>

...

demo.cpp:

// Problem link: https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_1_A

#include <assert.h>

#include <iostream>
...

Disjoint-Set Data Structure

An implemented Disjoint-set data structure in the form of a class. This class is designed with the intention of simplicity for its user when constructing the data structure.

The class is recommended for C++11 or later.

Constructor

Syntax	Complexity	Description
$DSU()$	$O (1)$	Initializes a new disjoint-set data structure of size $0$ .
$DSU(n)$	$O (n)$	Initializes a new disjoint-set data structure of size $n$ .

Methods

Syntax	Complexity	Description
$connectedNodes(x)$	$O (n)$	Returns a vector of nodes that are connected to node $x$ (excluding the node $x$ itself).
$find(x)$	$O (lo g n)$	Returns the representation of the group where node $x$ belongs.
$isConnected(u, v)$	$O (lo g n)$	Returns a boolean value indicating the connectivity between node $u$ and $v$ .
$merge(u, v)$	$O (lo g n)$	Merges groups where node $u$ and $v$ respectively belong and returns the representation.
$resize(n)$	$O (n)$	Resizes the current data structure size to $n$ ( $n$ should be larger than the current size).
$setParent(u, v)$	$O (1)$	Sets node $u$ as the parent of node $v$ .
$size()$	$O (1)$	Returns the size of the data structure.
$size(x)$	$O (lo g n)$	Returns the number of nodes that are connected to node $x$ (including the node $x$ itself).

dsu.hpp:

#ifndef DSU_HPP
#define DSU_HPP

#include <assert.h>

...

demo.cpp:

#include <iostream>

#include "dsu.hpp"

using namespace std;
...

Fenwick Tree

An implemented Fenwick tree data structure in the form of a class. This class is designed with the intention of simplicity for its user when constructing the data structure.

The class is recommended for C++11 or later.

Constructor

Syntax	Complexity	Description
$FenwickTree()$	$O (1)$	Initializes a new fenwick tree data structure of size $0$ .
$FenwickTree(n)$	$O (n)$	Initializes a new fenwick tree data structure of size $n$ .

Methods

Syntax	Complexity	Description
$add (index, val)$	$O (lo g n)$	Adds $val$ to $arr_{in d e x}$ .
$clear ()$	$O (n)$	Clears the current data structure.
$getZero ()$	$O (1)$	Returns the zero value.
$resize (n)$	$O (n)$	Resizes the current data structure size to $n$ .
$setZero (val)$	$O (1)$	Sets a zero value.
$size ()$	$O (1)$	Returns the size of data structure.
$sum (left, right)$	$O (lo g n)$	Returns a sum of $arr_{left} + arr_{left + 1} + \dots + arr_{right - 1}$

fenwick_tree.hpp:

#ifndef FENWICK_TREE_HPP
#define FENWICK_TREE_HPP

#include <assert.h>

...

demo.cpp:

#include <iostream>

#include "fenwick_tree.hpp"
using namespace std;

...

Sparse Table

An implemented sparse table data structure in the form of a class. This class is designed with the intention of simplicity for its user when constructing the data structure.

The class is recommended for C++11 or later.

Constructor

Syntax	Complexity	Description
$SparseTable (v)$	$O (n lo g n)$	Initializes a new sparse table data structure from the given vector $v$ .

Methods

Syntax	Complexity	Description
$query (left, right)$	$O (1)$	Returns $func (v_{left}, v_{left + 1}, \dots, v_{right - 1}$ )

sparse_table.hpp:

#ifndef SPARSE_TABLE_HPP
#define SPARSE_TABLE_HPP

#include <assert.h>
#include <math.h>
...

demo.cpp:

#include <iostream>

#include "sparse_table.hpp"

using namespace std;
...

← Natural Parallelism: The Paradigm of Refined Matrix Multiplication Natural Parallelism: Scalable Techniques in Distributed and Parallel Sorting Algorithms →