手机网站导航设计模板,潜江招聘资讯网,网站美工怎么做,做的好的购物网站目录 一、前备知识
二、建堆
2.2.1 向上调整算法建堆
2.2.2 向下调整算法建堆
三、排序
3.1 常见问题
3.2 思路
3.3 源码 一、前备知识
详细图解请点击#xff1a;二叉树的顺序实现-堆-CSDN博客
本文只附上向上/向下调整算法的源码
//交换
void Swap(int* p, int* …目录 一、前备知识
二、建堆
2.2.1 向上调整算法建堆
2.2.2 向下调整算法建堆
三、排序
3.1 常见问题
3.2 思路
3.3 源码 一、前备知识
详细图解请点击二叉树的顺序实现-堆-CSDN博客
本文只附上向上/向下调整算法的源码
//交换
void Swap(int* p, int* q)
{int tmp *p;*p *q;*q tmp;
}
//向下调整算法
void AdjustDown(int* a, int n, int parent)
{//左孩子的下标int child parent * 2 1;while (childn){//找到两个孩子中较小的孩子-假设法if (child 1 n a[child 1] a[child]){child;}if (a[parent] a[child]){Swap(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}
//向上调整算法
void AdjustUp(int* a, int child)
{int parent (child - 1) / 2;while (child 0){if (a[child] a[parent]){Swap(a[child], a[parent]);child parent;parent (child - 1) / 2;}else{break;}}
}
二、建堆
堆排序堆排序先有堆才能排序所以排序的第一步是要将一个一般的数组建成堆。
注由于建大堆还是小堆仅仅取决于自定的大小于号本文下述建堆都以小堆为例
2.2.1 向上调整算法建堆 思路 单一的一个结点可以看成一个堆后续的所有结点都可以看作是插入结点 所以只需要循环插入所有后续结点即可 void BuildHeap1(int* a, int n)
{//把根节点看作是堆剩下的结点看作插入结点开始依次插入for (int i 1; i n; i){AdjustUp(a, i);}
}
2.2.2 向下调整算法建堆 错误思路 向下调整算法要求左右子树必须为大/小堆所以从根节点开始结点开始建堆的做法是错误的 正确思路 上文说单一的一个结点可以看成一个堆。所以从最后一个叶子节点的父节点开始向下调整不断循环所有父节点就可以保证他的左右子树都是堆。 void BuildHeap2(int* a, int n)
{//从最后一个叶子结点的父结点开始调for (int i ((n - 1) - 1) / 2; i 0; i--){AdjustDown(a, n, i);}
}
三、排序
3.1 常见问题
为什么建堆后依然还要排序 大堆/小堆的定义注定了堆仅仅能保证父节点大于孩子结点无法保证孩子结点按照大于/小于的次序严格排列
升序建小堆降序建大堆的思路是否可行
升序建小堆首先对 n 个数建小堆选出最小的数接着对剩下的 n-1 个数建小堆选出第二小的数不断重复上述过程。若用向上调整算法可行但时间复杂度太高若使用向下调整算法时对n-1个调整就会发现原先的孩子父亲关系全乱不可行。降序建大堆首先对 n 个数建小堆选出最小的数接着对剩下的 n-1 个数建大堆选出第二大的数不断重复上述过程。使用向下调整算法时对n-1个调整就会发现原先的孩子父亲关系全乱不可行。
3.2 思路 本质上是堆删除的思路。利用堆的特性无论是大堆还是小堆根节点的值一定是最大/小的数。这样每进行一次调整就会选择出最小/大次小/大......便可以实现排序。为了防止出现父子关系乱序的问题将每次找到的最值放在堆的末位置对前n-1个元素进行向下调整便可以完美解决排序问题由此可以总结升序建大堆降序建小堆。 由此我们可以归纳出堆排序算法的步骤
1. 把无序数组构建成二叉堆。
2. 循环删除堆顶元素移到数组尾部调节堆产生新的堆顶。
3.3 源码
//降序建小堆
void HeapSortDown(int* a, int n)
{//建小堆for (int i ((n - 1) - 1) / 2; i 0; i--){AdjustDown(a, n, i);}//排序int end n - 1; //定位数组最后一个位置while (end 0){Swap(a[0], a[end]); // 将堆顶元素和堆中最后一个元素交换把最大的数(堆顶)放到最后AdjustDown(a, end, 0);end--; // 调整前n-1个元素}
}
