class Solution:
    """
    @param nums: an integer array
    @param k: An integer
    @return: the top k largest numbers in array
    """
    def topk(self, nums, k):
        # write your code here
        if nums == None or k > len(nums):
            return sorted(nums)
        result = [0 for i in range(k)]
        for i in range(k):
            self.heapInsert(result, nums[i], i)
        for i in range(k, len(nums)):
            if result[0] < nums[i]:
                result[0] = nums[i]
                self.heapify(result, 0, k)
        return sorted(result, reverse=True)

    # 需要使用小顶堆
    # 堆顶是最小元素
    # nums[0]是堆顶
    def heapInsert(self,nums, value, index):
        nums[index] = value
        while index != 0:
            parent = (index - 1) // 2
            if nums[parent] > nums[index]:
                nums[parent], nums[index] = nums[index], nums[parent]
                index = parent
            else:
                break
    def heapify(self, nums, index , heapsize):
        left = 2 * index + 1
        right = 2 * index + 2
        smallest = index
        while left < heapsize:
            if nums[left] < nums[index]:
                smallest = left
            if right < heapsize and nums[right] < nums[smallest]:
                smallest = right
            if smallest != index:
                nums[smallest] , nums[index] = nums[index] , nums[smallest]
            else:
                break
            index = smallest
            left = index * 2 + 1
            right = index * 2 + 2

f850fe0558d051419fc04e36d40f48ea8932a366
class Solution:
    <mask token>
    <mask token>
    <mask token>
    <mask token>

class Solution:
    <mask token>

    def topk(self, nums, k):
        if nums == None or k > len(nums):
            return sorted(nums)
        result = [(0) for i in range(k)]
        for i in range(k):
            self.heapInsert(result, nums[i], i)
        for i in range(k, len(nums)):
            if result[0] < nums[i]:
                result[0] = nums[i]
                self.heapify(result, 0, k)
        return sorted(result, reverse=True)
    <mask token>

    def heapify(self, nums, index, heapsize):
        left = 2 * index + 1
        right = 2 * index + 2
        smallest = index
        while left < heapsize:
            if nums[left] < nums[index]:
                smallest = left
            if right < heapsize and nums[right] < nums[smallest]:
                smallest = right
            if smallest != index:
                nums[smallest], nums[index] = nums[index], nums[smallest]
            else:
                break
            index = smallest
            left = index * 2 + 1
            right = index * 2 + 2

class Solution:
    <mask token>

    def topk(self, nums, k):
        if nums == None or k > len(nums):
            return sorted(nums)
        result = [(0) for i in range(k)]
        for i in range(k):
            self.heapInsert(result, nums[i], i)
        for i in range(k, len(nums)):
            if result[0] < nums[i]:
                result[0] = nums[i]
                self.heapify(result, 0, k)
        return sorted(result, reverse=True)

    def heapInsert(self, nums, value, index):
        nums[index] = value
        while index != 0:
            parent = (index - 1) // 2
            if nums[parent] > nums[index]:
                nums[parent], nums[index] = nums[index], nums[parent]
                index = parent
            else:
                break

    def heapify(self, nums, index, heapsize):
        left = 2 * index + 1
        right = 2 * index + 2
        smallest = index
        while left < heapsize:
            if nums[left] < nums[index]:
                smallest = left
            if right < heapsize and nums[right] < nums[smallest]:
                smallest = right
            if smallest != index:
                nums[smallest], nums[index] = nums[index], nums[smallest]
            else:
                break
            index = smallest
            left = index * 2 + 1
            right = index * 2 + 2

class Solution:
    """
    @param nums: an integer array
    @param k: An integer
    @return: the top k largest numbers in array
    """

    def topk(self, nums, k):
        if nums == None or k > len(nums):
            return sorted(nums)
        result = [(0) for i in range(k)]
        for i in range(k):
            self.heapInsert(result, nums[i], i)
        for i in range(k, len(nums)):
            if result[0] < nums[i]:
                result[0] = nums[i]
                self.heapify(result, 0, k)
        return sorted(result, reverse=True)

    def heapInsert(self, nums, value, index):
        nums[index] = value
        while index != 0:
            parent = (index - 1) // 2
            if nums[parent] > nums[index]:
                nums[parent], nums[index] = nums[index], nums[parent]
                index = parent
            else:
                break

    def heapify(self, nums, index, heapsize):
        left = 2 * index + 1
        right = 2 * index + 2
        smallest = index
        while left < heapsize:
            if nums[left] < nums[index]:
                smallest = left
            if right < heapsize and nums[right] < nums[smallest]:
                smallest = right
            if smallest != index:
                nums[smallest], nums[index] = nums[index], nums[smallest]
            else:
                break
            index = smallest
            left = index * 2 + 1
            right = index * 2 + 2

class Solution:
    """
    @param nums: an integer array
    @param k: An integer
    @return: the top k largest numbers in array
    """
    def topk(self, nums, k):
        # write your code here
        if nums == None or k > len(nums):
            return sorted(nums)
        result = [0 for i in range(k)]
        for i in range(k):
            self.heapInsert(result, nums[i], i)
        for i in range(k, len(nums)):
            if result[0] < nums[i]:
                result[0] = nums[i]
                self.heapify(result, 0, k)
        return sorted(result, reverse=True)

    # 需要使用小顶堆
    # 堆顶是最小元素
    # nums[0]是堆顶
    def heapInsert(self,nums, value, index):
        nums[index] = value
        while index != 0:
            parent = (index - 1) // 2
            if nums[parent] > nums[index]:
                nums[parent], nums[index] = nums[index], nums[parent]
                index = parent
            else:
                break
    def heapify(self, nums, index , heapsize):
        left = 2 * index + 1
        right = 2 * index + 2
        smallest = index
        while left < heapsize:
            if nums[left] < nums[index]:
                smallest = left
            if right < heapsize and nums[right] < nums[smallest]:
                smallest = right
            if smallest != index:
                nums[smallest] , nums[index] = nums[index] , nums[smallest]
            else:
                break
            index = smallest
            left = index * 2 + 1
            right = index * 2 + 2
