Find Subsequence of Length K with the Largest Sum

class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        for (int i = 0; i < (int)nums.size(); ++i) {
            pq.push({nums[i], i});
            if ((int)pq.size() > k) pq.pop();
        }
        vector<pair<int,int>> kept;
        while (!pq.empty()) { kept.push_back(pq.top()); pq.pop(); }
        sort(kept.begin(), kept.end(), [](auto& a, auto& b){ return a.second < b.second; });
        vector<int> ans;
        for (auto& [v, _] : kept) ans.push_back(v);
        return ans;
    }
};

import (
    "container/heap"
    "sort"
)

type pair struct{ val, idx int }
type minHeap []pair

func (h minHeap) Len() int            { return len(h) }
func (h minHeap) Less(i, j int) bool  { return h[i].val < h[j].val }
func (h minHeap) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *minHeap) Push(x interface{}) { *h = append(*h, x.(pair)) }
func (h *minHeap) Pop() interface{}   { old := *h; n := len(old); x := old[n-1]; *h = old[:n-1]; return x }

func maxSubsequence(nums []int, k int) []int {
    pq := &minHeap{}
    for i, v := range nums {
        heap.Push(pq, pair{v, i})
        if pq.Len() > k {
            heap.Pop(pq)
        }
    }
    kept := make([]pair, 0, pq.Len())
    for pq.Len() > 0 {
        kept = append(kept, heap.Pop(pq).(pair))
    }
    sort.Slice(kept, func(i, j int) bool { return kept[i].idx < kept[j].idx })
    ans := make([]int, len(kept))
    for i, p := range kept {
        ans[i] = p.val
    }
    return ans
}

import heapq
from typing import List

class Solution:
    def maxSubsequence(self, nums: List[int], k: int) -> List[int]:
        heap: List[tuple] = []
        for i, v in enumerate(nums):
            heapq.heappush(heap, (v, i))
            if len(heap) > k:
                heapq.heappop(heap)
        heap.sort(key=lambda p: p[1])
        return [v for v, _ in heap]

class MinHeap {
    constructor() { this.h = []; }
    size() { return this.h.length; }
    peek() { return this.h[0]; }
    push(v) {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop() {
        const top = this.h[0];
        const last = this.h.pop();
        if (this.h.length) {
            this.h[0] = last;
            let i = 0, n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

var maxSubsequence = function(nums, k) {
    const pq = new MinHeap();
    for (let i = 0; i < nums.length; i++) {
        pq.push([nums[i], i]);
        if (pq.size() > k) pq.pop();
    }
    const kept = [];
    while (pq.size()) kept.push(pq.pop());
    kept.sort((a, b) => a[1] - b[1]);
    return kept.map(p => p[0]);
};

class Solution {
    public int[] maxSubsequence(int[] nums, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
        for (int i = 0; i < nums.length; i++) {
            pq.offer(new int[]{nums[i], i});
            if (pq.size() > k) pq.poll();
        }
        int[][] kept = new int[pq.size()][];
        int idx = 0;
        while (!pq.isEmpty()) kept[idx++] = pq.poll();
        Arrays.sort(kept, (a, b) -> Integer.compare(a[1], b[1]));
        int[] ans = new int[kept.length];
        for (int i = 0; i < kept.length; i++) ans[i] = kept[i][0];
        return ans;
    }
}

class MinHeap {
    private h: [number, number][] = [];
    size(): number { return this.h.length; }
    push(v: [number, number]): void {
        this.h.push(v);
        let i = this.h.length - 1;
        while (i > 0) {
            const p = (i - 1) >> 1;
            if (this.h[p][0] <= this.h[i][0]) break;
            [this.h[p], this.h[i]] = [this.h[i], this.h[p]];
            i = p;
        }
    }
    pop(): [number, number] {
        const top = this.h[0];
        const last = this.h.pop()!;
        if (this.h.length) {
            this.h[0] = last;
            let i = 0;
            const n = this.h.length;
            while (true) {
                const l = 2 * i + 1, r = 2 * i + 2;
                let s = i;
                if (l < n && this.h[l][0] < this.h[s][0]) s = l;
                if (r < n && this.h[r][0] < this.h[s][0]) s = r;
                if (s === i) break;
                [this.h[s], this.h[i]] = [this.h[i], this.h[s]];
                i = s;
            }
        }
        return top;
    }
}

function maxSubsequence(nums: number[], k: number): number[] {
    const pq = new MinHeap();
    for (let i = 0; i < nums.length; i++) {
        pq.push([nums[i], i]);
        if (pq.size() > k) pq.pop();
    }
    const kept: [number, number][] = [];
    while (pq.size()) kept.push(pq.pop());
    kept.sort((a, b) => a[1] - b[1]);
    return kept.map(p => p[0]);
}