This repo is for studying binary heaps.
A heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max-heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min-heap, the key of P is less than or equal to the key of C.
A priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a priority associated with it. In a priority queue, an element with high priority is served before an element with low priority.
n - the number of nodes in a heap (the size of a heap or a priority queue).
peek()- O(1)push()- O(log n)pop()- O(log n)
The MaxHeap and MinHeap classes implement a basic heap data structure. They use a one-based indexed array as a data container. Both heap types can contain numbers only.
A constructor requires the maximum number of elements in a heap.
const minHeap = new MinHeap(10); // contains a maximum of 10 numbers in the heapsize- current size of a heap.maxSize- maximum size of a heap.
push(num: number)- Add a number to the heap. Returnstrueif the heap size is not exceeded, orfalseotherwise.pop(): number | undefined- Removes the min(max)-heap element and returns it. If the heap is empty returnsundefinedand the heap is not modified.peek(): number | undefined- Returns the top min(max)-heap number orundefinedif the heap is empty. The heap is not modified.
MaxHeap
const maxHeap = new MaxHeap(10);
maxHeap.push(5); // expected output: true
maxHeap.push(15); // expected output: true
maxHeap.push(7); // expected output: true
maxHeap.peek(); // expected output: 15
maxHeap.pop(); // expected output: 15
maxHeap.pop(); // expected output: 7
maxHeap.pop(); // expected output: 5
maxHeap.peek(); // expected output: undefinedMinHeap
const minHeap = new MinHeap(3);
minHeap.push(5); // expected output: true
minHeap.push(8); // expected output: true
minHeap.push(4); // expected output: true
minHeap.push(1); // expected output: false
minHeap.peek(); // expected output: 4
minHeap.pop(); // expected output: 4
minHeap.pop(); // expected output: 5
minHeap.pop(); // expected output: 8
minHeap.pop(); // expected output: undefinedThe PriorityQueue class implements the same binary heap structure as MinHeap and MaxHeap, the difference is that PQ elements are prioritized according a compare function and the elements can be anything that can be compared in terms of priority.
A constructor takes one argument compareFn - a function used to determine the order (priority) of the nodes in a heap. Function is expected to return a boolean value.
const compareFn = (childNode, parentNode) => boolean;When true is returned, it means that childNode has a higher priority than parentNode.
If omitted, the nodes prioritized according the function (min-heap):
const compareFn = (childNode, parentNode) => {
return newNode < parentNode;
};size- current size of aPQ.
push(node: any): number- Add a node to thePQ. Returns current size of thePQ.pop(): any | undefined- Removes the topPQnode and returns it. If thePQis empty returnsundefinedand thePQis not modified.peek(): number | undefined- Returns the top node orundefinedif thePQis empty. ThePQis not modified.
PriorityQueue as a MinHeap
// When compareFn argument is omitted the PQ behaves like a MinHeap.
const minHeap = new PriorityQueue();
minHeap.push(5); // expected output: 1
minHeap.push(15); // expected output: 2
minHeap.push(10); // expected output: 3
minHeap.peek(); // expected output: 5
minHeap.pop(); // expected output: 5
minHeap.pop(); // expected output: 10
minHeap.pop(); // expected output: 15
minHeap.peep(); // expected output: undefinedPriorityQueue with arrays as nodes
// The nodes of the PQ are arrays of length 2 - node: [number, number].
// Let's prioritize the nodes according the second element in the node.
// The node with the smallest second element will be at the top of the PQ.
const compareFn = (childNode, parentNode) => {
return childNode[1] < parentNode[1];
};
const pq = new PriorityQueue(compareFn);
pq.push([1, 4]); // expected output: 1
pq.push([1, 2]); // expected output: 2
pq.push([3, 1]); // expected output: 3
pq.push([2, 1]); // expected output: 4
pq.peek(); // expected output: [3, 1]
pq.pop(); // expected output: [3, 1]
pq.pop(); // expected output: [2, 1]
pq.pop(); // expected output: [1, 2]
pq.pop(); // expected output: [1, 4]In this example, when two nodes have the same second element, that means they have the same priority, and since [3, 1] was pushed earlier, it's higher in PQ than [2, 1].
PriorityQueue with objects as nodes
// The nodes of the PQ are objects of the structure - node: {x: number, y: string}.
// Let's prioritize the nodes first according to the `x` property
// (largest goes on top) and secondly according to the `y` property
// (in lexicographic order).
const compareFn = (childNode, parentNode) => {
if (childNode.x === parentNode.x) {
return childNode.y < parentNode.y;
}
return childNode.x > parentNode.x;
};
const pq = new PriorityQueue(compareFn);
pq.push({x: 10, y: 'b'}); // expected output: 1
pq.push({x: 10, y: 'a'}); // expected output: 2
pq.push({x: 3, y: 'c'}); // expected output: 3
pq.push({x: 8, y: 'c'}); // expected output: 4
pq.peek(); // expected output: {x: 10, y: 'a'}
pq.pop(); // expected output: {x: 10, y: 'a'}
pq.pop(); // expected output: {x: 10, y: 'b'}
pq.pop(); // expected output: {x: 8, y: 'c'}
pq.pop(); // expected output: {x: 3, y: 'c'}MinHeap, MaxHeap and PriorityQueue classes share the same utility methods:
#heapifyUp(idx: number)(iterative) - Traverse up the heap to find a suitable place for the node at indexidx. The method is implemented in thepush()method.#heapifyDown(idx: number)(iterative) - Traverse down the heap to find a suitable place for the node at indexidx. The method is implemented in thepop()method.