https://leetcode.com/problems/find-subsequence-of-length-k-with-the-largest-sum/

Leetcode: 2099. Find Subsequence of Length K With the Largest Sum

// There's definitely faster ways to do this but solution works well. 
func maxSubsequence(nums []int, k int) []int {
	h := NewIntHeap(0, 0, true)
	heap.Init(h)

	for _, num := range nums {
		heap.Push(h, num) // push every number onto descending heap
	}

	maxSubUnordered := map[int]int{}

	// pop the k-1 elements to find the minimum
	i := 0
	for i < k {
		i++
		maxSubUnordered[heap.Pop(h).(int)]++
	}

	maxSub := make([]int, k)[0:0]
	for _, num := range nums {
		if count := maxSubUnordered[num]; count > 0 {
			maxSubUnordered[num]--
			maxSub = append(maxSub, num)
		}
	}
	return maxSub

}

func NewIntHeap(initialSize int, maxSize int, desc bool) *IntHeap {
	return &IntHeap{
		data:    make([]int, initialSize)[0:0],
		desc:    desc,
		maxSize: maxSize,
	}
}

type IntHeap struct {
	data []int
	desc bool // true = descending, false = ascending
	initialSize int
	maxSize int
}

func (h *IntHeap) resetData() {
	h.data = make([]int, h.initialSize)[0:0]
	fmt.Println("Reset backing data", h)
	heap.Init(h)
}

func (h IntHeap) Len() int {
	return len(h.data)
}

func (h IntHeap) Less(i, j int) bool {
	if h.desc {
		return h.data[i] > h.data[j]
	}
	return h.data[i] < h.data[j]
}

func (h IntHeap) Swap(i, j int) {
	h.data[i], h.data[j] = h.data[j], h.data[i]
}

func (h *IntHeap) Push(x interface{}) {
	h.data = append(h.data, x.(int))
}

func (h *IntHeap) Prune() {
	if h.maxSize == 0 || h.Len() < h.maxSize {
		return
	}
	// pop the desired values
	r := make([]int, h.maxSize)
	for i := 0; i < h.maxSize; i++ {
		r[i] = heap.Pop(h).(int)
	}
	// reset heap data
	h.resetData()
	// push back
	for _, v := range r {
		heap.Push(h, v)
	}
}

func (h *IntHeap) Pop() interface{} {
	old := *h
	n := len(old.data)
	x := old.data[n-1]
	h.data = old.data[0:n-1]
	return x
}