{"id":27708,"date":"2018-04-09T20:22:57","date_gmt":"2018-04-09T14:52:57","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=27708"},"modified":"2018-09-11T19:21:05","modified_gmt":"2018-09-11T13:51:05","slug":"k-largestor-smallest-elements-array-added-min-heap-method","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/k-largestor-smallest-elements-array-added-min-heap-method\/","title":{"rendered":"k largest(or smallest) elements in an array | added Min Heap method"},"content":{"rendered":"

Question: <\/strong>Write an efficient program for printing k largest elements in an array. Elements in array can be in any order.<\/span><\/p>\n

For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30 and 23.<\/p>\n

\n

Recommended: Please solve it on “PRACTICE<\/u><\/i><\/b>” first, before moving on to the solution.<\/a><\/h2>\n


\nMethod 1 (Use Bubble k times)<\/strong>
\nThanks to Shailendra for suggesting this approach.
\n1) Modify Bubble Sort<\/a> to run the outer loop at most k times.
\n2) Print the last k elements of the array obtained in step 1.<\/p>\n

Time Complexity: O(nk)<\/p>\n

Like Bubble sort, other sorting algorithms like Selection Sort<\/a> can also be modified to get the k largest elements.<\/p>\n

Method 2 (Use temporary array)<\/strong>
\nK largest elements from arr[0..n-1]\n

1) Store the first k elements in a temporary array temp[0..k-1].
\n2) Find the smallest element in temp[], let the smallest element be min<\/em>.
\n3) For each element x<\/em> in arr[k] to arr[n-1]\nIf x <\/em>is greater than the min then remove min <\/em>from temp[] and insert x<\/em>.
\n4) Print final k elements of temp[]<\/em><\/p>\n

Time Complexity: O((n-k)*k). If we want the output sorted then O((n-k)*k + klogk)<\/p>\n

Thanks to nesamani1822 for suggesting this method.<\/p>\n

Method 3(Use Sorting)<\/strong>
\n1) Sort the elements in descending order in O(nLogn)
\n2) Print the first k numbers of the sorted array O(k).<\/p>\n

Time complexity: O(nlogn)<\/p>\n

Method 4 (Use Max Heap)<\/strong>
\n1) Build a Max Heap tree in O(n)
\n2) Use Extract Max<\/a> k times to get k maximum elements from the Max Heap O(klogn)<\/p>\n

Time complexity: O(n + klogn)<\/p>\n

Method 5(Use Oder Statistics)<\/strong>
\n1) Use order statistic algorithm to find the kth largest element. Please see the topic selection in worst-case linear time <\/a>O(n)
\n2) Use QuickSort <\/a>Partition algorithm to partition around the kth largest number O(n).
\n3) Sort the k-1 elements (elements greater than the kth largest element) O(kLogk). This step is needed only if sorted output is required.<\/p>\n

Time complexity: O(n) if we don\u2019t need the sorted output, otherwise O(n+kLogk)<\/p>\n

Thanks to Shilpi <\/a>for suggesting the first two approaches.<\/p>\n

Method 6 (Use Min Heap)<\/strong>
\nThis method is mainly an optimization of method 1. Instead of using temp[] array, use Min Heap.<\/p>\n

Thanks to geek4u <\/a>for suggesting this method.<\/p>\n

1) Build a Min Heap MH of the first k elements (arr[0] to arr[k-1]) of the given array. O(k)<\/p>\n

2) For each element, after the kth element (arr[k] to arr[n-1]), compare it with root of MH.
\n\u2026\u2026a) If the element is greater than the root then make it root and call heapify <\/a>for MH
\n\u2026\u2026b) Else ignore it.
\n\/\/ The step 2 is O((n-k)*logk)<\/p>\n

3) Finally, MH has k largest elements and root of the MH is the kth largest element.<\/p>\n

Time Complexity: O(k + (n-k)Logk) without sorted output. If sorted output is needed then O(k + (n-k)Logk + kLogk)<\/p>\n

All of the above methods can also be used to find the kth largest (or smallest) element.<\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"

Question: Write an efficient program for printing k largest elements in an array. Elements in array can be in any order. For example, if given array is [1, 23, 12, 9, 30, 2, 50] and you are asked for the largest 3 elements i.e., k = 3 then your program should print 50, 30 and […]<\/p>\n","protected":false},"author":1,"featured_media":31258,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[73012,80127],"tags":[81996,82000,72887,81997,81998,82001,82002,81999],"class_list":["post-27708","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-data-structures","category-heap","tag-find-k-largest-elements-in-array","tag-find-kth-largest-element-in-max-heap","tag-find-kth-smallest-element-in-array-java","tag-kth-largest-element-in-an-array-geeksforgeeks","tag-kth-largest-element-in-an-array-leetcode","tag-kth-largest-element-in-array-in-c","tag-kth-smallest-element-in-an-array-in-c","tag-kth-smallest-element-in-an-array-without-sorting"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27708","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=27708"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/27708\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media\/31258"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=27708"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=27708"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=27708"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}