# Kth Largest Element in an Array

O(n): n + k * log(n)

class Solution:
    def buildHeap(self, array):
        # Write your code here.
        firstParentIdx = (len(array)-2) // 2
        for currentIdx in reversed(range(firstParentIdx + 1)):
            self.siftDown(currentIdx, len(array)-1, array)
        return array
    
    def siftDown(self, currentIdx, endIdx, heap):
        # Write your code here.
        childOneIdx = currentIdx * 2 + 1
        while childOneIdx <= endIdx:
            childTwoIdx = currentIdx * 2 + 2 if currentIdx * 2 + 2 <= endIdx else -1
            if childTwoIdx != -1 and heap[childTwoIdx] > heap[childOneIdx]:
                idxToSwap = childTwoIdx
            else:
                idxToSwap = childOneIdx
            if heap[idxToSwap] > heap[currentIdx]:
                heap[currentIdx], heap[idxToSwap] = heap[idxToSwap], heap[currentIdx]
                currentIdx = idxToSwap
                childOneIdx = currentIdx * 2 + 1
            else:
                return
    def findKthLargest(self, nums: List[int], k: int) -> int:
        nums = self.buildHeap(nums)
        k -= 1
        while k > 0:
            nums[0], nums[len(nums)-1] = nums[len(nums)-1], nums[0]
            nums.pop(-1)
            self.siftDown(0, len(nums)-1, nums)
            k -= 1
        return nums[0]

O(nlogk): k + (n-k) * 2 * log(k)

class Solution:
    def buildHeap(self, array):
        # Write your code here.
        firstParentIdx = (len(array)-2) // 2
        for currentIdx in reversed(range(firstParentIdx + 1)):
            self.siftDown(currentIdx, len(array)-1, array)
        return array
    
    def siftUp(self, currentIdx, heap):
        # Write your code here.
        parentIdx = (currentIdx-1) // 2
        while currentIdx != 0 and heap[parentIdx] > heap[currentIdx]:
            heap[parentIdx], heap[currentIdx] = heap[currentIdx], heap[parentIdx]
            currentIdx = parentIdx
            parentIdx = (currentIdx-1) // 2
    
    def siftDown(self, currentIdx, endIdx, heap):
        # Write your code here.
        childOneIdx = currentIdx * 2 + 1
        while childOneIdx <= endIdx:
            childTwoIdx = currentIdx * 2 + 2 if currentIdx * 2 + 2 <= endIdx else -1
            if childTwoIdx != -1 and heap[childTwoIdx] < heap[childOneIdx]:
                idxToSwap = childTwoIdx
            else:
                idxToSwap = childOneIdx
            if heap[idxToSwap] < heap[currentIdx]:
                heap[currentIdx], heap[idxToSwap] = heap[idxToSwap], heap[currentIdx]
                currentIdx = idxToSwap
                childOneIdx = currentIdx * 2 + 1
            else:
                return
    def insert(self, value, heap):
        # Write your code here.
        heap.append(value)
        self.siftUp(len(heap)-1, heap)
        
    def findKthLargest(self, nums: List[int], k: int) -> int:
        k_l = self.buildHeap(nums[:k])
        
        i = k
        while i < len(nums):
            self.insert(nums[i], k_l)
            k_l[0], k_l[k] = k_l[k], k_l[0]
            k_l.pop(-1)
            self.siftDown(0, len(k_l)-1, k_l)
            i += 1
        
        return k_l[0]