sliding window maximum using priority queue code example

Example 1: sliding window maximum using queue

int[] slidingWindowMaximum(int arr[], int n, int k)
{
   q = Dequeue()   
   ans = []
   // for First K elements
   for( i = 0 to k-1)
   {
       while(!q.empty() and  arr[i] >= arr[q.back()])
       {
           // Remove the indices of elements that are smaller than the current elements
           q.pop_back()
       }    
       q.push_back(i)
   }
   // the element at the front has index of the highest element in the window
   ans.append(arr[q.front()])
   // for rest elements
   for(i = k to n-1)
   {
        // drop the elements that are out of window
        while(!q.empty() and q.front() <= i-k)
            q.pop_front()
        
        // remove those elements smaller than the current element from back
        while(!q.empty() and arr[i] >= arr[q.back()])
            q.pop_back()    
        q.push_back(i)
        ans.append(arr[q.front()])
   }   
   return ans
}

Example 2: sliding window maximum using queue

int[] slidingWindowMaximum(int arr[], int n, int k)
{
    heap = PriorityQueue()
    toDrop = PriorityQueue()
    // Push First K elements in the heap
    for(i = 0 to k-1)
        heap.push(arr[i])
    ans = []
    // store the maximum in ans
    ans.append(heap.top())
    //iterate for rest elements
    for(i = k to n)
    {
        // pop the heap if leftmost element is previous element was maximum
        if(arr[i-k] == heap.top())
            heap.pop()
        else
        {
            // push the leftmost element to toDrop heap 
            toDrop.push(arr[i-k])
        }   
        // pop elements from both heap till their top matches
        while(!toDrop.isEmpty() and toDrop.top() == heap.top())
        {
            heap.pop()
            toDrop.pop()
        }
        // push the element to the heap
        heap.push(arr[i])
        ans.append(heap.top())
    }
    return ans
}