Given an array Arr of N positive integers and an integer K, find K largest elements from the array.  The output elements should be printed in decreasing order.
Example 1:
Input:
N = 5, K = 2
Arr[] = {12, 5, 787, 1, 23}
Output: 787 23
Explanation: 1st largest element in the
array is 787 and second largest is 23.
Example 2:
Input:
N = 7, K = 3
Arr[] = {1, 23, 12, 9, 30, 2, 50}
Output: 50 30 23
Explanation: 3 Largest element in the
array are 50, 30 and 23.
Your Task:
You don't need to read input or print anything. Your task is to complete the function kLargest() which takes the array of integers arr, n and k as parameters and returns an array of integers denoting the answer. The array should be in decreasing order.
Expected Time Complexity: O(N + KlogK)
Expected Auxiliary Space: O(K+(N-K)*logK)
Constraints:
1 ≤ K ≤ N ≤ 10^{5}
1 ≤ Arr[i] ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:



	def kLargest(self,arr, n, k):

		# code here

Solutions:
import heapq

class Solution:

	def kLargest(self, arr, n, k):
		heap = []
		for elm in arr:
			if len(heap) < k:
				heapq.heappush(heap, elm)
			elif elm >= heap[0]:
				heapq.heappop(heap)
				heapq.heappush(heap, elm)
		ans = []
		while heap != []:
			ans.insert(0, heapq.heappop(heap))
		return ans


from heapq import *

class Solution:

	def kLargest(self, arr, n, k):
		heap = []
		for ele in arr:
			if len(heap) < k:
				heappush(heap, ele)
			else:
				top = heap[0]
				if ele > top:
					heappop(heap)
					heappush(heap, ele)
		heap.sort(reverse=True)
		return heap


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort()
		arr = arr[::-1]
		return arr[:k]


class Solution:

	def partition(self, arr, s, e, p):
		if s + 1 == e:
			return s
		j = s
		v = arr[p]
		(arr[e - 1], arr[p]) = (arr[p], arr[e - 1])
		for i in range(s, e):
			if arr[i] > v:
				(arr[j], arr[i]) = (arr[i], arr[j])
				j += 1
		(arr[j], arr[e - 1]) = (arr[e - 1], arr[j])
		return j

	def quickSort(self, arr, s, e):
		if s + 1 >= e:
			return
		m = self.partition(arr, s, e, (s + e) // 2)
		self.quickSort(arr, s, m)
		self.quickSort(arr, m + 1, e)

	def kLargest(self, arr, n, k):
		s = 0
		e = n
		while True:
			m = self.partition(arr, s, e, k)
			if m == k:
				break
			if m > k:
				e = m
			else:
				s = m + 1
		self.quickSort(arr, 0, k)
		return arr[:k]


class Solution:

	def kLargest(self, arr, n, k):
		brr = sorted(arr, reverse=True)
		crr = []
		for i in range(k):
			crr.append(brr[i])
		return crr


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		heapq.heapify(arr)
		return heapq.nlargest(k, arr)


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort(reverse=True)
		return arr[:k]


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort(reverse=True)
		for i in range(k):
			return arr[:k]


class Solution:

	def kLargest(self, arr, n, k):
		return sorted(arr)[::-1][:k]


class Solution:

	def kLargest(self, arr, n, k):
		sorted_arr = sorted(arr)
		k_largestArr = sorted_arr[n - k:]
		k_largestArr.reverse()
		return k_largestArr


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		maxheap = []
		ans = []
		for i in range(0, n):
			heapq.heappush(maxheap, -arr[i])
		while k > 0:
			ele = -heapq.heappop(maxheap)
			ans.append(ele)
			k -= 1
		return ans


import heapq as h

class Solution:

	def kLargest(self, arr, n, k):
		result = []
		arr.sort()
		arr.reverse()
		for i in range(0, k):
			result.append(arr[i])
		return result


import heapq as h

class Solution:

	def kLargest(self, arr, n, k):
		minheap = []
		result = []
		for i in range(0, n):
			if len(minheap) < k:
				h.heappush(minheap, arr[i])
			elif arr[i] > minheap[0]:
				h.heappop(minheap)
				h.heappush(minheap, arr[i])
		while k > 0:
			result.append(h.heappop(minheap))
			k = k - 1
		return result[::-1]


import heapq as h

class Solution:

	def kLargest(self, arr, n, k):
		maxheap = []
		result = []
		for i in range(0, n):
			h.heappush(maxheap, -arr[i])
		while k > 0:
			result.append(-h.heappop(maxheap))
			k = k - 1
		return result


class Solution:

	def kLargest(self, arr, n, k):
		l = []
		arr.sort()
		arr.reverse()
		for i in range(k):
			l.append(arr[i])
		return l


class Solution:

	def kLargest(self, arr, n, k):
		b = sorted(arr, reverse=True)
		return b[:k]


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		arr1 = arr[0:k]
		heapq.heapify(arr1)
		for i in range(k, n):
			if arr1[0] < arr[i]:
				heapq.heappop(arr1)
				heapq.heappush(arr1, arr[i])
		ans = []
		for i in range(k):
			ans.append(heapq.heappop(arr1))
		return ans[::-1]


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort(reverse=True)
		ans = []
		for i in range(0, k):
			ans.append(arr[i])
		return ans


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		h = []
		heapq.heapify(h)
		for ele in arr:
			heapq.heappush(h, -1 * ele)
		ans = []
		for i in range(k):
			a = heapq.heappop(h)
			ans.append(-1 * a)
		return ans


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		heap = []
		list1 = []
		for i in range(n):
			heapq.heappush(heap, -arr[i])
		while k > 0:
			list1.append(-heapq.heappop(heap))
			k -= 1
		return list1


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort()
		result = []
		for i in range(k):
			result.append(arr[-i - 1])
		return result


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort(reverse=True)
		l = []
		i = 0
		while k != 0:
			l.append(arr[i])
			i += 1
			k -= 1
		return l


class Solution:

	def kLargest(self, arr, n, k):

		def heapify(arr, n, i):
			left = 2 * i + 1
			right = 2 * i + 2
			if left <= n - 1 and arr[left] > arr[i]:
				largest = left
			else:
				largest = i
			if right <= n - 1 and arr[right] > arr[largest]:
				largest = right
			if largest != i:
				(arr[largest], arr[i]) = (arr[i], arr[largest])
				heapify(arr, n, largest)

		def buildHeap(arr, n):
			i = n // 2 - 1
			while i >= 0:
				heapify(arr, n, i)
				i = i - 1
		buildHeap(arr, n)
		a = []
		for i in range(k):
			a.append(arr[0])
			(arr[0], arr[n - 1]) = (arr[n - 1], arr[0])
			n = n - 1
			heapify(arr, n, 0)
		return a


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		l = []
		for i in range(k):
			heapq.heappush(l, arr[i])
		for i in range(k, n):
			if arr[i] > l[0]:
				heapq.heappushpop(l, arr[i])
		res = []
		while l:
			res.append(heapq.heappop(l))
		res.reverse()
		return res


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		l = []
		min = []
		for val in arr:
			if len(min) < k:
				heapq.heappush(min, val)
			elif len(min) == k:
				if val > min[0]:
					heapq.heappop(min)
					heapq.heappush(min, val)
		for i in range(k):
			l += [heapq.heappop(min)]
		l1 = []
		for i in l:
			l1.insert(0, i)
		return l1


class Solution:

	def kLargest(self, arr, n, k):
		b = n - k
		v = sorted(arr)
		l = []
		for i in range(n - 1, b - 1, -1):
			l.append(v[i])
		return l


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort()
		a = []
		for i in range(len(arr)):
			if len(a) != k:
				a.append(arr[n - 1 - i])
			else:
				return a


class Solution:

	def kLargest(self, arr, n, k):
		a = []
		arr.sort()
		j = n - 1
		for i in range(k):
			a.append(arr[j])
			j = j - 1
		return a


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort()
		x = arr[::-1]
		y = []
		for i in range(k):
			y.append(x[i])
		return y


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort()
		li = []
		for i in arr[n - k:]:
			li.append(i)
		return li[::-1]


def heapify(arr, i, n):
	index = i
	lchild = 2 * index + 1
	rchild = 2 * index + 2
	if i >= n or lchild >= n:
		return
	if rchild < n and arr[index] < arr[rchild]:
		index = rchild
	if lchild < n and arr[index] < arr[lchild]:
		index = lchild
	if index != i:
		(arr[index], arr[i]) = (arr[i], arr[index])
		heapify(arr, index, n)

def buildHeap(arr, n):
	lp = n // 2 - 1
	while lp > -1:
		heapify(arr, lp, n)
		lp -= 1

class Solution:

	def kLargest(self, arr, n, k):
		ans = []
		if k <= n:
			buildHeap(arr, n)
			ans.append(arr[0])
			k -= 1
			while k > 0:
				(arr[0], arr[n - 1]) = (arr[n - 1], arr[0])
				n -= 1
				heapify(arr, 0, n)
				ans.append(arr[0])
				k -= 1
		return ans


class Solution:

	def kLargest(self, arr, n, k):
		res = []
		arr.sort()
		arr.reverse()
		i = 0
		while i < k:
			popped = arr.pop(0)
			res.append(popped)
			i += 1
		return res


class Solution:

	def kLargest(self, arr, n, k):
		res = []
		arr.sort()
		arr = arr[::-1]
		return arr[0:k]


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort()
		l = []
		j = -1
		while k:
			l.append(arr[j])
			j -= 1
			k -= 1
		return l


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		s = []
		lis = []
		for i in range(n):
			heapq.heappush(s, -arr[i])
		i = 0
		while i < k:
			lis.append(-1 * heapq.heappop(s))
			i = i + 1
		lis.sort(reverse=True)
		return lis


class Solution:

	def kLargest(self, arr, n, k):
		arr = sorted(arr)
		arr.reverse()
		return arr[0:k]


class Solution:

	def kLargest(self, arr, n, k):
		arr.sort()
		sze = len(arr) - 1
		ans = []
		while k != 0:
			ans.append(arr[sze])
			sze -= 1
			k -= 1
		return ans


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		heap = []
		for i in arr:
			heapq.heappush(heap, -1 * i)
		result = []
		for i in range(k):
			result.append(-1 * heapq.heappop(heap))
		return result


class Solution:

	def kLargest(self, arr, n, k):
		from heapq import heappush, heappop
		h = []
		for i in arr:
			heappush(h, -i)
		ans = []
		while k:
			ans += [-heappop(h)]
			k -= 1
		return ans


from queue import PriorityQueue

def k_largest_element(input_arr: [], n: int, k: int):
	data_queue = PriorityQueue()
	for i in range(k):
		data_queue.put(input_arr[i])
	for i in range(k, n):
		curr_element = input_arr[i]
		worst_element = data_queue.get()
		if worst_element < curr_element:
			data_queue.put(curr_element)
		else:
			data_queue.put(worst_element)
	final_arr = []
	while len(data_queue.queue) > 0:
		final_arr.append(data_queue.get())
	return list(reversed(final_arr))

class Solution:

	def kLargest(self, arr, n, k):
		return k_largest_element(arr, n, k)


class Solution:

	def kLargest(self, arr, n, k):
		a = []
		arr.sort()
		c = 0
		for i in range(n - 1, -1, -1):
			a.append(arr[i])
			c += 1
			if c == k:
				break
		return a


from heapq import *

class Solution:

	def kLargest(self, arr, n, k):
		maxheap = []
		for i in arr:
			heappush(maxheap, -i)
		ans = []
		for i in range(k):
			ans.append(-heappop(maxheap))
		return ans


class Solution:

	def kLargest(self, arr, n, k):
		arr = sorted(arr, reverse=True)
		b = []
		n = len(arr)
		for i in range(k):
			b.append(arr[i])
		return b


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		p = arr[:k]
		heapq.heapify(p)
		for i in arr[k:]:
			q = heapq.heappop(p)
			if q < i:
				heapq.heappush(p, i)
			else:
				heapq.heappush(p, q)
		p.sort(reverse=True)
		return p


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		h = arr[:k]
		heapq.heapify(h)
		for i in range(k, len(arr)):
			if arr[i] > h[0]:
				heapq.heappushpop(h, arr[i])
		r = []
		for i in range(k):
			r.append(heapq.heappop(h))
		r.reverse()
		return r


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		heap = arr[:k]
		heapq.heapify(heap)
		for i in range(k, n):
			if arr[i] > heap[0]:
				heapq.heappop(heap)
				heapq.heappush(heap, arr[i])
		return sorted(heap, reverse=True)


from heapq import heappush, heappop

class Solution:

	def kLargest(self, arr, n, k):
		arr.sort(reverse=True)
		return arr[0:k]


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		minheap = []
		for i in arr:
			heapq.heappush(minheap, i)
			if len(minheap) > k:
				heapq.heappop(minheap)
		ans = [0 for i in range(0, k)]
		idx = k - 1
		while len(minheap) != 0:
			ans[idx] = heapq.heappop(minheap)
			idx -= 1
		return ans


import heapq

class Solution:

	def heapify(self, arr, n, i):
		smallest = i
		left = 2 * i + 1
		right = 2 * i + 2
		if left < n and arr[left] > arr[smallest]:
			smallest = left
		if right < n and arr[right] > arr[smallest]:
			smallest = right
		if smallest != i:
			(arr[smallest], arr[i]) = (arr[i], arr[smallest])
			self.heapify(arr, n, smallest)

	def buildheap(self, arr, n):
		for i in range(n // 2, -1, -1):
			self.heapify(arr, n, i)

	def kLargest(self, arr, n, k):
		self.buildheap(arr, n)
		j = n - 1
		for i in range(k):
			(arr[0], arr[j]) = (arr[j], arr[0])
			self.heapify(arr, j, 0)
			j -= 1
		res = []
		while k != 0:
			res.append(arr.pop())
			k -= 1
		return res


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		heap = []
		for num in arr:
			if len(heap) < k:
				heapq.heappush(heap, num)
			elif num > heap[0]:
				heapq.heappop(heap)
				heapq.heappush(heap, num)
		res = []
		while heap:
			res.insert(0, heapq.heappop(heap))
		return res


import heapq

class Solution:

	def kLargest(self, arr, n, k):
		l = []
		l1 = []
		for i in range(len(arr)):
			heapq.heappush(l, -arr[i])
		heapq.heapify(l)
		while k != 0:
			l1.append(-heapq.heappop(l))
			k -= 1
		return l1


import heapq

class Solution:

	def kLargest(self, array, n, k):
		array = list(map(lambda x: -x, array))
		heapq.heapify(array)
		ans = []
		for i in range(k):
			ans.append(-heapq.heappop(array))
		return ans


class Solution:

	def kLargest(self, arr, n, k):
		arr1 = []
		v = n - k
		arr.sort()
		for i in range(n - 1, v - 1, -1):
			arr1.append(arr[i])
		return arr1