leetcode

commit 574556ef3e31cf13453b8b54397410cfc1c01c36
parent 4051ad7047233180411f610e43be80af6a13695d
Author: Andrew Laack <andrew@laack.co>
Date:   Thu,  3 Jul 2025 10:31:38 -0500

Completed kth largest element in a stream

Diffstat:
A
kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV3.py
 | 
88
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 88 insertions(+), 0 deletions(-)
diff --git a/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV3.py b/kth-largest-element-in-a-stream/kth-largest-element-in-a-streamV3.py
@@ -0,0 +1,88 @@
+# TODO:
+# I still need to implement heappush and heappop.
+
+from heapq import heappush, heappop
+
+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._compare_three(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):
+        return heappop(self.nums)
+
+    def push(self, val):
+        heappush(self.nums, val)
+
+    def _compare_three(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._compare_three(nums, min_index)
+        
+        return
+
+    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]