堆和堆排序

发表于

二叉堆

二叉堆是通过递归定义的：首先二叉堆是一个完全二叉树或近似完全二叉树（这里近似完全二叉树是什么东东？）

  1. 父节点键值大于或等于（or小于或等于）子节点键值;
  2. 左右子树仍然是二叉堆。

上浮和下沉

  • 下沉
    对于根节点而言，一般是最大或最小的节点，那么如果一个不满足这个条件的序列，就需要通过一系列步骤来建立堆，下沉是其中之一。
    删除节点时，首先将最后的节点覆盖根节点，然后通过下沉操作确定合适的位置，完成删除操作。

  • 上浮
    后续插入的节点，通过上浮的操作来确定其位置。

堆化数组

将所有树枝点进行一次下沉操作，其实也可以对所有叶子节点执行上浮操作，但是对两个同双亲的叶子节点执行上浮相当于对一个树枝点进行下沉，所以选择下沉操作了。
另外，对所有树枝点进行下沉操作，可以理解为每一次都是对已经调整好的左右二叉堆添加一个根节点再进行下沉，具有递归的思想定义，但是使用叶子节点进行上浮操作的话，没有一个合理的递归思想的定义来理解，虽然也可以这么做，也应该是对的。

堆排序

每次将根节点与最后一个数交换，然后去掉最后一个节点，重新更新二叉堆，这样重复N-1次，就得到了有序的数组。

特点

最大堆得到的序列是递增的，最小堆得到的序列是递减的。

算法复杂度

建立堆时N/2次下沉操作，每次复杂度log(N),排序时经过N-1次交换，但每次恢复堆需要log(N)，所以总的复杂度仍然是N * log(N)。