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


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

Saved by @bryantirawan #python #heap #top #k #max

#solution involving minHeap 
#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 
      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_length_index = len(nums) - 1 - k 

  for i in range(nums_length_index + 1, len(nums)): 
  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_set = set(nums)
  nums_length_index = len(nums_set) - 1 - k 

  for i in range(nums_length_index + 1, len(nums_set)): 
  return result

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