rough-outline.c

struct tree {
    struct tree_node *root, minimum;
    size_t size; 
};

struct tree ktree = { 0 };

// within the loop

if (size(ktree) < k) {
    struct tree_node *n = new_node(arr[i]);
    insert(n, ktree);
    continue;
} 

struct tree_node *min = find_min(ktree); 

if (key(min) < arr[i]) { 
    delete(min, ktree); 
    struct tree_node *n = min; 
    set_key(arr[i], n); 
    insert(n, ktree); 
}

// find_min(ktree) O(1), insert and delete maintain a pointer to the minimum element in the ktree to avoid the O (log k) lookup
// insert(n, ktree), delete(n, ktree) O(log k)
// space complexity: k nodes total, k total allocations