LC 番外 heapsort 算法

原始教程来源：

链接

代码

class Solution:
    def sort_heap(self,nums):
        # 对heap进行排序
        self.build_heap(nums)
        for i in range(len(nums)-1,-1,-1):
            # i 和 头 互换，此时头是最大
            nums[i],nums[0] = nums[0],nums[i] 
            # 针对0位置做
            self.heapify(nums,i,0)

    def build_heap(self,nums):
        # 构造一个heap，即根节点是最大的一个完全二叉树
        n = len(nums)
        last_node = n-1
        parent = (last_node-1)//2 # 最后的父节点
        for i in range(parent,-1,-1):
            self.heapify(nums,n,i) # 处理到根为止

    def heapify(self,nums,n,i):
        # 这个函数将节点中，最大的值给捞上来
        # 出口
        if i >= n:
            return 
        c1 = 2 * i + 1 # 左孩子
        c2 = 2 * i + 2 # 右孩子
        max_i = i
        if c1 < n and nums[c1] > nums[max_i]:
            max_i = c1
        if c2 < n and nums[c2] > nums[max_i]:
            max_i = c2
        if max_i != i:
            nums[max_i],nums[i] = nums[i],nums[max_i]
            self.heapify(nums,n,max_i) # 递归，底层也做

    def findPeakElement(self, nums: List[int]) -> int:
        # 可以在这个题目中使用：https://leetcode-cn.com/leetbook/read/top-interview-questions-medium/xv4hjg/
        temp = nums.copy()
        self.sort_heap(nums)
        max_val = nums[-1]
        for i,v in enumerate(temp):
            if max_val == v:
                return i