数据结构 堆排序问题,高手请进

发布网友 发布时间：2022-04-29 22:08

我来回答

共4个回答

热心网友 时间：2022-05-22 02:42

又有注释又调试通过的程序，多好！以下部分已经在win-tc和Dev-c++下调试通过。
void Heapify(int s,int m) /*这就是你所需要的部分*/
{
int j,temp; /*对R[1..n]进行堆调整，用temp做暂存单元 */
temp=R[s];
j=2*s;
while (j<=m)
{
if (R[j]>R[j+1]&&j<m) j++;
if (temp<R[j]) break;
R[s]=R[j];
s=j;
j=j*2;
}
R[s]=temp;
}

void BuildHeap(int n)
{ /* 由一个无序的序列建成一个堆 */
int i;
for(i=n/2;i>0;i--)
Heapify(i,n);
}
原题和你这题都是大根堆。
如果是小根堆，只要将程序中的大于号相应改为小于号即可：
if (R[j]<R[j+1]&&j<m) j++;
if (temp>R[j]) break;

参考资料：具体请参阅：http://zhidao.baidu.com/question/80787783.html

热心网友 时间：2022-05-22 04:00

从最后一个有孩子节点的元素开始到第一个元素为止
1:筛选62得序列(46,25,78,29,12,37,70,62)
2:筛选78得序列(46,25,37,29,12,78,70,62)
3:筛选25得序列(46,12,37,29,25,78,70,62)
4:筛选46得序列(12,25,37,29,46,78,70,62)分两步

热心网友 时间：2022-05-22 05:35

代码
/*小根树*/#include<iostream>
using namespace std;
int a[10000];
int n;
void check(int i)
{
int min;
if(2*i<n)
{
if(n%2==0&&i==n/2)
min=2*i;
else
min=a[2*i]<a[2*i+1]?2*i:2*i+1;
if(a[i]>a[min])
{
a[0]=a[i];
a[i]=a[min];
a[min]=a[0];
check(min);
}
}
}
void bheap()
{
for(int i=n/2/*最后一个有子的节点*/;i>0;i--)
check(i);/*最多N次*/
}
int main()
{
cin>>n;
int i;
for(i=1;i<=n;i++)
cin>>a[i];
bheap();
for(i=n;i>=1;i--)
{
cout<<a[1]<<endl;
a[1]=a[n];
check(1);
n--;
}
system("pause");
return 0;
}

热心网友 时间：2022-05-22 07:26

又有注释又调试通过的程序，多好！以下部分已经在win-tc和Dev-c++下调试通过。
void
Heapify(int
s,int
m)
/*这就是你所需要的部分*/
{
int
j,temp;
/*对R[1..n]进行堆调整，用temp做暂存单元
*/
temp=R[s];
j=2*s;
while
(j<=m)
{
if
(R[j]>R[j+1]&&j<m)
j++;
if
(temp<R[j])
break;
R[s]=R[j];
s=j;
j=j*2;
}
R[s]=temp;
}
void
BuildHeap(int
n)
{
/*
由一个无序的序列建成一个堆
*/
int
i;
for(i=n/2;i>0;i--)
Heapify(i,n);
}
原题和你这题都是大根堆。
如果是小根堆，只要将程序中的大于号相应改为小于号即可：
if
(R[j]<R[j+1]&&j<m)
j++;
if
(temp>R[j])
break;