should we use STL(set) to find the kth smallest/largest element in an unsorted array??
time complexity:O(logn)
SOURCES*****************
please see the `1 answer:
Suppose a max-heap in this case (in which the value of parent is atleast that of the max(child1, child2)).
We can build a heap from an array in almost O(n) time. Once the heap is ready, all we have to do is pop the element and heapify() to resolve any violations which may occur in the process (value of parent should be atleast the value of its childs for every edge). Now pop() operations is constant time. heapify() has a complexity of O(TreeHeight) which will be O(log(n)) . All we have to do now is repeat this operation k times. Thus the overall complexity is O(n + klog(n)) .
Now comes the part why Heap is better than Sorting (O(nlog(n) ) in terms of complexity. After observing a little, we can infer that the Sorting solution is kind of an upper bound to the Heap solution because if the value of k is not large enough, then the Heap solution can have an overall complexity of O(n).
thanks for the explaination.
got it!!!
In the problem TSORT, STL sort had the execution time of 0.71 sec but Heap sort gave me the execution time of 0.55 sec.
Use counting sort in that question. My counting sort solution has a running time of 0.28 secs.