毕设做网站什么能过,营销怎么做,专业网站开发制作公司,旅游景区网站建设规划堆#xff08;二叉树的应用#xff09;#xff1a;
完全二叉树。最大堆#xff1a;每个节点比子树所有节点的数值都大#xff0c;根节点是最大值。父子索引号关系#xff08;根节点为0#xff09;#xff1a;#xff08;向上#xff09;子节点x#xff0c;父节点(x…堆二叉树的应用
完全二叉树。最大堆每个节点比子树所有节点的数值都大根节点是最大值。父子索引号关系根节点为0向上子节点x父节点(x-1) // 2。向下父节点x左子节点2x1右子节点2x2。一般用数组实现堆。 堆排序
第一步、构建堆最大堆。
找到最后的父节点(最后元素的索引号-1) // 2。从最后的父节点到根节点依次向下调整比较父节点和左右子节点最大值为父节点。最终根节点为最大值。尾指针指向最后节点。
第二步、排序
交换根节点和尾指针所在节点。此时尾指针所在节点为目前正在排序中数据的最大值保持不动。尾指针向前向左移动一位。从根节点到尾指针所在节点依次向下调整。此时根节点为目前正在排序中数据的最大值不包含已排序好且保持不动的最大值。
第三步、重复第二步直到尾指针指向根节点停止。 时间复杂度O(nlogn)
初次构建堆时间约n。每次向下调整都是使用2x1、2x2遍历次数是logn对数几乎每个元素都要重排因此时间约 nlogn。相对于nlogn而言n可忽略即总时间O(nlogn)。
空间复杂度O(1)
在原位置排序只重复使用了用于交换的临时空间不随数据量的变动而变动空间使用为常量(1)。 C语言实现思路
先构建堆最大堆再排序。
void heapsort(int *array, int length) // heap sort
{// 构建堆最大堆// 找到最后的父节点int i ceil((length - 1) / 2); // 从最后的父节点到根节点依次向下调整父子节点比较大小最大值为父节点for(; i 0; i--){adjustdown(array, i, length - 1);}// 排序// 交换根节点和尾指针所在节点尾指针前移一位从根节点开始向下调整for(int n length - 1; n 0; n--){swap(array[0], array[n]);adjustdown(array, 0, n - 1);}
} 因多次向下调整多次交换两个数据因此向下调整、交换数据分别用函数单独实现。 交换两个数据
传入的参数为数据的内存地址将直接在内存地址进行数据交换。
void swap(int *a, int *b)
{int tmp *a;*a *b;*b tmp;
}
向下调整
向下在左右子节点中找到较大值的节点父节点再与较大值的子节点比较大小若子节点数值更大父子节点交换位置。
void adjustdown(int *array, int start, int end) // adjust the heap down
{while(start end){int left 2 * start 1, right 2 * start 2, maxchild;// 比较左右子节点找到较大值的子节点if(left end) break;if(right end array[left] array[right]) maxchild right;else maxchild left;// 与较大值的子节点比较若子节点数值更大交换父子节点的位置if(array[start] array[maxchild]){swap(array[start], array[maxchild]);start maxchild;}else break;}
} 完整代码heapsort.c
#include stdio.h
#include math.h/* function prototype */
void heapsort(int *, int); // heap sort
void traverse(int *, int); // show element one by one/* main function */
int main(void)
{int arr[] {4,2,6,9,5,1,3};int n sizeof(arr) / sizeof(int);traverse(arr, n);heapsort(arr, n); printf([ after heap sort ] );traverse(arr, n);return 0;
}/* subfunction */
void swap(int *a, int *b) // change the value of two datas
{int tmp *a;*a *b;*b tmp;
}void adjustdown(int *array, int start, int end) // adjust the heap down
{while(start end){int left 2 * start 1, right 2 * start 2, maxchild;// left child or right child, find the max oneif(left end) break;if(right end array[left] array[right]) maxchild right;else maxchild left;// parent compair with maxchild, if smaller than maxchild,change the positionif(array[start] array[maxchild]){swap(array[start], array[maxchild]);start maxchild;}else break;}
}void heapsort(int *array, int length) // heap sort
{// build a heapint i ceil((length - 1) / 2); // find the last parent// from the last parent to 0 index, cycle ajust the heap down(parent compair with child)for(; i 0; i--){adjustdown(array, i, length - 1);}// sort (root is max, change max to the last, end pointer move a step to the left)for(int n length - 1; n 0; n--){// swap the first and last elementswap(array[0], array[n]);// from 0 index, compair with left child and right child, max is parentadjustdown(array, 0, n - 1);}
}void traverse(int *array, int length) // show element one by one
{printf(elements(%d): , length);for(int k 0; k length; k){printf(%d , array[k]);}printf(\n);
} 编译链接 gcc -o heapsort heapsort.c 执行可执行文件 ./heapsort
