Complex Data Structure Snippet

Useful snippets of complex data structures for algorithm contests

• 📋 Copy-and-paste Ready
• ⛑ Tested
• ⚙️ Written in TypeScript

Usage

Copy and paste into the editor.

Snippets

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(){const t=this.head;if(this.tree.length>=2){this.tree[0]=this.tree.pop();let t=0;for(;t<this.tree.length;){const e=2*t+1,r=2*t+2;let h=t;if(e<this.tree.length&&this.compare(this.tree[e],this.tree[h])<0&&(h=e),r<this.tree.length&&this.compare(this.tree[r],this.tree[h])<0&&(h=r),t===h)break;[this.tree[t],this.tree[h]]=[this.tree[h],this.tree[t]],t=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)]}getIn(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)
  • priorityQueue.head
  • priorityQueue.pop()
  • priorityQueue.push(value)
  • priorityQueue.length
• new SegmentTree(values, identity, associate)
  • segmentTree.getAt(i)
  • segmentTree.getIn(from, to)
  • segmentTree.setAt(i, value)
  • segmentTree.length
• new UnionFind(length)
  • unionFind.isUnited(a, b)
  • unionFind.unite(a, b)
  • unionFind.length

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().

priorityQueue.head

Gets the head value in the heap. This method takes O(1) time.

Returns the head value, or undefined otherwise.

const priorityQueue = new PriorityQueue([3, 5, 8, 2], (a, b) => b - a);

priorityQueue.head; // => 8

const priorityQueue = new PriorityQueue(
  [
    { name: "Annie", age: 32 },
    { name: "Braum", age: 24 },
    { name: "Caitlyn", age: 28 }
  ],
  (a, b) => a.age - b.age
);

priorityQueue.head; // => { name: "Braum", age: 24 }

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.

const priorityQueue = new PriorityQueue([3, 5, 8, 2], (a, b) => b - a);

priorityQueue.head; // => 8
priorityQueue.pop(); // => 8
priorityQueue.head; // => 5

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; // => 12

priorityQueue.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 build segment values at internal nodes.

segmentTree.getAt(i)

Gets the value at the i position.

segmentTree.getIn(from, to)

Queries a single value in the range from and to (to is exlusive) along association strategy. This method takes O(log n) time.

To solve the famous algorithm problem "Range Minimum Query", you can specify associate as choosing the minimum value.

const segmentTree = new SegmentTree([2, 1, 3, 4], Infinity, (a, b) =>
  Math.min(a, b)
);

// equivalant to [2, 1, 3, 4].slice(2, 4) but only takes O(n log n) time
segmentTree.getIn(2, 4); // => 3

segmentTree.setAt(i, value)

Set the value at i position and updates its ancestors. This method takes O(log n) time.

const segmentTree = new SegmentTree([2, 1, 3, 4], Infinity, (a, b) =>
  Math.min(a, b)
);

segmentTree.setAt(2, prev => prev * 2);
segmentTree.getIn(2, 4); // => 4

segmentTree.length

Returns the length of values.

new UnionFind(length)

Creates union find tree (disjoint set) structure.

unionFind.isUnited(a, b)

Returns true if the given a and b is in the same unite, false otherwise.

unionFind.unite(a, b)

Unites the given a and b.

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.

License

MIT