complex-data-structures
v0.0.1
Published
Useful snippets of complex data structures for algorithm contests
Downloads
1
Readme
Complex Data Structure Snippet
Useful snippets of complex data structures for algorithm contests
- 🔋 Battery-included
- 🗜 Minified with Terser
- 🛠 Super Flexible (but not fastest)
- ⛑ Well Tested
Usage
Copy and paste into the editor.
Priority Queue
class PriorityQueue {
constructor(t) {
(this.tree = []), (this.compare = t);
}
get length() {
return this.tree.length;
}
get head() {
return this.tree.length > 0 ? this.tree[0] : void 0;
}
pop() {
if (this.length <= 1) return this.tree.shift();
const t = this.head;
this.tree[0] = this.tree.pop();
let e = 0;
for (; e < this.tree.length; ) {
const t = 2 * e + 1,
r = 2 * e + 2;
let h = e;
if (
(t < this.tree.length &&
this.compare(this.tree[t], this.tree[h]) < 0 &&
(h = t),
r < this.tree.length &&
this.compare(this.tree[r], this.tree[h]) < 0 &&
(h = r),
e === h)
)
break;
([this.tree[e], this.tree[h]] = [this.tree[h], this.tree[e]]), (e = h);
}
return t;
}
push(t) {
this.tree.push(t);
let e = this.tree.length - 1;
for (; e > 0; ) {
const t = (e - 1) >> 1;
if (this.compare(this.tree[e], this.tree[t]) >= 0) break;
([this.tree[e], this.tree[t]] = [this.tree[t], this.tree[e]]), (e = t);
}
}
}Segment Tree
class SegmentTree {
constructor(t, e, h) {
if (0 === t.length)
throw new Error("values' length must be greater than 0.");
const s = 2 ** Math.ceil(Math.log2(t.length)) * 2 - 1,
r = [];
for (let h = 0; h <= s >> 1; ++h) r[(s >> 1) + h] = h < t.length ? t[h] : e;
for (let t = (s >> 1) - 1; t >= 0; --t)
r[t] = h(r[2 * t + 1], r[2 * t + 2]);
(this.valueLength = t.length),
(this.identity = e),
(this.associate = h),
(this.tree = r);
}
get length() {
return this.valueLength;
}
getAt(t) {
return this.tree[t + (this.tree.length >> 1)];
}
queryIn(t, e) {
let h = this.identity;
const s = [[0, 0, 1 + (this.tree.length >> 1)]];
for (; s.length > 0; ) {
const [r, i, n] = s.pop();
i >= t && n <= e
? (h = this.associate(h, this.tree[r]))
: i >= e ||
n < t ||
r > this.tree.length >> 1 ||
s.push([2 * r + 1, i, (i + n) >> 1], [2 * r + 2, (i + n) >> 1, n]);
}
return h;
}
setAt(t, e) {
const h = t + (this.tree.length >> 1);
this.tree[h] = e;
let s = (h - 1) >> 1;
for (; s >= 0; )
(this.tree[s] = this.associate(
this.tree[2 * s + 1],
this.tree[2 * s + 2]
)),
(s = (s - 1) >> 1);
}
}Union Find / Disjoint Set
class UnionFind {
constructor(e, t = 0) {
this.nodes = [];
for (let s = 0; s < e; ++s) {
const e = { size: 1 };
(e.parent = e), (this.nodes[s + t] = e);
}
}
get length() {
return this.nodes.reduce((e, t) => (t.parent === t ? e + 1 : e), 0);
}
isUnited(e, t) {
return (
this.getRepresentative(this.nodes[e]) ===
this.getRepresentative(this.nodes[t])
);
}
unite(e, t) {
const s = this.getRepresentative(this.nodes[e]),
n = this.getRepresentative(this.nodes[t]);
let i, r;
s.size >= n.size ? ((i = s), (r = n)) : ((i = n), (r = s)),
(r.parent = i),
(i.size += r.size),
(r.size = 1);
}
getRepresentative(e) {
return e.parent === e
? e
: ((e.parent = this.getRepresentative(e.parent)), e.parent);
}
}API
new PriorityQueue(values, compare)
Creates a priority queue from values.
compare is a function to specify priority comparison strategy. It is used the exact same way with Array#sort().
// 1046. Last Stone Weight
// https://leetcode.com/problems/last-stone-weight/
const stones = [2, 7, 4, 1, 8, 1];
// prioritize bigger numbers
const maxHeap = new PriorityQueue((a, b) => b - a);
while (maxHeap.length > 1) {
const [a, b] = [maxHeap.pop(), maxHeap.pop()];
const diff = Math.abs(a - b);
if (diff !== 0) {
maxHeap.push(diff);
}
}
return maxHeap.head ?? 0;priorityQueue.head
Gets the head value in the heap. This method takes O(1) time.
Returns the head value, or undefined otherwise.
priorityQueue.pop()
Gets the head value and removes it from the heap. This method takes O(log n) time.
Returns the head value, or undefined otherwise.
priorityQueue.push(value)
Puts value to the priority queue. This method takes O(log n) time.
const priorityQueue = new PriorityQueue([3, 5, 8, 2], (a, b) => b - a);
priorityQueue.push(4);
priorityQueue.head; // => 8
priorityQueue.push(12);
priorityQueue.head; // => 12priorityQueue.length
Returns the length of queue.
new SegmentTree(values, identity, associate)
Creates a segment tree from the given values.
Segment trees use hard the given identity. identity value should be a neutral value that doesn't change when associate(otherValue, identity) called. See identity element and the examples below.
associate is a function to specify how to resolve querying.
Example: Range Minimum Query
const values = [5, 0, 7, 2, 3, 6, 1, 4, 8];
const rangeMin = new SegmentTree(
values,
// Infinity unchanges the result of Math.min()
Infinity,
// how to resolve querying
// this time, we want to find the minimum value in the range
(a, b) => Math.min(a, b)
);
// get the minimum value in the range [2, 5)
// equivalant to `Math.min(...values.slice(2, 5))`
rangeMin.queryIn(2, 5); // => 2
// update values, equivalant to `values[3] = -1`
rangeMin.setAt(3, -1);
// you can query values in mutable operations
rangeMin.queryIn(2, 5); // => -1segmentTree.getAt(i)
Gets the value at the i position.
segmentTree.queryIn(from, to)
Get the value in the range the range from and to (to is exlusive) along associate. This operation takes O(log n) time.
segmentTree.setAt(i, value)
Set the value at i position and updates its ancestors. This operation takes O(log n) time.
segmentTree.length
Returns the length of values. This operation takes O(1) time.
new UnionFind(length)
Creates union find tree (disjoint set) structure. It takes O(n) time.
unionFind.isUnited(a, b)
Returns true if the given a and b is in the same unite, false otherwise. It takes O(log n) time.
unionFind.unite(a, b)
Unites the given a and b. It takes O(log n) time.
unionFind.length
Returns number of unions in the union find tree. If no unite() is called, the return value will be the same with the length at constructor. It takes O(1) time.