堆排序过程中

看不懂楼主题意...指的是原地排序最后置换的过程么？置换之后的最大最小值就不用管的呀，已不属于堆了...

索引0已经是最值了，然后对剩余的元素再排序啊

看的一个例子，比如(49,38,65,97,76,13,27,49)，用的是小堆。 贴输出第一个值的最后几个图， 问题就是：输出13时候，49.65.27不满足小堆的要求。 如果这3个不做调整就直接输出13，好像也不会影响最终的排序结果，对吗 【 在 jiayidong 的大作中提到: 】 : 看不懂楼主题意...指的是原地排序最后置换的过程么？置换之后的最大最小值就不用管的呀，已不属于堆了...

当然是影响的。 设堆大小为N 按堆排的步骤，构建完最小堆后，将堆中最小元素A[0]和A[N-1]交换，同时N=N-1（也就是将已经找到的最小元素排除在堆外）。 之后，对交换后产生堆找其最小的元素。按你的举例,如果上一步不满足最小堆的性质，找出的最小元素A[0]是38，而不是27了，这样不就错了。 建议看看算法导论上堆排序那一章的内容，原理讲的很详细。 【 在 tycoon0 的大作中提到: 】 : 看的一个例子，比如(49,38,65,97,76,13,27,49)，用的是小堆。 : 贴输出第一个值的最后几个图， 问题就是：输出13时候，49.65.27不满足小堆的要求。 如果这3个不做调整就直接输出13，好像也不会影响最终的排序结果，对吗 : [upload=1][/upload]

说说我的做法 1.输出13后，把97放入a[0]位置，同时：49,65,27不满足最小堆 2.从下标N-2往前搜索第一个非叶子节点，这时候会调整49,65,27. 这种做法有什么不妥？？ 【 在 ZeroMoe 的大作中提到: 】 : 当然是影响的。 : 设堆大小为N : 按堆排的步骤，构建完最小堆后，将堆中最小元素A[0]和A[N-1]交换，同时N=N-1（也就是将已经找到的最小元素排除在堆外）。 : ...................

这样也可以啊，跟书上的原理是一样的啊，提出最小的一个数，然后再对余下的数重新建堆。 只不过书上是把a[0]给提出来，余下的a[1]-a[N]建堆， 你是把最后的a[N-1]赋值给a[0]，余下的a[0]-a[N-2]建堆，一个原理 【 在 tycoon0 的大作中提到: 】 : 说说我的做法 : 1.输出13后，把97放入a[0]位置，同时：49,65,27不满足最小堆 : 2.从下标N-2往前搜索第一个非叶子节点，这时候会调整49,65,27. : ...................

因为没有将代码贴出来，从下标N-2往前搜索第一个非叶子节点，这时候会调整49,65,27.，这句话我就先按会对所有的非叶子节点进行一次判断。这样的话每次都需要判断N-2/2个节点。 而如果一开始是满足最小堆的性质，交换A[0]和A[N-1]后，排除A[N-1]后，继续维护堆的性质需要判断的节点数最多为Lg(N-2)个（也就是树高）。 算法的复杂度不一样。 【 在 tycoon0 的大作中提到: 】 : 说说我的做法 : 1.输出13后，把97放入a[0]位置，同时：49,65,27不满足最小堆 : 2.从下标N-2往前搜索第一个非叶子节点，这时候会调整49,65,27. : ...................

是的 复杂度不一样了 明天贴代码 自己一个人这么鼓捣 害怕弄错或者不是最优解 【 在 ZeroMoe 的大作中提到: 】 : 因为没有将代码贴出来，从下标N-2往前搜索第一个非叶子节点，这时候会调整49,65,27.，这句话我就先按会对所有的非叶子节点进行一次判断。这样的话每次都需要判断N-2/2个节点。 : 而如果一开始是满足最小堆的性质，交换A[0]和A[N-1]后，排除A[N-1]后，继续维护堆的性质需要判断的节点数最多为Lg(N-2)个（也就是树高）。 : 算法的复杂度不一样。 : ...................

#include <stdio.h> #include <stdlib.h> #include <string.h> int sort_heap(int *a, int size) { int n = size-1; int tmp = 0; for(n = size-1; n >=0; n--) { if( (n*2+1) > size || (n*2+2) > size) continue; if(a[n*2+1] > a[n]) { tmp = a[n]; a[n] = a[2*n+1]; a[2*n+1] = tmp; } if( (n*2+2 < size) && a[n*2+2] > a[n] ) { tmp = a[n]; a[n] = a[n*2+2]; a[n*2+2] = tmp; } } int ret = 0; ret = a[0]; a[0] = a[size-1]; return ret; } int main() { int a[] = {77, 75, 26, 45, 9, 12, 93, 78, 62, 45, 8, 19, 82}; int size = sizeof(a)/sizeof(a[0]); int i =0; for(i=size; i >=1; i--) printf("%d ", sort_heap(a, i)); } 【 在 ZeroMoe 的大作中提到: 】 : 因为没有将代码贴出来，从下标N-2往前搜索第一个非叶子节点，这时候会调整49,65,27.，这句话我就先按会对所有的非叶子节点进行一次判断。这样的话每次都需要判断N-2/2个节点。 : 而如果一开始是满足最小堆的性质，交换A[0]和A[N-1]后，排除A[N-1]后，继续维护堆的性质需要判断的节点数最多为Lg(N-2)个（也就是树高）。 : 算法的复杂度不一样。 : ...................