FAANG JS Helper Library for heap, tree, graph, queue etc

You can use below helpers to implement heap, graph etc

// ===================================== // FAANG JS Helper Library // =====================================

// -------------------- // MinHeap // -------------------- class MinHeap { constructor() { this.heap = []; }

_parent(i) { return Math.floor((i - 1) / 2); }
_left(i) { return 2 * i + 1; }
_right(i) { return 2 * i + 2; }

_swap(i, j) { [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]; }

push(val) {
    this.heap.push(val);
    this._heapifyUp();
}

_heapifyUp() {
    let i = this.heap.length - 1;
    while (i > 0) {
        let parent = this._parent(i);
        if (this.heap[parent] > this.heap[i]) {
            this._swap(parent, i);
            i = parent;
        } else break;
    }
}

pop() {
    if (!this.heap.length) return null;
    if (this.heap.length === 1) return this.heap.pop();
    const root = this.heap[0];
    this.heap[0] = this.heap.pop();
    this._heapifyDown();
    return root;
}

_heapifyDown() {
    let i = 0;
    const n = this.heap.length;
    while (this._left(i) < n) {
        let left = this._left(i);
        let right = this._right(i);
        let smallest = left;
        if (right < n && this.heap[right] < this.heap[left]) smallest = right;

        if (this.heap[i] > this.heap[smallest]) {
            this._swap(i, smallest);
            i = smallest;
        } else break;
    }
}

peek() { return this.heap[0]; }
size() { return this.heap.length; }

}

// -------------------- // MaxHeap (extends MinHeap) // -------------------- class MaxHeap extends MinHeap { _heapifyUp() { let i = this.heap.length - 1; while (i > 0) { let parent = this._parent(i); if (this.heap[parent] < this.heap[i]) { this._swap(parent, i); i = parent; } else break; } }

_heapifyDown() {
    let i = 0;
    const n = this.heap.length;
    while (this._left(i) < n) {
        let left = this._left(i);
        let right = this._right(i);
        let largest = left;
        if (right < n && this.heap[right] > this.heap[left]) largest = right;

        if (this.heap[i] < this.heap[largest]) {
            this._swap(i, largest);
            i = largest;
        } else break;
    }
}

}

// -------------------- // PriorityQueue (min-heap based) // -------------------- class PriorityQueue { constructor() { this.heap = new MinHeap(); }

push(value, priority) {
    this.heap.push({ value, priority });
}

pop() {
    const { value } = this.heap.pop() || {};
    return value;
}

peek() {
    const { value } = this.heap.peek() || {};
    return value;
}

size() { return this.heap.size(); }

}

// -------------------- // Binary Search Tree (BST) // -------------------- class TreeNode { constructor(val) { this.val = val; this.left = null; this.right = null; } }

class BST { constructor() { this.root = null; }

insert(val) {
    const node = new TreeNode(val);
    if (!this.root) {
        this.root = node;
        return;
    }
    let curr = this.root;
    while (true) {
        if (val < curr.val) {
            if (!curr.left) { curr.left = node; break; }
            curr = curr.left;
        } else {
            if (!curr.right) { curr.right = node; break; }
            curr = curr.right;
        }
    }
}

// In-order traversal
inorder(node = this.root, res = []) {
    if (!node) return res;
    this.inorder(node.left, res);
    res.push(node.val);
    this.inorder(node.right, res);
    return res;
}

// Search value
search(val) {
    let curr = this.root;
    while (curr) {
        if (val === curr.val) return true;
        curr = val < curr.val ? curr.left : curr.right;
    }
    return false;
}

}

// -------------------- // Graph (Adjacency List) // -------------------- class Graph { constructor() { this.adj = new Map(); }

addVertex(v) {
    if (!this.adj.has(v)) this.adj.set(v, []);
}

addEdge(u, v) {
    if (!this.adj.has(u)) this.addVertex(u);
    if (!this.adj.has(v)) this.addVertex(v);
    this.adj.get(u).push(v);
    // For undirected graph, also add reverse edge
    // this.adj.get(v).push(u);
}

neighbors(v) {
    return this.adj.get(v) || [];
}

// BFS traversal
bfs(start) {
    const visited = new Set();
    const queue = [start];
    const res = [];
    visited.add(start);

    while (queue.length) {
        const node = queue.shift();
        res.push(node);
        for (let neighbor of this.neighbors(node)) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return res;
}

// DFS traversal
dfs(start) {
    const visited = new Set();
    const res = [];
    const stack = [start];

    while (stack.length) {
        const node = stack.pop();
        if (!visited.has(node)) {
            visited.add(node);
            res.push(node);
            for (let neighbor of this.neighbors(node).reverse()) {
                if (!visited.has(neighbor)) stack.push(neighbor);
            }
        }
    }
    return res;
}

}

// ===================================== // Export if using modules // module.exports = { MinHeap, MaxHeap, PriorityQueue, BST, Graph };