The other day I stumble upon the question to find the kth largest element in the array. At first glance, I thought the solution was trivial. But later I thought that there are multiple ways to achieve efficient solution
Heap is a useful data structure when root of the tree is important. Extracting an element from the heap is in logarithmic time. This could be used to find kth element from the array since finding maximum or minimum in heap is constant time.
Suppose, we have an array of arbitrary integer values. We need to find the kth largest element in the array. A sample of the input file is given below
3 9, 4, 5, 2, 1, 23, 55, 88, 74
Here, the first line is the value of n and next line contains the array
The output should print the 3rd element in the array i.e.
Before we begin, we need to perpare our tools and gather required inputs. First we need to read the input file and get the value of k and the array. Also I’ll be using ruby to write code as it is closer to psuedo code. So fire up your text editor and paste the code below
One of the first solution that pops in my mind to find the nth largest element is
We can visualize our array as tree with each value as a node of tree. However to build our array as heap , we need to satisfy certain properties
In a nutshell our array should look like this
Building heap takes O(n) time. First visit to every non-leaf node and checks if the value at the node satisfy heap property.
Max_down() is the most important function as it heapifies (or maintain the heap property).
Our last step involves extracting the kth max element.
Time complexity analysis of two methods discussed above
|Sort||O(n log(n)) + O(1)||Sorting the array + accessing the element|
|Heap||O(n) + O(k log(n))||Building heap + extracting maximum element|