我要招人

去企业版

首页 > 试题广场 >

使用堆排序方法排序（45，78，57，25，41，89），初

[单选题]

使用堆排序方法排序（45，78，57，25，41，89），初始堆为（？）

```
78,45,57,25,41,89
```
```
89,78,57,25,41,45
```
```
89,78,25,45,41,57
```
```
89,45,78,41,57,25
```

查看答案及解析

weicon

第一层： 45

第二层： 78 57

第三层：25 41 89

按照选项应该是递减的排序，从89开始上移，完成max heap

则第一次移动之后

第一层： 89

第二层： 78 57

第三层：25 41 45

发表于 2015-09-17 13:19:27 回复(5)

mingshan

i从n/2到1进行调整，每次调整都将编号的节点调整到对应位置。

题目中n=6，则经过3次调整。

45 78 89 25 41 57

89 78 57 25 41 45

发表于 2017-03-04 15:29:34 回复(1)

jacksonary

初始堆的构建，一开始不用想，先让根节点和末节点交换

发表于 2017-08-01 14:23:13 回复(0)

林湾村龙猫

我的构建方式是 89 ， 45，78，25，41，57 ，然而没有。最后，按照堆定义（完全二叉树，根大于子节点），根据选项确定

http://blog.csdn.net/pursuing0my0dream/article/details/45844199

编辑于 2016-01-04 20:14:28 回复(1)

momo_gogogo

初始堆到底是啥？？？

我按照正常的大根堆排序一步的结果就是答案，所以还是不懂这个说的初始堆到底指的是啥？？

发表于 2022-08-18 21:07:45 回复(0)

Wanna_Peace

void swap(int *a, int *b)

{

int temp = *a;

*a = *b;

*b = temp;

}

void Maxheap(int a[], int n, int i)

{

int j,temp;

temp = a[i];

j = 2*i +1;

while(j<n)

{

if(j+1<n && a[j+1]>a[j])

j++;

if(a[j]<=temp)

break;

a[i] = a[j];

i=j;

j = 2*i +1;

}

a[i]=temp;

}

void MaxheapSort(int a[], int n)

{

//for(int i=n-1; i >=1; i--)

//{

int i;

i= n-1;

swap(a[i], a[0]);

Maxheap(a, 0, i);

for(int m=0; m<n;m++)

cout<<a[m]<<" ";

system("PAUSE");

//}

}

void main()

{

int a[]={45,78,57,25,41,89};

MaxheapSort(a,6);

}

发表于 2015-09-16 13:45:16 回复(0)

夕一啊

http://blog.csdn.net/jinyongqing/article/details/12651349

建堆的过程，放进完全二叉树之后，从最后一个非叶子节点开始调整，

所以第一个调整57，和89交换，然后是它前一个，78，不变，然后再前一个，就是堆顶了45，和89交换，再下沉

发表于 2017-05-16 17:02:38 回复(1)

不要浮于表面

推荐一个讲堆排序的博客，迄今为止看到讲的最好最明白的，https://blog.csdn.net/u013384984/article/details/79496052

白话讲排序系列（六）堆排序（绝对让你明白堆排序！）

发表于 2019-06-01 21:47:13 回复(0)

啦啦啦不想起床

$\begin{cases} a_i \leq a_{2i} \\ a_i \leq a_{2i+1} \\ \end{cases} or \begin{cases} a_i \geq a_{2i} \\ a_i \geq a_{2i+1} \\ \end{cases}$

满足条件即可吧

编辑于 2024-01-30 11:33:34 回复(0)

牛客536017089号

先将57和89进行交换，再将89和45交换，在将45和57交换。最后得到大根堆89 78 57 25 41 45

发表于 2022-07-29 12:40:51 回复(0)

牛客905435118号

转自评论区:推荐一个讲堆排序的博客，迄今为止看到讲的最好最明白的，https://blog.csdn.net/u013384984/article/details/79496052

发表于 2020-10-27 22:03:34 回复(0)

关机自闭的么么哒

建堆的过程，从倒数第 n/2 个元素开始，自底向上地维护堆的性质。

发表于 2020-03-17 20:41:26 回复(0)

孟庆良

这个不同实现都可以啊。C++ 标准库中

int main()
{
	vector<int> vec{45,78,57,25,41,89};
	make_heap(vec.begin(),vec.end());
	for (int i : vec)
	{
		cout << i << " ";
	}
}

输出89 78 57 25 41 45

发表于 2020-02-28 22:36:09 回复(0)

和风气

给定堆去进行初始化，不是一个一个插入地建堆

发表于 2019-12-16 19:21:39 回复(0)

codeor

有个小技巧，利用选项，已知为大根堆，A排除，剩下只有B为大根堆

发表于 2019-08-13 21:09:50 回复(0)

o小菜

第一次移动之后叫初始堆吗。。

发表于 2019-01-23 10:30:28 回复(1)

NotFear

就是记得不是和平衡二叉树那样，边插入边平衡，而是先建立一个完全二叉树，然后是实现堆有序

发表于 2019-01-05 08:09:34 回复(0)

大雄好叻

建立二叉树看

发表于 2018-11-01 11:15:08 回复(0)

Ray12345

首先对第n/2取下界个节点为根的子树进行筛选，本题中为89和57

发表于 2017-11-07 23:16:44 回复(0)

轩~^~*~^~

堆排序的性质：

任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。

大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。

发表于 2016-08-27 16:49:44 回复(0)

提交观点

问题信息

C++工程师运维工程师美团算法工程师 2016 排序 Java工程师

来自：美团2016研发工程师...

难度：

21条回答 557收藏 21103浏览

使用堆排序方法排序（45，78，57，25，41，89），初

白话讲排序系列（六）堆排序（绝对让你明白堆排序！）

问题信息

热门推荐

相关试题

使用堆排序方法排序（45，78，57，25，41，89），初

白话讲排序系列（六） 堆排序（绝对让你明白堆排序！）

问题信息

热门推荐

相关试题

白话讲排序系列（六）堆排序（绝对让你明白堆排序！）