https://leetcode.com/problems/kth-largest-element-in-a-stream/ so i was solving this leetcode question and i am getting the last testcase wrong, i commented and simplified every line of code, can someone help me find the error here?
#🔒 IMPLEMENTATION OF BINARY HEAP (using array)
vagrant quiver
coral swiftBOT
https://leetcode.com/problems/kth-largest-element-in-a-stream/ so i was solving ...
@vagrant quiver
Python help channel opened
vagrant quiver
THIS IS MY ENTIRE CODE
i will post it in small forms, since i cant attach a file here i think
def heapush(self,val):
#append the element at the last position of the heap
self.nums.append(val)
#take the index of the last position
elementpos=len(self.nums)-1
#check if the inserted element is smaller than it's successive parents
#if it is, then keep on swapping them
while(elementpos!=0):
#parent of an i-th element in the heap is at floor(i/2)th position
parentpos = elementpos//2
#if the element is smaller than its parent
#swap it with its parent so the element moves up in the minheap
if self.nums[parentpos]>self.nums[elementpos]:
self.swap(parentpos,elementpos)
#repeat this process and comapre with successive parents
#until either it is no longer smaller
#or it reaches the root position (i=0)
elementpos=elementpos//2
else:
#it is no longer smaller
#hence current position is intended position of the element
#break out
break
this is heapush
def _heapify(self):
#start heapifying the elements from bottom to top
#all leaf nodes have no children, they are already heap
#so we can start from the middle of the array
#array is the abstract representation of heap
for i in range(len(self.nums)//2,-1,-1):
self.make_it_heap(i)``` this is heapify def make_it_heap(self,i):
#binary heap is a complete binary tree, it has either leftchild, both children, or no child
rightpos=2*i+2
leftpos=2*i+1
#checking if left child exists
if leftpos>=len(self.nums):
#left child doesnt exist, leaf node is already a heap
return
#checking if rightchild exists
if rightpos < len(self.nums):
#rightchild exists and smaller than left child
if self.nums[rightpos]<self.nums[leftpos]:
#right child smaller than parent too
if self.nums[rightpos]<self.nums[i]:
#swap rightchild with parent, so bigger parent moves down in minHeap
self.swap(rightpos,i)
#after swapping repeat this process for the new position of the parent
self.make_it_heap(rightpos)
#leftchild is smaller than rightchild
#so we check its smaller than parent too
elif self.nums[leftpos]<self.nums[i]:
#swap left child with parent
self.swap(leftpos,i)
#repeat the process on the new position of the parent
self.make_it_heap(leftpos)
#rightchild doesn't exist
#but leftchild does
#so we check if left child is smaller than parent
elif self.nums[leftpos]<self.nums[i]:
#if it is, then swap it with the parent
self.swap(leftpos,i)
#continue this process for the new position of the parent
self.make_it_heap(leftpos)
#return if the given element is already adjusted
return
``` the make_it_heap function def heapop(self):
#heap pops the top most element
k=self.nums[0]
#put the last element at top place
#overwriting the top element (deletion)
self.nums[0]=self.nums[-1]
#and pop the last element (reducing heap's size) in O(1)
self.nums.pop(-1)
#now with the last element at the top
#we need to heapify the heap by adjusting the top element
#such that it moves down if its big
self.make_it_heap(0)
#return the popped element
return k
``` this is heapop def swap(self,a, b):
self.nums[a], self.nums[b] = self.nums[b], self.nums[a]``` and this is swapclass KthLargest:
def __init__(self, k: int, nums: List[int]):
self.k=k
self.nums=nums
self._heapify()
while(k<len(self.nums)):
self.heapop()
print(self.nums)
def add(self, val: int) -> int:
self.heapush(val)
if len(self.nums)>self.k:
self.heapop()
return self.nums[0]``` these are the functions i am supposed to be using to solve this problemconstructor and add
i am stuck on the last test case, but its really big so i cant make anything out of it
this is the output vs the expected
round sapphire
i will post it in small forms, since i cant attach a file here i think
!paste
coral swiftBOT
vagrant quiver
bumo
coral swiftBOT
Python help channel closed