python 最小堆最大堆

概述堆本质是完全二叉树，最小堆要求节点元素不大于左右叶子节点元素，最大堆要求节点元素不小于左右叶子节点元素。下面通过例子来讲解最大堆。给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序。首先根据该数组元素构建一个完全二叉树，得到根据最大堆的定义要求，我们需要让节点

堆本质是完全二叉树，最小堆要求节点元素不大于左右叶子节点元素，最大堆要求节点元素不小于左右叶子节点元素。

下面通过例子来讲解最大堆。

给定一个列表array=[16,7,3,20,17,8]，对其进行堆排序。首先根据该数组元素构建一个完全二叉树，得到

根据最大堆的定义要求，我们需要让节点元素不小于左右叶子节点元素，所以我们从最后一个非叶节点开始依次向上调整元素位置。
构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：
第一步: 初始化大顶堆(从最后一个有子节点开始往上调整最大堆)

20和16交换后导致16不满足堆的性质，因此需重新调整

这就得到了初始堆。

第二步: 堆顶元素R[1]与最后一个元素R[n]交换，交换后堆长度减一

第三步: 重新调整堆。此时3位于堆顶不满堆的性质，则需调整继续调整(从顶点开始往下调整)

重复上面的步骤:

请特别特别注意: 初始化大顶堆时 是从最后一个有子节点开始往上调整最大堆。而堆顶元素(最大数)与堆最后一个数交换后，需再次调整成大顶堆，此时是从上往下调整的。

class Solution:    def max_heAPIfy(self, heap, root, heap_len):        pos = root        while pos * 2 + 1 < heap_len:            l,r = pos * 2 + 1, pos * 2 + 2            if heap_len <= r or heap[r] < heap[l]:                new = l            else:                new = r            if heap[pos] < heap[new]:                heap[pos], heap[new] = heap[new], heap[pos]                pos = new             else:                break    def build_heap(self, heap):        for i in range(len(heap) - 1, -1, -1):            self.max_heAPIfy(heap, i, len(heap))    def heap_sort(self, nums):        self.build_heap(nums)        for i in range(len(nums) - 1, -1, -1):            nums[i], nums[0] = nums[0], nums[i]            self.max_heAPIfy(nums, 0, i)                def sortArray(self, nums: List[int]) -> List[int]:        self.heap_sort(nums)        return nums

总结

以上是内存溢出为你收集整理的python 最小堆最大堆全部内容，希望文章能够帮你解决python 最小堆最大堆所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。