Hello Everyone,
In continuation with last post.
Method 3: This method uses Deque to solve the above problem.
Approach:
Create a Deque, Qi of capacity k, that stores only useful elements of current window of k elements. An element is useful if it is in current window and is greater than all other elements on right side of it in current window. Process all array elements one by one and maintain Qi to contain useful elements of current window and these useful elements are maintained in sorted order. The element at front of the Qi is the largest and element at rear/back of Qi is the smallest of current window.
Algorithm:
 Create a deque to store k elements.
 Run a loop and insert first k elements in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element , if it is so remove the element from the back of the deque, until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
 Now, run a loop from k to end of the array.
 Print the front element of the deque.
 Remove the element from the front of the queue if they are out of the current window.
 Insert the next element in the deque. Before inserting the element, check if the element at the back of the queue is smaller than the current element , if it is so remove the element from the back of the deque, until all elements left in the deque are greater than the current element. Then insert the current element, at the back of the deque.
 Print the maximum element of the last window.
Implementation:
// CPP program for the above approach
#include <bits/stdc++.h>
using
namespace
std;
// A Dequeue (Double ended queue) based
// method for printing maximum element of
// all subarrays of size k
void
printKMax(
int
arr[],
int
n,
int
k)
{
// Create a Double Ended Queue,
// Qi that will store indexes
// of array elements
// The queue will store indexes
// of useful elements in every
// window and it will
// maintain decreasing order of
// values from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()]
// are sorted in decreasing order
std::deque<
int
> Qi(k);
/* Process first k (or first window)
elements of array */
int
i;
for
(i = 0; i < k; ++i)
{
// For every element, the previous
// smaller elements are useless so
// remove them from Qi
while
((!Qi.empty()) && arr[i] >=
arr[Qi.back()])
// Remove from rear
Qi.pop_back();
// Add new element at rear of queue
Qi.push_back(i);
}
// Process rest of the elements,
// i.e., from arr[k] to arr[n1]
for
(; i < n; ++i)
{
// The element at the front of
// the queue is the largest element of
// previous window, so print it
cout << arr[Qi.front()] <<
" "
;
// Remove the elements which
// are out of this window
while
((!Qi.empty()) && Qi.front() <=
i  k)
// Remove from front of queue
Qi.pop_front();
// Remove all elements
// smaller than the currently
// being added element (remove
// useless elements)
while
((!Qi.empty()) && arr[i] >=
arr[Qi.back()])
Qi.pop_back();
// Add current element at the rear of Qi
Qi.push_back(i);
}
// Print the maximum element
// of last window
cout << arr[Qi.front()];
}
// Driver code
int
main()
{
int
arr[] = { 12, 1, 78, 90, 57, 89, 56 };
int
n =
sizeof
(arr) /
sizeof
(arr[0]);
int
k = 3;
printKMax(arr, n, k);
return
0;
}
Output
78 90 90 90 89
Complexity Analysis:

Time Complexity: O(n).
It seems more than O(n) at first look. It can be observed that every element of array is added and removed at most once. So there are total 2n operations. 
Auxiliary Space: O(k).
Elements stored in the dequeue take O(k) space.
Method 4: This method uses MaxHeap to solve the above problem.
Approach:
In the abovementioned methods, one of them was using AVL tree. This approach is very similar to that approach. The difference is that instead of using the AVL tree, MaxHeap will be used in this approach. The elements of the current window will be stored in the MaxHeap and the maximum element or the root will be printed in each iteration.
Maxheap is a suitable data structure as it provides constanttime retrieval and logarithmic time removal of both the minimum and maximum elements in it, i.e. it takes constant time to find the maximum element and insertion and deletion takes log n time.
Algorithm:
 Pick first k elements and create a max heap of size k.
 Perform heapify and print the root element.
 Store the next and last element from the array
 Run a loop from k – 1 to n
 Replace the value of element which is got out of the window with new element which came inside the window.
 Perform heapify.
 Print the root of the Heap.