Heap: Sort a K sorted array or nearly sorted array

Problem Statement:

You are given an array elements in which each element is at k away from its target position.

Example

Input:
arr[] = {6, 5, 3, 2, 8, 10, 9}

k = 3

Solution

First we will understand the question.

Here the array is nearly sorted. It means an element at index “n” can be present at “n-k to n+k”

It means, for example “6” is at index “0”, but can be at index “1, 2, 3”

Similarly element “5” at index 1, can be at index “0, 2, 3, 4”.

Here we need to sort, so it can be considered as smallest.

So now it is clear. We will understand with an example.

Consider the array arr[] = {6, 5, 3, 2, 8, 10, 9} and k = 3

Pass 1: element = 6

We take a min_heap of size “k”. Because in the question, it is clear that any element is misplaced from “k” position.

Stack: 6

Pass 2: element = 5

Stack: 6 5

Pass 3: element = 3

Stack: 6 5 3

Pass 4: element = 2

Stack: 6 5 3 2

Now it is clear for us, for the size “k”, 2 is the smallest. We will pop 2 and insert at the 0th index of array.

Pass 5: element = 8

As we are using min heap, 8 will go at the bottom. Now the size is more than “k”. So pop 3 and insert at the 1st index of the array.

Stack: 8 6 5 3

Similarly we sort the whole array

Solution in C++

#include <algorithm>  
#include <iostream>    
#include <string>
#include <stack>
#include <vector>
#include <queue> 
#include <list> 

using namespace std;

void sort_K_sorted_array(vector<int> &arr, int k)
{

    priority_queue<int, vector<int>, greater<int>> min_heap;
 
    // insert the first `k+1` elements into min_heap
    for (int i = 0; i <= k; i++) 
    {
        min_heap.push(arr[i]);
    }
 
    int index = 0;
 
    // perform the same operation for remaining elements of the array
    for (int i = k + 1; i < arr.size(); i++)
    {
      // pop the top element of the heap and assign to the 
      // next available index of the array starting from 0
        arr[index++] = min_heap.top();
        min_heap.pop();
 
        // push the next element into the heap
        min_heap.push(arr[i]);
    }
 
    // pop remaining elements form the min_heap into the array.
    while (!min_heap.empty())
    {
        arr[index++] = min_heap.top();
        min_heap.pop();
    }
}
 
int main()
{
    vector<int> vec = {6, 5, 3, 2, 8, 10, 9};
 
    int k = 3;
 
    sort_K_sorted_array(vec, k);
 
    cout<<"Sorted array is ";

    for (int i = 0; i < vec.size(); i++)
        cout << vec[i] << " ";
    cout<<endl;

    return 0;
}

Output:

Sorted array is 2 3 5 6 8 9 10