python将一个列表调整为大根堆模板

本文主要是介绍python将一个列表调整为大根堆模板，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

有的时候需要将一个列表调整为一个大根堆或者小根堆，我们其实可以从n = len(nums) // 2的位置一直到下标为0的位置逆序开始从上到下进行调整（将数组看成是一棵完全二叉树），将列表调整为小根堆或者是大根堆其实是在循环比较当前根节点的值与左右孩子节点调整比较的符号即可，下面是将列表调整为大根堆的代码模板：

from typing import List
import random


class Solution:
    # 从上到下进行调整
    def makeToHeap(self, nums: List[int], low: int, high: int):
        i = low
        j = 2 * i + 1
        while j <= high:
            # 调整下面nums[j]与nums[j + 1]比较的符号可以调整为小根堆
            if j + 1 < len(nums) and nums[j] < nums[j + 1]: j += 1
            if nums[i] < nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
                i = j
                j = 2 * i + 1
            else:
                break


if __name__ == "__main__":
    # 从控制台输入n
    n = int(input())
    nums = list()
    for i in range(n):
        # 生成0~n * 10的随机数
        nums.append(random.randint(0, n * 10))
    i = n // 2
    while i >= 0:
        # 由上到下进行调整为大根堆
        Solution().makeToHeap(nums, i, n - 1)
        i -= 1
    print(nums)

这篇关于python将一个列表调整为大根堆模板的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！