heaps.py

import heapq

from typing import List


def kthsmallest1(l: List[int], k: int) -> int:  # nlogk
    if k > len(l):
        return min(l)

    l = [-1 * elt for elt in l]

    h: List[int] = []
    # O(log k)
    for elt in l[:k]:
        heapq.heappush(h, elt)
    for elt in l[k:]:
        if elt in h:
            pass
        else:
            # O(n log k) worst case
            heapq.heappushpop(h, elt)
    return -1*heapq.heappop(h)


def test_kth_smallest1():
    assert 3 == kthsmallest1(range(10), 4)


test_kth_smallest1()