Question

C++堆排序建堆问题

我想建小顶堆，思路大概是从无序数组的j=n/2-1处开始与2*j+1和2*j+2比较，如果j比它们小，就与它们两个中最大的数交换。不知道这种建堆方式对不对，还是其它地方有问题。void HeapSort(int r[],int n){ int t; for(int i=0;i<n;i++) { t=i; BuildHeap(r,t,n); int temp=r[i]; r[i]=r[n]; r[n]=temp; }}void BuildHeap(int r[],int t,int n){ for(int j=(n-t)/2-1;j>0;j=j/2) { if(r[2*j+1]<=r[2*j+2]) { if(r[j]<r[2*j+2]) { int temp=r[j]; r[j]=r[2*j+2]; r[2*j+2]=temp; } } if(r[2*j+1]>r[2*j+2]) { if(r[j]<r[2*j+1]) { int temp=r[j]; r[j]=r[2*j+1]; r[2*j+1]=temp; } } }}

Answer 1

在你的HeapSort应该加一段初始化为最小堆的代码，然后再进入那个for循环。BuildHeap建堆的过程是至上而下的,也就是说j的值变成 2*j或 2*j+1,而不是j/=2.
如果按你这样的方法构建会出现这样的交换过程：
1.8 2 3 1
2.8 1 3 2
3.1 8 3 2
显然不是最小堆，正确的应该是1 2 3 8

你可以看一下这个：http://blog.csdn.net/ouyangying123/article/details/51334165

追问

我改了一下但是还是有问题，能帮忙看看吗

追答

void BuildHeap(){
if(r[j]<r[2*j]){//建立小顶堆的话，这里应该是大于吧。。。。
交换;
}
if(r[j]<r[2*j +1 ])//同理
}

追问

还得再麻烦你一次。。。改完之后还是什么都输出不了，应该是还有别的问题。。但是我看不出来。。

追答

如果单是对代码的话，你可以照着上面的链接里面的代码一行一行对~
我觉得你的思路不是很清晰，建议你照着链接里的数据，手动模拟一遍过程，然后根据过程对你的代码~ 要注意数组下标 和 你的堆下标是否一致~