堆排序是什么

概念堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]]

>=

A[i]。在数组的非降序排序中，需要使用的就是大根堆，因为根据大根堆的要求可知，最大的值一定在堆顶。

起源

1991年的计算机先驱奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德(Robert

W．Floyd）和威廉姆斯(J．Williams）在1964年共同发明了著名的堆排序算法（

Heap

Sort

)。

简介

堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得在当前无序区中选取最大（或最小）关键字的记录变得简单。

（1）用大根堆排序的基本思想

①

先将初始文件R[1n]建成一个大根堆，此堆为初始的无序区

②

再将关键字最大的记录R[1]（即堆顶）和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1n-1]和有序区R[n]，且满足R[1n-1]keys≤R[n]key

③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1n-1]调整为堆。然后再次将R[1n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1n-2]和有序区R[n-1n]，且仍满足关系R[1n-2]keys≤R[n-1n]keys，同样要将R[1n-2]调整为堆。

……

直到无序区只有一个元素为止。

（2）大根堆排序算法的基本操作：

①建堆，建堆是不断调整堆的过程，从len/2处开始调整，一直到第一个节点，此处len是堆中元素的个数。建堆的过程是线性的过程，从len/2到0处一直调用调整堆的过程，相当于o(h1)+o(h2)…+o(hlen/2)

其中h表示节点的深度，len/2表示节点的个数，这是一个求和的过程，结果是线性的O(n)。

②调整堆：调整堆在构建堆的过程中会用到，而且在堆排序过程中也会用到。利用的思想是比较节点i和它的孩子节点left(i),right(i)，选出三者最大(或者最小)者，如果最大（小）值不是节点i而是它的一个孩子节点，那边交互节点i和该节点，然后再调用调整堆过程，这是一个递归的过程。调整堆的过程时间复杂度与堆的深度有关系，是lgn的操作，因为是沿着深度方向进行调整的。

③堆排序：堆排序是利用上面的两个过程来进行的。首先是根据元素构建堆。然后将堆的根节点取出(一般是与最后一个节点进行交换)，将前面len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。堆排序过程的时间复杂度是O(nlgn)。因为建堆的时间复杂度是O(n)（调用一次）；调整堆的时间复杂度是lgn，调用了n-1次，所以堆排序的时间复杂度是O(nlgn)[2]

注意：

①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。

②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止

特点

堆排序（HeapSort）是一树形选择排序。堆排序的特点是：在排序过程中，将R[ln]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系（参见二叉树的顺序存储结构），在当前无序区中选择关键字最大（或最小）的记录

算法分析

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。

平均性能：O(NlogN)。

其他性能：由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。堆排序是就地排序，辅助空间为O(1）。它是不稳定的排序方法。（排序的稳定性是指如果在排序的序列中，存在前后相同的两个元素的话，排序前

和排序后他们的相对位置不发生变化）。

堆（英语：heap)是计算机科学中一类特殊的数据结构的统称。堆通常是一个可以被看做一棵树的数组对象。

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。

向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

扩展资料：

一、堆的算法思想

不必将值一个个地插入堆中，通过交换形成堆。假设根的左、右子树都已是堆，并且根的元素名为R。这种情况下，有两种可能：

（1） R的值小于或等于其两个子女，此时堆已完成。

（2） R的值大于其某一个或全部两个子女的值，此时R应与两个子女中值较小的一个交换，结果得到一个堆，除非R仍然大于其新子女的一个或全部的两个。这种情况下，我们只需简单地继续这种将R“拉下来”的过程，直至到达某一个层使它小于它的子女，或者它成了叶结点。

二、栈的基本算法

1、进栈（PUSH）算法

①若TOP≥n时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）。

②置TOP=TOP+1（栈指针加1，指向进栈地址）。

③S(TOP)=X，结束（X为新进栈的元素）。

2、退栈（POP）算法

①若TOP≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作②)。

②X=S(TOP)，（退栈后的元素赋给X）。

③TOP=TOP-1，结束（栈指针减1，指向栈顶）。

-堆

-栈

小张、小李效率比是1/4:1/3=3:4

小张单独做1÷7/8÷6×3/（3+4）

=1÷7/48÷3/7

=1÷1/16

=16天

小李16×3/4=12天

堆其实就是一棵完全二叉树，即若设二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边。

定义为：具有n个元素的序列（h1,h2,hn），当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,,n/2)时称之为堆。完全二叉树的根结点称为堆的顶。

可以注意到，堆仅保证元素和其子结点之间的关系，并不保证兄弟结点之间的关系。

常见的堆包括最大堆和最小堆。

最大堆，顾名思义，堆顶的键值是所有堆结点键值中最大者。套用前面讲到过的规则， 当且仅当满足（hi>=h2i,hi>=h2i+1）或（hi<=h2i,hi<=2i+1） (i=1,2,,n/2) ，所有父结点的键值均大于子结点。

由最大堆的定义，可以很容易的理解最小堆，即所有父结点的键值均小于子结点。

堆的内存形式有两种，一种是链表，一种是数组。

对于一个堆，常用的操作有两种，插入一个新的结点和删除堆顶。

向堆插入一个结点，首先要保证堆依然是一个完全二叉树，即必须保证一行（也就是一层）构建完成才能继续添加下一层的结点。这就意味着完全二叉树新增加结点的位置是唯一固定的。对应数组来说，就是在数组的末尾增加一个元素。

进一步，对这个完全二叉树进行调整，即移动父结点和子结点的相互位置关系，使其满足条件而重新成为堆。这种调整可以简单的看成是一些列的上浮（shift-up）操作。可以看看下面这个简单的图。

可以看到，所谓的shift-up，就是将新插入的结点不停的和其父结点进行比较，如果子结点的键值大于（最大堆）/小于（最小堆）其父结点，那么就对二者进行交换，因为这里是数组，所以仅需要交换结点之间的键值，直到子结点的键值不大于（最大堆）/不小于（最小堆）其父结点。

和插入新的结点类似，删除堆顶，还是首先要保证堆依然是一个完全二叉树，即必须保证一行（也就是一层）全部删除之后才能继续删除上一层的结点。这就意味着完全二叉树删除的结点的位置是唯一固定的。对应数组来说，就是删除数组末尾的元素。

删除堆顶的操作可以分为3步：

步骤1和2非常简单，执行完成之后，新的完全二叉树如图所示：

步骤3是问题的重点和难点，可以简单的看成是一些列的下沉（shift-down）操作。

对于某个结点（parent），所谓的shift-down，包括以下子步骤（这里以最大堆为例）：

以上面的堆为例：

构建堆有两种方式，一种是从无到有，也就是一个不断插入结点的过程；而另一种就是在原有完全二叉树的基础上，按照某种规则对结点进行调整。

从原理上说，从无到有的构建堆比较简单，对于每一个新增结点，对其进行插入操作，结果必然是一个堆。

在原有的完全二叉树上进行调整，稍微复杂一些，可以从最后一个非叶结点开始，对每个非叶结点进行shift-down操作。

该操作的难点在于如何找到“非叶结点”和“最后一个非叶结点”。考虑非叶结点的定义，一个结点如果 有至少一个子结点 ，那么就称其为 非叶结点 。因此，我们只要遍历所有的结点（根结点除外）的父结点，就可以遍历所有的 非叶结点 。知道了如何找到“非叶结点”，找出“最后一个非叶结点”的方法显而易见，最后一个叶结点（数组的末尾）的父结点就是“最后一个非叶结点”。

通过之前的章节，不难看出，堆操作的核心是两个步骤：shift-down和shift-up，更进一步，这两个操作都是递归的。

不仅在面试中，堆在日常工作中也经常被使用。堆经常会被作为优先队列来使用，常见于例如任务调度，数组合并等场景。

在java中，优先队列实现了堆的数据结构1。我之前的一篇文章 Java 优先队列 （PriorityQueue） 对优先队列进行了简单介绍，可以参考。

1 https://docsoraclecom/en/java/javase/11/docs/api/javabase/java/util/PriorityQueuehtml

其他参考文章：

2 最大堆（创建、删除、插入和堆排序）

3 数据结构：堆（Heap）

4 关于堆结构的详解

5 构建堆的时间复杂度

6 最大堆的插入/删除/调整/排序操作(图解+程序)（JAVA）

起始序列为14，15，30，28，5，10，

(1)因此起始堆的情况如下：

14

15 30

28 5 10

(2)假设是打算得到一个从小到大的c，所以需要建大顶堆，起始状态从下向上建堆：

第一步： 第二步：

14 30

28 30 28 14

25 5 10 25 5 10

(3)此时已经建立完了初始的堆。此时堆顶元素30即为最大元素，将堆顶元素与堆最后

一个元素进行交换，此时30是最大元素位于队尾，因此无需继续排序。所以堆如下图

所示：10 28 14 25 5

(4)此时由于除被交换到堆顶的10以外其他的都基本有序，所以自上而下建堆得到的堆

如下：

28

25 14

10 5

(5)重复（3）和（4）步骤确定了28的位置并得到堆如下：

25

10 14

5

(6)重复（3）和（4）步骤确定了25的位置并得到堆如下：

14

10 5

(7)重复（3）和（4）步骤确定了14的位置并得到堆如下：

10

5

(8)重复（3）和（4）步骤确定了10的位置,此时只有一个数5也位于了堆的第一个位置，

因此排序完成。

扩展资料：

建堆效率

n个结点的堆，高度d =log2n。根为第0层，则第i层结点个数为2^i，考虑一个元素在堆中向下移动的距离。大约一半的结点深度为d-1，不移动（叶）。四分之一的结点深度为d-2，而它们至多能向下移动一层。树中每向上一层，结点的数目为前一层的一半，而子树高度加一。

这种算法时间代价为Ο（n)

由于堆有log n层深，插入结点、删除普通元素和删除最小元素的平均时间代价和时间复杂度都是

Ο（log n）。

操作实现

在程序中，堆用于动态分配和释放程序所使用的对象。在以下情况中调用堆操作：

1事先不知道程序所需对象的数量和大小。

2对象太大，不适合使用堆栈分配器。

堆使用运行期间分配给代码和堆栈以外的部分内存。

传统上，操作系统和运行时库随附了堆实现。当进程开始时，操作系统创建称为进程堆的默认堆。如果没有使用其他堆，则使用进程堆分配块。

语言运行时库也可在一个进程内创建单独的堆。（例如，C 运行时库创建自己的堆。）除这些专用堆外，应用程序或许多加载的动态链接库 (DLL) 之一也可以创建并使用单独的堆。Win32 提供了一组丰富的 API用于创建和使用专用堆。有关堆函数的优秀教程，请参阅 MSDN 平台 SDK 节点。

-堆