AlgoDesign

K largest in max heap

1from heapq import *
2class Solution:
3    def kLargestMaxHeap(self, heap, k):
4        res, maxHeap = [], [(-heap[0], 0)]
5
6        for _ in range(k):
7            val, i = heappop(maxHeap)
8            val = -val
9            res.append(val)
10
11            leftIndex = i * 2 + 1
12            if leftIndex < len(heap): heappush(maxHeap, (-heap[leftIndex], leftIndex))
13            rightIndex = i * 2 + 2
14            if rightIndex < len(heap): heappush(maxHeap, (-heap[rightIndex], rightIndex))
15        
16        return res