如何通过堆排序算法高效解决堆的TOPK问题？

本文共计6811个文字，预计阅读时间需要28分钟。

这篇博客我会尽我所能讲解堆，同时详细解释堆中重要的向下和向上调整算法，以及排序中的两种实现方法，以及堆的TOPK问题。堆是什么？我们之前已经介绍过树，而堆就是一种特殊的树。

这篇博客我会尽我自己的所能讲解堆，同时详细的解释堆中重要的向下和向上调整算法，以及推排序的两种实现方法，和堆的TOPK问题。

堆是什么

我们之前已经介绍过了树，而堆就是一种完全二叉树。

这里我放一张二叉树的图

下面我来解释一下满二叉树，和完全二叉树的区别：

满二叉树是指除了叶子节点外，每个节点都有两个子节点，且所有叶子节点都在树的同一层次上。换句话说，满二叉树是一颗高度为h，且具有2^(h+1)-1个节点的二叉树。例如，下图所示的二叉树就是一颗满二叉树：

6 / \ 4 8 / \ / \ 2 5 7 9

完全二叉树是指除了最后一层外，其他所有层都被完全填充，最后一层可以有从左到右缺少一些节点，但这些节点只能出现在最后一层上，且不允许有空洞。换句话说，完全二叉树是一颗高度为h，具有2^h 至 2^(h+1)-1 个节点的二叉树，其中最后一层的节点都在最左边，不会出现在右边。举个例子，下图是一颗完全二叉树：

6 / \ 4 8 / \ / 2 5 7

在完全二叉树中，可以用数组来存储节点，存储顺序为从上到下、从左到右的顺序。这样，可以用较少的存储空间存储一颗完全二叉树。