阅读中文版本

Priority Queue CLI

A Node CLI that implements a binary-heap priority queue, accepting push and pop commands from stdin and printing popped values in priority order.

node --version

printf "push 5\npush 1\npush 3\npop\npop\npop" | node pq.mjs

node --test pq.test.mjs

Prints values popped from the priority queue in ascending order (min-heap), with push adding values and pop extracting the minimum.

What it does

Implements a min-heap priority queue with sift-up and sift-down operations. Push appends and sifts up to restore the heap property; pop swaps the root with the last element, removes it, and sifts down. Both operations are O(log n).

const heap = [];
const siftUp = i => { while (i > 0) { const p = (i - 1) >> 1; if (heap[p] <= heap[i]) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } };
const siftDown = i => { for (;;) { let s = i; const l = 2*i+1, r = 2*i+2; if (l < heap.length && heap[l] < heap[s]) s = l; if (r < heap.length && heap[r] < heap[s]) s = r; if (s === i) break; [heap[s], heap[i]] = [heap[i], heap[s]]; i = s; } };
const push = v => { heap.push(v); siftUp(heap.length - 1); };
const pop = () => { const top = heap[0]; const last = heap.pop(); if (heap.length > 0) { heap[0] = last; siftDown(0); } return top; };
const rl = require('readline').createInterface({ input: process.stdin });
rl.on('line', cmd => {
  const [op, val] = cmd.split(' ');
  if (op === 'push') push(+val); else if (op === 'pop') console.log(pop());
});

Run and verify

printf "push 5\npush 1\npush 3\npop\npop\npop" | node pq.mjs

Run the test command to check the implementation: node --test pq.test.mjs.

Expected Output

Values are popped in ascending order from the min-heap:

1
3
5

Limitations

The heap is a min-heap; a max-heap would negate values on push and pop. Duplicate values are supported. The heap does not support decrease-key or arbitrary removal.