Algorithm, that finds the k-greatest number in O(n*log(k))

Displayed Name 0
Viewed 32

was wondering, if you have given an unsorted list of arrays of any length n >= k, what is your idea, to find the k-greatest number in O(n*log(k)) time. So the k = 2 -greatest number of an Array containing the numbers 1 to 9 would be 8 for example.

I'm trying to code this in python, if you have an idea how in that time complexity :)

python-3.x
1 Answers

My answer is not python-specific, however you should be able to implement the used concepts in python, or find libraries already implementing them.

The basic idea is to iterate over the list and store the current greatest, second greatest, ... , k-greatest number in a separate data structure. Since you will be iterating over all n entries in your array, the complexity of this is in O(n * insertion_step_complexity)
As seen above, the insertion step needs to not exceed a complexity of O(log(k)) to achieve this you can use a AVL-Tree that has a complexity of O(log(m)) for inserting and deleting items, where m is the number of items stored within the avl-tree.

An algorithm would look like this:

def find_k_greatest_number(k, array):
    avl_tree = initialize AVL tree here
    avl_items = 0
    for number in array:
        if (number > avl_tree.smallest_number()):
            if (avl_itmes >= k):
                avl_tree.delete_smallest_number()
            else:
                avl_items++
            avl_tree.insert(number)
    return avl_tree.smallest_number()

Finding the smallest number in a sorted tree is dependent on its height. Since the AVL tree can't exceed the height of log(k) the complexity of finding the smallest number is O(log(k)).

seven_seas0
Related