JavaScript Additional Data Structure Snippet

Usage

Copy and paste or install

npm install --save additional-data-structure

Snippets

Binary Heap

class BinaryHeap{constructor(t,h){this.cbt=[],this.compare=h;for(const h of t)this.push(h)}peek(){if(0!==this.cbt.length)return this.cbt[0]}pop(){const t=this.cbt[0];if(this.cbt.length>=2){this.cbt[0]=this.cbt.pop();let t=0;for(;t<this.cbt.length;){const h=2*t+1,s=2*t+2;let c=t;if(h<this.cbt.length&&this.compare(this.cbt[h],this.cbt[c])<0&&(c=h),s<this.cbt.length&&this.compare(this.cbt[s],this.cbt[c])<0&&(c=s),t===c)break;[this.cbt[t],this.cbt[c]]=[this.cbt[c],this.cbt[t]],t=c}}return t}push(t){let h=this.cbt.length;for(this.cbt.push(t);h>0;){const t=Math.floor((h-1)/2);if(this.compare(this.cbt[h],this.cbt[t])>=0)break;[this.cbt[h],this.cbt[t]]=[this.cbt[t],this.cbt[h]],h=t}}}

Segment Tree

class SegmentTree{constructor(t,e,h,i){this.cbt=[],this.identity=e,this.associate=h,this.update=i,this.leafLength=2**Math.ceil(Math.log2(t.length)),this.internalLength=this.leafLength-1;for(let e=0;e<this.leafLength;++e)e<t.length?this.cbt[e+this.internalLength]=t[e]:this.cbt[e+this.internalLength]=this.identity;for(let t=this.internalLength-1;t>=0;--t)this.cbt[t]=this.associate(this.cbt[2*t+1],this.cbt[2*t+2])}static fill(t,e,h,i,s){return new SegmentTree(Array.from({length:t},()=>e),h,i,s)}getIn(t,e){let h=this.identity;const i=[[0,0,this.leafLength]];for(;i.length>0;){const[s,n,a]=i.shift();n>=t&&a<=e?h=this.associate(h,this.cbt[s]):n>=e||a<t||s>=this.internalLength||i.push([2*s+1,n,Math.floor((n+a)/2)],[2*s+2,Math.floor((n+a)/2),a])}return h}updateAt(t,e){const h=t+this.internalLength;this.cbt[h]=this.update(this.cbt[h],e);let i=Math.ceil(h/2)-1;for(;i>=0;)this.cbt[i]=this.associate(this.cbt[2*i+1],this.cbt[2*i+2]),i=Math.ceil(i/2)-1}}