Optimal search for k minimum values ​​in an unsorted list of integers

Question

I only had a question with a question, and I'm curious what the answer should be. The problem was essentially:

Say you have an unsorted list of n integers. How do you find k minimum values ​​in this list? That is, if you have a list [10, 11, 24, 12, 13] and you are looking for two minimum values, you will get [10, 11].

I have an O (n * log (k)) solution, and this is best, but I'm curious what other people came up with. I will refrain from polluting the brain of people by posting my decision and editing it after a while.

EDIT # 1: For example, a function such as: list getMinVals (list & l, int k)

EDIT # 2: It looks like a selection algorithm, so I will throw in my decision too; iterate through the list and use the priority queue to keep the minimum values. The specification in the priority queue was that the maximum values ​​end at the top of the priority queue, so when comparing the vertex with the element, the upper part will slip out and the smaller element will be pressed. This suggested that the priority queue had O (log n) push and O (1) pop.

Answer 1

quickSelect. , . Python, , .

def quickSelect(data, nLeast) :
    pivot = data[-1]
    less = [x for x in data if x <= pivot]
    greater = [x for x in data if x > pivot]
    less.append(pivot)

    if len(less) < nLeast :
        return less + quickSelect(greater, nLeast - len(less))
    elif len(less) == nLeast :
        return less
    else :
        return quickSelect(less, nLeast)

O (N) , data . . O (N ^ 2), , , , -3.

Answer 2

" ". min/max k . O (nlog (k)).