堆排序(heapSort)（堆排序的比较次数）

一、堆的定义

堆排序（Heap Sort）是一种基于堆（Heap）这种数据结构的排序算法，具有 O(n \log n) 的时间复杂度。堆是一种特殊的完全二叉树，可以分为大顶堆和小顶堆：

o 大顶堆：每个节点的值都大于或等于其子节点的值，堆顶是最大值。

o 小顶堆：每个节点的值都小于或等于其子节点的值，堆顶是最小值。

什么是堆懂了么？没懂得话，认为堆就是平常看到的土堆的形状；

二、堆的数据结构，近似完全二叉树

该数组从逻辑上讲就是一个堆结构，我们用简单的公式来描述一下堆的定义就是：

树根的索引为0；

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

再加个一个小插曲，完全二叉树n/2+1到n都是叶子节点

三、堆排序

堆排序主要分为两个步骤：

1. 构建堆：将数组调整为大顶堆或小顶堆。

1、针对叶子节点之外的所有节点构成大顶堆

2、交换的节点在构成大顶堆

2. 排序过程：将堆顶元素（最大值或最小值）与末尾元素交换，然后对剩下的元素重新调整为堆，反复进行直到排序完成。

排序的规程是堆大小不断变小的过程

三、算法分析：

时间复杂度：堆排序包括建堆和排序两个操作，建堆过程的时间复杂度是 O(n)，排序过程的时间复杂度是 O(nlgn)，所以，堆排序整体的时间复杂度是 O(nlgn)。

空间复杂度： 因为堆排序是就地排序（原址排序），空间复杂度为常数：O(1)

稳定性：不稳定。因为在堆的调整过程中，元素进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的元素就可能出现排在后面的元素被交换到前面来的情况。

概括：简单来点说，就是把数组构成一个堆，取堆顶元素，交换到数组末尾；依次循环，直到数组为有序数组

四、优先队列

优先队列（Priority Queue）是一种特殊的队列数据结构，其中每个元素都带有一个优先级。与普通队列（FIFO）不同，优先队列的元素出队顺序取决于优先级的高低，而不是它们进入队列的顺序。

1、插入元素

放到数组尾部

向上交换heapify

2、取出元素

取出数组头部

尾部元素放到头部

向下heapify

3、修改