1 二叉堆

  • 二叉堆本质上是一种完全二叉树，它分为两个类型：
    • 最大堆：最大堆任何一个父节点的值，都大于等于它的左右孩子节点的值。
    • 最小堆：最小堆任何一个父节点的值，都小于等于它的左右孩子节点的值。
  • 二叉堆的根节点叫做堆顶。

  • 最大堆和最小堆的特点，决定了最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶是整个堆中的最小元素。

    2 堆的自我调整

    插入节点

    删除节点

    构建二叉堆

  • 构建二叉堆，也就是把一个无序的完全二叉树调整为二叉堆，本质上就是让所有非叶子节点依次下沉。

    3 堆的代码实现

  • 二叉堆虽然是一棵完全二叉树，但它的存储方式并不是链式存储，而是顺序存储。换句话说，二叉堆的所有节点都存储在数组当中。

  • 怎么来定位孩子节点的父节点或者父节点的孩子节点呢？

    堆排序

  • 当我们删除一个最大堆的堆顶（并不是完全删除，而是替换到最后面），经过自我调节，第二大的元素就会被交换上来，成为最大堆的新堆顶。

image.png

  1. class Solution:
  2.     def findKthLargest(self, nums, k):
  3.         # 堆排
  4.         self._k = len(nums) - k
  5.         return self.heapsort(nums)
  7.     def heapsort(self, nums):
  8.         self.build_heap(nums)
  9.         for i in range(len(nums)-1, self._k-1, -1):
  10.             nums[i], nums[0] = nums[0], nums[i]
  11.             # 这里要排除最后一个元素
  12.             self.max_heapify(nums, 0, i)
  13.         return nums[self._k]
  15.     def build_heap(self, nums):
  16.         length = len(nums)
  17.         for i in range(((length-1) // 2), -1, -1):
  18.             # 从最后一个节点的父节点开始向上调整
  19.             self.max_heapify(nums, i, length)
  21.     def max_heapify(self, nums, i, length):
  22.         left = i * 2 + 1
  23.         right = i * 2 + 2
  24.         if left < length and nums[left] > nums[i]:
  25.             largest = left
  26.         else:
  27.             largest = i
  28.         if right < length and nums[right] > nums[largest]:
  29.             largest = right
  30.         if largest != i:
  31.             nums[i], nums[largest] = nums[largest], nums[i]
  32.             # 子树也要调整
  33.             self.max_heapify(nums, largest, length)

复杂度分析

  • 假设二叉堆总共有 n 个元素，那么向下调整的最坏时间复杂度就等同于二叉堆的高度，也就是P2 堆排序 - 图2。
  • 我们来回顾一下堆排序算法的步骤：
      1. 把无序数组构建成二叉堆。
      1. 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶。
    • 第一步，把无序数组构建成二叉堆，假设满二叉树高为 h，有P2 堆排序 - 图3个节点。那么建堆过程中，第h层的P2 堆排序 - 图4个节点最多交换 0 次即可调整为堆，第 (h-1) 层的P2 堆排序 - 图5个节点最多交换 1 次，……，第1层的1个节点最多交换 (h-1) 次。因此时间复杂度为P2 堆排序 - 图6。
    • 第二步，需要进行n-1次循环。每次循环调用一次 downAdjust 方法，所以第二步的计算规模是 P2 堆排序 - 图7，时间复杂度为P2 堆排序 - 图8。
    • 两个步骤是并列关系，所以整体的时间复杂度同样是P2 堆排序 - 图9。