Sliding Window Maximum Using a Heap

Problem: Given an array and a window size k, find the maximum element in every contiguous sliding window of size k, using a heap-based approach.

Constraints: Array length up to 10^5.

Example: arr = [1,3,-1,-3,5,3,6,7], k=3 -> [3,3,5,5,6,7].

Approach: Use a max-heap of (value, index) pairs. Push every element as it enters the window; before reading the max for the current window, pop from the top any entries whose index has fallen outside the window (lazy deletion). The top of the heap after cleanup is the window's maximum. O(n log n) with a heap (a monotonic deque achieves O(n), often discussed as a follow-up/optimization).