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 
#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
     
  
        
Comments