Implement a Min Heap

To implement a Min Heap using an array, I first establish the structural invariant: it must be a complete binary tree where each parent node is less than or equal to its children. We map this structure linearly to an array where the root sits at index 0. For any node at index i, its left child is at 2*i + 1, the right child at 2*i + 2, and the parent at (i - 1) / 2. For insertion, we append the new element to the end of the array to maintain completeness. Then, we perform a 'bubble-up' operation. We compare the new element with its parent; if it is smaller, we swap them and repeat until the heap property is restored. This takes O(log n) time. To extract the minimum, which is always at the root, we swap the root with the last element, remove the last element, and then 'sift-down' the new root. During sift-down, we compare the node with its children, swapping it with the smaller child if necessary, continuing down the tree until the property holds. This also runs in O(log n). The getMin operation simply returns the element at index 0 in O(1) time. This array-based approach is highly cache-friendly and memory efficient, which aligns well with Cisco's focus on optimized network resource management.