Sliding Window Maximum Using a Heap

Problem Given an array and a window size k, report the maximum element of every contiguous window of size k as the window slides from left to right, using a heap-based approach.

Input / Output

• Input: array arr of length n, and integer k.
• Output: an array of n-k+1 values — the maximum of each successive window.

Constraints

• Array length up to 10^5, so the brute-force O(n*k) rescan of each window is too slow.
• 1 <= k <= n. When k == 1 the output is the array itself; when k == n there is a single answer.
• Values may be negative and may repeat, so identical values must be distinguished by index.

Example

• arr = [1,3,-1,-3,5,3,6,7], k=3 → [3,3,5,5,6,7].
• Tricky case: arr = [7,1,1,1], k=2 → [7,1,1]. The 7 must be evicted the moment it leaves the window, even though it remains the largest value ever seen.