K отсортированный массив с использованием очереди приоритетов - C ++

Question

Я реализую отсортированный массив с использованием очереди приоритетов в C ++. На выходе сортируются только первые k элементов, а остальные нет. Пожалуйста, найдите проблему в коде.

Вот код:

#include <iostream>
#include <queue>
using namespace std;

void kSortedArray(int input[], int n, int k){
    priority_queue<int> pq;
    for(int i= 0; i < k; i++){
        pq.push(input[i]);
    }

    int j = 0;
    for(int i = k; i < n; i++){
        int ans = pq.top();
        pq.pop();
        input[j] = ans;
        pq.push(input[i]);
        j++;
    }

    while(pq.size() != 0){
        input[j] = pq.top();
        pq.pop();
    }
}





int main() {
    int input[] = {10, 12, 6, 7, 9};
    int k = 3;
    kSortedArray(input, 5, k);
    for(int i = 0; i < 5; i++){
        cout << input[i] << " ";
    }
}

Answer 1

Исправьте эту часть (вы забыли увеличить j):

    while(pq.size() != 0){
        input[j++] = pq.top(); // <-- this line
        pq.pop();
    }

Также ваш код сортируется в порядке убывания. Если вы хотите сортировать по возрастанию, используйте minheap:

priority_queue<int,vector<int>, greater<int>> pq;