How to Implement a Priority Queue using a Min-Heap

A Min-Heap is a complete binary tree where every parent node is smaller than or equal to its children. This guarantees the smallest element is always at the root. It is stored as an array where for any node at index i, its left child is at 2i plus 1, its right child is at 2i plus 2, and its parent is at i minus 1 divided by 2 using integer division.

To insert a new element, add it to the end of the array. The heap property may now be violated. Perform Bubble Up by comparing the new element with its parent. If the new element is smaller, swap them. Keep comparing and swapping upward until the element is at the root or its parent is smaller than it.

Bubble Up starts at the last index and repeatedly compares a node with its parent using the index formula. If the node is smaller than its parent, swap them and move the current index to the parent index. Stop when the node is larger than its parent or when it reaches index zero.

The minimum is always at index zero. Swap it with the last element in the array and then remove the last element. Now the root holds a large value that likely violates the heap property. Perform Bubble Down to fix this.

Bubble Down starts at index zero and compares the current node with its two children. Find the smaller of the two children. If that child is smaller than the current node, swap them and continue from the child's index. Stop when the current node is smaller than both children or when it reaches a leaf.

Peek simply returns the element at index zero without removing it. This gives you the current minimum in constant time with no modifications to the heap.

If you have an unsorted array and want to turn it into a heap all at once, start from the last non-leaf node at index n divided by 2 minus 1 and apply Bubble Down on each node going backwards to index zero. This converts the entire array into a valid heap in linear time, which is faster than inserting elements one by one.