职友集一家做公司点评的网站,网页设计方案,营销师,html网页制作介绍自己家乡文章目录 建堆的时间复杂度向下调整建堆向上调整建堆 堆排序实现 建堆的时间复杂度
下面都以建大堆演示
向下调整建堆
void Adjustdown(HPDataType* a, int size,int parent)
{int child parent * 2 1;while (child size){if (child1sizea[child 1] parent * 2 1;while (child size){if (child1sizea[child 1] a[child]){child;}if (a[parent] a[child]){Swap(a[child], a[parent]);parent child;child parent * 2 1;}else{break;}}
}我们根据求堆的节点总数利用等比数列求和公式可以知道堆节点总数N和堆高度h之间的关系N2^h-1。再根据图片规律求出移动节点的步数 因此利用向下调整建堆的的时间复杂度为ON。 向上调整建堆
void Adjustup(HPDataType*a,int child)
{int parent (child - 1) / 2;while (child 0){if (a[parent] a[child]){Swap(a[parent], a[child]);child parent;parent (child - 1) / 2;}else{break;}}
}对比两种建堆的时间复杂度我们能看出向下调整建堆要优于向上调整建堆接下来我们利用向下调整建堆实现堆排序。 堆排序
排序可以分为升序排序和降序排序实现堆排序前我们先要思考升序和降序哪种适合大堆哪种适合小堆假如我们现在要实现升序排序我们可以先用小堆理一遍思路小堆结构是堆顶元素最小如果我们直接把堆顶拿出来那么下面父子兄弟节点的关系全乱了最差的情况需要把每个节点都向上调整一遍时间复杂度太高。如果选择大堆我们只需把每次堆顶的元素和堆中最后一个元素交换然后让新的堆顶向下调整每次交换完后最后的元素不参与后续的向下调整就能得到一个升序的数组。
void Swap(HPDataType* p1, HPDataType* p2)
{HPDataType tmp *p1;*p1 *p2;*p2 tmp;
}void Heapsort(int *a,int n)
{for (int i 1; i n; i){Adjustup(a, i);}int end n - 1;while (end0){Swap(a[0], a[end]);Adjustdown(a, end, 0);--end;}
}先建一个大堆然后不断将堆顶和堆尾元素交换再让新堆顶向下调整得到次大的数
实现
int main()
{int a[] { 4,6,8,2,3,7,1,5 };Heapsort(a, sizeof(a) / sizeof(int));for (int i 0; i sizeof(a) / sizeof(int); i){printf(%d , a[i]);}printf(\n);return 0;
}
