# minHeap: Top K Elements: Find k largest numbers in array Python

Tue Aug 09 2022 23:23:42 GMT+0000 (Coordinated Universal Time)

```#solution involving minHeap
#Strategy:
#1) Take out the smallest number from the heap, and
#2) Insert the larger number into the heap.
#3) repeat
#This will ensure that we always have ‘K’ largest numbers in the heap. The most efficient way to repeatedly find the smallest number among a set of numbers will be to use a min-heap.

#Big O n log k. Space: O (k)

from heapq import *
#this is a heap library. look at relevant functions: https://docs.python.org/3/library/heapq.html

def find_k_largest_numbers(nums, k):
minHeap = []
# put first 'K' numbers in the min heap
for i in range(k):
heappush(minHeap, nums[i])

# go through the remaining numbers of the array, if the number from the array is bigger than the
# top(smallest) number of the min-heap, remove the top number from heap and add the number from array
for i in range(k, len(nums)):
if nums[i] > minHeap[0]:
#heapop removes smallest element in heap
heappop(minHeap)
heappush(minHeap, nums[i])

# the heap has the top 'K' numbers
return minHeap

#brute force approach has big O of n log N
def find_k_largest_numbers(nums, k):
result = []

nums.sort()
nums_length_index = len(nums) - 1 - k

for i in range(nums_length_index + 1, len(nums)):
result.append(nums[i])

return result

find_k_largest_numbers([3, 1, 5, 12, 2, 12], 3) # will result in [5, 12, 12]

#if you dont want duplicates you can do the following:
def find_k_largest_numbers(nums, k):
result = []

nums.sort()
nums_set = set(nums)
nums_length_index = len(nums_set) - 1 - k

for i in range(nums_length_index + 1, len(nums_set)):
result.append(nums[i])

return result```
content_copyCOPY

Whenever dealing with top k elements, think of heaps whether min or max heap

https://www.educative.io/courses/grokking-the-coding-interview/RM535yM9DW0