Sort an Almost-Sort Array

EPI 11.3

Description:

almostly sorted array, each element is at most k distance from its true location.

Example:

Note

Idea:

use heap of size k+1.

Should use Min Heap.

Code:

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

vector<int> sortAlmostSortedArray(vector<int> arr, int k){
    priority_queue<int, vector<int>, greater<int>> pqueue;
    for(int i=0; i <= k; ++i){
        pqueue.push(arr[i]);
    }

    vector<int> result;
    for(int i=k+1; i<arr.size(); i++){
        result.push_back(pqueue.top());
        pqueue.pop();
        pqueue.push(arr[i]);
    }

    while(!pqueue.empty()){
        result.push_back(pqueue.top());
        pqueue.pop();
    }

    return result;
}

int main(){
    vector<int> arr = {3, -1, 2, 6, 4, 5, 8};
    int k=2;

    for(auto elem: sortAlmostSortedArray(arr, k)){
        cout<<elem<<' ';
    }
}