leetcode

commit e4a43d6ce64312d5165af31765e0ea701a6c4445
parent b4d9b4612cabe498885a393547080c5d24a20efd
Author: Andrew Laack <andrew@laack.co>
Date:   Fri,  4 Jul 2025 10:20:32 -0500

Completed kth largest element in a stream

Diffstat:
A
kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV5.py
 | 
100
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 100 insertions(+), 0 deletions(-)
diff --git a/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV5.py b/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV5.py
@@ -0,0 +1,100 @@
+class Heap:
+    def __init__(self, nums):
+        if nums is None:
+            self.nums = []
+            return
+
+        if len(nums) <= 1:
+            self.nums = nums
+            return
+        
+        self.nums = self._make_heap(nums, 0)
+    
+    def _make_heap(self, nums, index):
+        if not self._is_leaf(nums, index):
+            self._make_heap(nums, self._left_child(index))
+            self._make_heap(nums, self._right_child(index))
+        else:
+            return
+        
+        self._heapify_down(nums,index)
+        return nums
+
+    def _left_child(self, index):
+        return (index * 2) + 1
+    
+    def _right_child(self, index):
+        return (index * 2) + 2
+    
+    def pop(self):
+        nums = self.nums
+        nums[0] = nums[-1]
+        ret_val = nums.pop()
+
+        if len(nums) > 1:
+            self._heapify_down(nums, 0)
+        
+        return ret_val
+
+    def push(self, val):
+        self.nums.append(val)
+        self._heapify_up(self.nums, len(self.nums) - 1)
+
+    def _heapify_down(self, nums, index):
+        """Compare and move pair of three to be arranged correctly. Assume index is root."""
+        
+        root = index
+        left = self._left_child(index)
+        right = self._right_child(index)
+
+        min_index = root
+
+        if nums[left] < nums[min_index]:
+            min_index = left
+        if len(nums) > right and nums[right] < nums[min_index]:
+            min_index = right
+        
+        if min_index != index:
+            temp = nums[root]
+            nums[root] = nums[min_index]
+            nums[min_index] = temp
+            if not self._is_leaf(nums, min_index):
+                self._heapify_down(nums, min_index)
+        
+        return
+
+    def _heapify_up(self, nums, index):
+        if index == 0:
+            return
+
+        parent = (index - 1) // 2
+        if nums[index] < nums[parent]:
+            nums[index], nums[parent] = nums[parent], nums[index]
+            self._heapify_up(nums, parent)
+
+    def _is_leaf(self, nums, index):
+        
+        if len(nums) <= (index * 2) + 1:
+            return True
+        
+        return False
+
+class KthLargest:
+
+    def __init__(self, k: int, nums: List[int]):
+
+        heap = Heap(nums)
+        self.heap = heap
+        self.k = k
+        self.prune()
+
+    def prune(self):
+        k = self.k
+        heap = self.heap
+        while len(heap.nums) > k:
+            heap.pop()
+
+    def add(self, val: int) -> int:
+        self.heap.push(val)
+        self.prune()
+        return self.heap.nums[0]