Top 5 elements in an unsorted array

Question

An unsorted array is given and we need to find top 5 elements in an efficient way and we cannot sort the list .

My solution :

• Find the max element in the array. O(n)

• Delete this max element after processing/using it.

• Repeat step 1 & 2 , k times ( 5 times in this case ).

Time Complexity : O(kn) / O(n) , Space Complexity : O(1).

I think we can find the max element in O(logN) , So it can be improved to O(klogN). Please correct me if I am wrong.

Can we do better than this ? Using max-heap would be inefficient I guess?

PS - This is not any homework.

Answer 1

If you can use an auxiliary heap (a min heap with minus element at top) you can do that in O(nlogm), where n is the list length and m the number of max elements to keep track of.

Since the aux heap has a fixed max size (5) I think that operations on that structure can be considered O(1). In that case the complexity is O(n).

Pseudo code:

foreach element in list:
    if aux_heap.size() < 5  
        aux_heap.add(element)
    else if element > aux_heap.top()
        aux_heap.remove_top()
        aux_head.add(element)

Answer 2

Using a partial quicksort we can achieve O(n), this doesn't require any auxiliary space. Using a max heap, as in the other solution requires O(n log k) time.