跳到主要内容

堆排序

很久没接触过堆排序, 再次不记得详细定义用法. 在网上搜了一下如何构建堆, 看来看去都没有当年了解时候的清晰, 最后终于搜到Sedgewick的算法解析, 就是当年学习时候理解的思路, 一下子豁然开朗. 有时候算法看起来复杂, 其实是没有找到一个合理理解的方式.

有几个刚才的疑惑点, 看完之后重新清晰

  • 堆排序不关注左右两个节点之间的大小, 只关心上下级
  • 堆一般是用列表作为底层数据存储的, 堆是完全二叉树, 只有最后一层节点的数据铺不满, 其他层级的元素数量都是上个层级的两倍.
    • 在列表中index为k的元素, 其下级为[2k, 2k+1]. 考虑index从0开始, 则index k的下级为[2k + 1, 2k + 2], 其实就是 [(k + 1) 2 - 1, (k + 1) 2 - 1 + 1] = [2k + 1, 2k + 2]. 纯靠思考很难推导, 从例子看比较直接. 后面只考虑index从0开始的计算.
    • 比如indx为 0, 下级为 1, 2; index为 1, 下级为 3, 4; index为 2, 下级为 5, 6.
    • 反过来index为k的元素, 其上级为 (k - 1) // 2
  • 堆排序有两个关键点, swim上浮和sink下沉, 理解清楚就很方便.
    • swim: 插入新元素的时候, 直接放在最后一个元素的位置上, 然后不断的跟上级比较, 将上级往下替换, log(n)就可以实现一个数字的插入
    • sink: 从堆里拿走最小/最大元素的时候, 只需要把堆顶拿走, 然后把队列最尾的元素放到堆顶, 一个一个的与下一层级做对比. 毕竟是从最下层级上来的, 肯定能够沉下去到合适的位置. 跟下一层级对比的时候, 下一层级有两个元素, 需要跟里面最小的元素做对比(最小堆), 以便能够把两个里面最小的元素替换到上一层级. 这个复杂度明显也是logN级别.
  • 构建堆的思路, 可以通过不停的加入新节点swim来实现.
  • 成功构建一个堆, 其实并不算完成了堆排序, 还需要逐次将堆顶元素吐出来放到新列表里, 才算是完成了排序. 构建堆的复杂度是NlogN, 吐出来每一个堆顶元素的复杂度是logN, 所有的遍历完是NlogN, 因此总的堆排序复杂度是NLogN.
  • 堆排序有两种堆, 最小堆和最大堆, 取决于定点是最大值还是最小值. 据说python的heapq库只用最小堆, 因此要实现最大堆的效果, 可以先把数字取反, 比如正数转换为负数.
  • 获取topK的元素, 可以不断的取走堆顶元素, 复杂度就是kLogN.
  • 如果要在超大数据序列里快速获取前k个元素, 就不能维持一整个堆了, 只能维持k个元素的堆. 问题是堆里的前k个index的元素, 其实并不是最小的前k个数字, 毕竟同一层级的左右节点之间并没有大小关系. 这时候需要用逆向思维, 比如要求前k个最大的元素, 那其实应该维持一个数量为k的最小堆, 而不是最大堆.堆顶的元素就是k个数字里面最小的, 其他数字肯定比当前数字大. 这时候来新的数字, 跟堆顶比较, 如果比堆顶小, 那可以直接扔了; 如果比堆顶元素大, 说明可以放到这k个最大元素里, 把堆顶元素扔掉, 然后放到堆顶开始sink排序即可. 复杂度其实是NlogK. 这种场景适合在流式数据里获取前100榜单之类的场景.
  • 一般做算法题并不会要求从头构建堆, 直接使用python的heapq模块即可. heapify(list)可以实现堆, 然后逐次heap.heappop吐出堆顶元素实现排序. heap.nLargest(k)可以直接获取最大/最小的前k个元素.

Understanding how to create a heap in Python

https://stackoverflow.com/questions/12749622/understanding-how-to-create-a-heap-in-python

https://algs4.cs.princeton.edu/24pq/

The heap is represented internally in an array where if a node is at k, it's children are at 2k and 2k + 1. The first element of the array is not used, to make the math more convenient.

To add a new element to the heap, you append it to the end of the array and then call swim repeatedly until the new element finds its place in the heap.

To delete the root, you swap it with the last element in the array, delete it and then call sink until the swapped element finds its place.

swim(k):
  while k > 1 and less(k/2, k):
    exch(k, k/2)
    k = k/2

sink(k):
  while 2*k <= N:
    j = 2*k
    if j < N and less(j, j+1):
      j++
    if not less(k, j):
      break
    exch(k, j)
    k = j
created at 2023-09-12