堆与堆排序

1. 什么是“堆”？如何存储一个堆？

“堆”是一种特殊的树，它满足两个条件：①堆是完全二叉树；②堆中任意节点都大于等于（或小于等于）其左右子节点。前者称为“大碓顶”，后者称为“小堆顶”。

用数组来存储完全二叉树是非常节省空间的，因此我们用数组来存储“堆”。

• 如果下标从 0 开始，假设父节点下标为 i，则左子节点是 2*i+1，右子节点是 2*i+2；而假设子节点的下标为 i，那么父节点的下标为(i-1)/2

• 如果下标从 1 开始，假设父节点为 i，则左子节点是 2*i，右子节点是 2*i+1。而假设子节点的下标为 i，那么父节点的下标为 i/2

2. “往堆中插入一个元素”和“删除堆顶元素”

堆的两个操作：“往堆中插入一个元素”和“删除堆顶元素”

插入：我们将待插入元素放到数组的下一个空闲位置，然后自下而上进行堆化。堆化操作，即 与父节点比较，如果大于父节点，则交换。

删除堆顶元素：我们用数组的最后一个元素来替代堆顶元素，然后自上而下进行堆化。

3. “往堆中插入一个元素”和“删除堆顶元素”的时间复杂度

插入和删除的主要逻辑是堆化，而对于一个包含 n 个节点的完全二叉树，树的高度不会超过 。堆化的时间复杂度和树的高度成正比，因此往堆中插入一个元素和删除堆顶元素的时间复杂度都是 O(logN)。

4. 堆排序。

借助“堆”这种数据结构实现的排序算法，就叫堆排序。堆排序包括两个步骤：建堆和排序。

建堆：将待排序数组原地建成一个堆。所谓原地，即在原数组上进行操作，不借助另一个数组。

建堆有两个思路：

一个是借助插入的思想，即，原始堆元素是[0]，然后将[1,n-1]元素依次插入堆；这是自下而上的思路。

另一个思路是，依次对所有的非叶子节点进行自上而下堆化。——如果数组下标从 0 开始，则(arr.length-1-1)/2 为最后一个叶子节点的父节点。// arr.length-1 为最后一个叶子节点的下标。

排序：将堆顶元素与数组[--n]进行交换，然后对堆顶元素进行自上而下堆化；

5. 堆排序的复杂度分析：

结论：时间复杂度为 O(NlogN)、原地排序、不稳定的排序算法

分析：

堆排序分为建堆和排序：

建堆是依次对每一个非叶子节点进行自上而下的堆化，因此，将每个非叶子节点的高度求和，得出的就是建堆的时间复杂度。

由于叶子节点不需要堆化，因此下图省去了高度 0。

对每个非叶子节点的高度求和：

将 S1*2，得到 S2，然后将 S2 与 S1 进行错位相减，得到 S

因为 h=log2N ，代入公式 S，就能得到 S=O(n)，所以，建堆的时间复杂度就是 O(n)。

排序：

排序过程类似于“删除堆顶元素”的操作。删除堆顶元素的时间复杂度是 O(logN)，因此，排序的时间复杂度是 O(NlogN).

堆排序的时间复杂度由建堆和排序两部分的时间复杂度构成，因此，堆排序整体的时间复杂度就是 O(nlogn)

由于在排序过程，存在将堆的最后一个节点跟堆顶节点互换的操作，所以就有可能改变值相同数据的原始相对顺序。因此堆排序是不稳定的排序算法。

在整个堆排序的过程中，都只需要极个别临时存储空间，所以堆排序是原地排序算法。