堆排序小根堆是怎么调整顺序(堆排序默认是小根堆还是大根堆)

对元素序列如何进行堆排序

首先说一个知识点,就是用数组操作二叉树(把堆看成二叉树容易理解)

一个数组a[n], a[0]不考虑舍弃,a[1]为根节点那么,a[i]的两个孩子节点就是a[2i]和a[2i+1] (不理解的话自己做下实验),好了那么k[i]=k[2i]且k[i]=k[2i+1](1=i= n）,当然,这是小根堆,大根堆则换成=号.

用小根堆排序的基本思想(用小根堆排序其排序结果是递减有序的,大根堆排序是递增有序)

先将初始数组k[1..n]建成一个小根堆

此堆为初始的无序区再将最小的记录k[1]（即堆顶）和无序区的最后一个记录k[n]交换,由此得到新的无序区k[1..n-1]和有序区k[n],且满足k[1..n-1]=k[n]

由于交换后新的根节点k[1]可能违反堆性质,故应将当前无序区k[1..n-1]调整为堆.然后再次对k[1..n-1]进行上面重复的操作.直到无序区只有一个元素为止.那么排序也就算结束了.

这就是堆排序的思想

你的题目上说的是原始数据构成的初始堆

7 ?3 5 9 1 12 实际上是这样的

? ? ? ? 7

? ? 3 ? ? ?5

9 ? 1 ? ? ? ?12

5和12比较不变,9,1和3比较调换1和3的位置1,5和7比较调换1和7的位置则变成这样

? ? ? ? 1

? ? 7 ? ? ?5

9 ? 3 ? ? ? ?12

还不满足小根堆继续比较9,3和7比较替换3和7的位置3,5和1比较不用换

? ? ? ? 1

? ? 3 ? ? ?5

9 ? 7 ? ? ? ?12

满足小根堆了,所以初始堆为1,3,5,9,7,12(选B)

还不懂的话这里有个动态模拟过程

堆排序是什么

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

=

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

【起源】

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

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

Heap

Sort

)。

【简介】

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

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

①

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

②

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

③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-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[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系（参见二叉树的顺序存储结构），在当前无序区中选择关键字最大（或最小）的记录

【算法分析】

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

平均性能：O(N*logN)。

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

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

数据结构：堆排序：看图，在图中最上面那一排中的第三个，不是应该897先和503交换吗？

小根堆的排序方法是:

循环将待处理节点i与其子节点三个中最大的值调整整到待i处,然后将它放入有序部.直到无序部分只有一个节点0.

等处理节点从堆一半开始,简单的说就是从下往下第二层最右那个节点.

初始堆位置编号:

堆位置编号

???0

?1???2

3?4?5?6

第一步就是将2,5,6中最大的放到2处;

第二步将1,3,4中最大的放到1处;

第三步将0,1,2中最大的放到0处;

第四步将0与无序中最后一个节点换(0与6交换),这时6是有序堆,完成第一次调整.

将节点i与其子节点l,r中最大的放到i处这里并不是分成两步的,因此不需要先比较i与r或i与l的大小.

堆排序是怎么建堆的 关键字序列 42 13 24 91 23 16 05 88是怎样建堆的

首先把所有数据填进一个完全二叉树中。然后对非终端结点n/2向下进行调整。建小根堆的时候方法是：1.元素下调。比较它与两个孩子的大小。哪个孩子比它小也比兄弟小则把它调到那个孩子的位置。然后再判断该位置还要不要往下调。2.从n/2开始，对它之前的所有元素进行1操作。

本题解法为（按完全二叉树写）

一。把所有元素写进完全二叉树中得

42

13 24

91 23 16 05

88

二。1.对非叶子元素进行调整，即第n/2个元素，即本题的91.

因为91的孩子为88.比91小。所以调到88的位置。即91和88换

42

13 24

88 23 16 05

91

2.对n/2前一个元素进行调整。即本题的24.因为16和05都比24小，而05比16小，所以24和05调

42

13 05

88 23 16 24

91

3.对步骤2之前的一个元素，即本题的13进行调整，因为88和23都比13大，所以不用调。

4.对步骤3之前的一个元素，即本题的42进行调整。因为13和05都比42小，二05比13小。所以05和42调换位置。而调换位置后42的儿子为16和24,16比24小。所以42和16换位置。（此时已经对第一个元素进行了调整，就可以结束了，如果没错的话就是最终结果）

05

13 16

88 23 42 24

91

建的是小根堆，如果要建大根堆的话，也是往下调，但比较的是下面的哪个大。其他同理

堆排序的具体算法

分类: 电脑/网络 程序设计 其他编程语言

解析:

1、 堆排序定义

n个关键字序列Kl，K2，…，Kn称为堆，当且仅当该序列满足如下性质(简称为堆性质)：

(1) ki≤K2i且ki≤K2i+1 或(2)Ki≥K2i且ki≥K2i+1(1≤i≤ )

若将此序列所存储的向量R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。

【例】关键字序列(10，15，56，25，30，70)和(70，56，30，25，15，10)分别满足堆性质(1)和(2)，故它们均是堆，其对应的完全二叉树分别如小根堆示例和大根堆示例所示。

2、大根堆和小根堆

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小根堆。

根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大根堆。

注意：

①堆中任一子树亦是堆。

②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。

3、堆排序特点

堆排序(HeapSort)是一树形选择排序。

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

4、堆排序与直接插入排序的区别

直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。

堆排序可通过树形结构保存部分比较结果，可减少比较次数。

5、堆排序

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

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

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

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

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

……

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

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

① 初始化操作：将R[1..n]构造为初始堆；

② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。

注意：

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

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

（3）堆排序的算法：

void HeapSort(SeqIAst R)

{ 对R[1..n]进行堆排序，不妨用R[0]做暂存单元

int i；

BuildHeap(R)； 将R[1-n]建成初始堆

for(i=n;i1；i--){ 对当前无序区R[1..i]进行堆排序，共做n-1趟。

R[0]=R[1]；R[1]=R[i];R[i]=R[0]； 将堆顶和堆中最后一个记录交换

Heapify(R，1，i-1)； 将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质

} endfor

} HeapSort

（4） BuildHeap和Heapify函数的实现

因为构造初始堆必须使用到调整堆的操作，先讨论Heapify的实现。

① Heapify函数思想方法

每趟排序开始前R[l..i]是以R[1]为根的堆，在R[1]与R[i]交换后，新的无序区R[1..i-1]中只有R[1]的值发生了变化，故除R[1]可能违反堆性质外，其余任何结点为根的子树均是堆。因此，当被调整区间是R[low..high]时，只须调整以R[low]为根的树即可。

"筛选法"调整堆

R[low]的左、右子树(若存在)均已是堆，这两棵子树的根R[2low]和R[2low+1]分别是各自子树中关键字最大的结点。若R[low].key不小于这两个孩子结点的关键字，则R[low]未违反堆性质，以R[low]为根的树已是堆，无须调整；否则必须将R[low]和它的两个孩子结点中关键字较大者进行交换，即R[low]与R[large](R[large].key=max(R[2low].key，R[2low+1].key))交换。交换后又可能使结点R[large]违反堆性质，同样由于该结点的两棵子树(若存在)仍然是堆，故可重复上述的调整过程，对以R[large]为根的树进行调整。此过程直至当前被调整的结点已满足堆性质，或者该结点已是叶子为止。上述过程就象过筛子一样，把较小的关键字逐层筛下去，而将较大的关键字逐层选上来。因此，有人将此方法称为"筛选法"。

具体的算法【参见教材】

②BuildHeap的实现

要将初始文件R[l..n]调整为一个大根堆，就必须将它所对应的完全二叉树中以每一结点为根的子树都调整为堆。

显然只有一个结点的树是堆，而在完全二叉树中，所有序号 的结点都是叶子，因此以这些结点为根的子树均已是堆。这样，我们只需依次将以序号为 ， -1，…，1的结点作为根的子树都调整为堆即可。

具体算法【参见教材】。

5、大根堆排序实例

对于关键字序列(42，13，24，91，23，16，05，88)，在建堆过程中完全二叉树及其存储结构的变化情况参见【动画演示】。

6、 算法分析

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

堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。

由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

堆排序是就地排序，辅助空间为O(1)，

它是不稳定的排序方法。

二叉堆应用一：堆排序

如图所示：当父结点的值，都比其子结点的值小时，就是 小根堆 ，一个小根堆中，最小的值肯定在堆顶。

同理，当父结点的值都比其子结点的值大时，就是 大根堆 ，一个大根堆中，最大的值肯定在堆顶。

现在是一个大顶堆，那么最大值肯定在堆顶处，我们将堆顶的元素与最后一个元素交换。

然后再将剩下的元素（排除交换的最后一个元素）重新调整为大根堆，过程如下：

10 与左儿子结点右儿子结点中最大值交换。

此时有形成一个新的大根堆。我们在做第一步做

此时，我们就将最大数，和第二大数排好序（升序排列）。

将这个过程往复下去，最后我们就能够将所有数据排序完毕。

我们上面所作的所有步骤，都是假设序列一开始就是大根堆的情况下，但是并不是所有将要排序序列一开始就是是符合大根堆的。

所以，其中关键就是构造大根堆。当我们第一次把随机的数组构造成大根堆后，以后我们只需要每次交换后调整堆顶的数据使之再成为大根堆。往复下去。

给定一个结点n， 其左子结点2n+1，右子节点：2n+2。然后与左右子结点中最大值childmax比较，如果大于childmax，则说明该结点及子树已经符合大根堆标准。

否则则与childmax交换，然后再把原childmax结点作为新的父结点和其左子结点和右子结点比较，作上述过程。最后一直下溯至叶子结点（叶子节点没有左右子结点）。这样我们将结点n及其子树调整为了大根堆。整个过程如上图3。

但是步骤3排序思路的大前提是我们已经将一个随机的数组已经有构造成大根堆的情况下。所以我们之前还必须做将一个随机数组构造成一个大根堆。

有了步骤3 的思路，我们可以从最后一个非叶子结点开始，每一个按照步骤3调整，（这样，每一个结点调整后都可以保证该结点及其子树是副符合大根堆）。这样至下而上，直到根节点。完成后我们将一个随机数组调整为了大根堆。