215. Kth Largest Element in an A

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

import heapq
class Solution(object):
    def findKthLargest(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        def partition(nums,l,r):
            privot = nums[r]
            i = l-1
            for j in range(l,r):
                if nums[j]  >= privot:
                    i += 1
                    nums[i],nums[j] = nums[j],nums[i]
            nums[i+1],nums[r] = nums[r],nums[i+1]
            return i+1
        l = 0
        r = len(nums) -1
        while True:
            privot_index = partition(nums,l,r)
            if privot_index == k-1:return nums[k-1]
            elif privot_index < k-1:
                l = privot_index + 1
            else:
                r = privot_index -1

def heap_sort(self,nums,k):
        for i in range(len(nums) // 2 - 1,-1,-1):
            self.heap_adjust(nums,i,len(nums))
        cnt = 0
        for i in range(len(nums)-1,0,-1):
            self.heap_swap(nums,0,i)
            cnt += 1
            if cnt == k:
                return nums[i]
            self.heap_adjust(nums,0,i)
        
        return nums[0]
    def heap_adjust(self,nums,start,length):
        tmp = nums[start]
        k = start * 2 + 1
        while k < length:
            left = start * 2 + 1 
            right = left + 1
            
            if right < length and nums[right] > nums[left]:
                k = right
            if nums[k] > tmp:
                nums[start] = nums[k]
            else:
                break
            k = k * 2 + 1
        nums[start] = tmp
        
    def heap_swap(self,nums,i,j):
        nums[i],nums[j] = nums[j],nums[i]
        return nums