What is the time complexity of sorting half an array using a priority queue?

0
votes

So I have developed a Priority Queue using a Min Heap and according to online tutorials it takes O(nlogn) time to sort an entire array using a Priority Queue. This is because we extract 'n' times and for every extraction we have to perform a priority fix which takes logn time. Hence it is nlogn.

However, if I only want to sort half an array every single time, would it still be O(nlogn) time? Or would it be just O(logn)? The reason why I want to do this is because I want to get the element with middle priority and this seems like the only way to do it using a priority queue by extracting half the elements unless there is a more intuitive way of getting the element with middle priority in Priority Queue.

1
algorithmtime-complexitypriority-queue
Do you mean (1) sorting the first half of the array (2) finding the sorted order of the smallest n/2 elements in the array or (3) just finding the n/2-smallest element. The latter can be done in O(log n) using a balanced binary search tree data structure. The former two will need at least O(n log n) time – Niklas B.

1 Answers

1
votes

I think that the question is in two parts, so I will answer in two parts:

(a) If I understand you correctly, by sorting "half an array" you mean obtaining a sorted array of (n/2) smallest values of the given array. This will have to take O(n lg n) time. If there were a technique for doing this shorter than O(n lg n) time, then whenever we wanted to sort an array of n values whose maximum value is known to be v (and we can obtain the maximum value in O(n) time), we could construct an array of 2n elements, where the first half is the original array and the second half is filled with a value larger than v. Then, applying the hypothetical technique, we could in effect sort the original array in a time shorter than O(n lg n), which is known to be impossible.

(b) But if I am correct in understanding "the element with middle priority" as the median element in an array, you may be interested in this question.