前言:
现时各位老铁们对“堆排序算法描述”大体比较珍视,你们都需要学习一些“堆排序算法描述”的相关内容。那么小编也在网络上搜集了一些关于“堆排序算法描述””的相关文章,希望大家能喜欢,小伙伴们快快来了解一下吧!二叉堆的定义:二叉堆是完全二叉树或者是近似完全二叉树
二叉堆满足两个特性:
a.父节点的键值总是大于等于或小于等于任何一个子节点的键值
b.每个节点的左子树和右子树都是一个二叉堆(都是最大堆或最小堆)
大顶堆:父节点的键值总是大于或等于任何一个子节点的键值
小顶堆:父节点的键值总是小于或等于任何一个子节点的键值
算法思想:堆排序 = 堆构造 + 交换堆末尾元素与根节点 + 删除未节点 + 构造堆 + 交换...一次循环,
由于根节点必定是堆中最大或最小的元素,所以删除出来的元素序列也必定是升序或降序的。
void minHeapFixdown(int arr, int i, int count){ int j, temp; temp = arr[i]; j = 2 * i + 1; while(j < count) { if (j + 1 < count && arr[j + 1] < arr[j]) { j++; //找出较小的子节点 } if(arr[j] >= temp) { break; //如果较小的子节点比父节点大 直接返回 } arr[i] = arr[j]; //设置父节点为较小节点 i = j; //调整的子节点作为新一轮的父节点 j = 2 * i + 1; //调整的子节点的子节点 } arr[i] = temp;}void heapSort(int array[], int count) { for (int i = (count - 1) / 2; i >= 0; i--) { // 构造小顶堆 minHeapFixdown(array, i, count); } for (int i = count - 1; i >= 1; i--) { // 交换根结点与最末节点 int temp = array[i]; array[i] = array[0]; array[0] = temp; // 剩余的n-1个元素再次建立小顶堆 minHeapFixdown(array, 0, i); }}
版权声明:
本站文章均来自互联网搜集,如有侵犯您的权益,请联系我们删除,谢谢。
标签: #堆排序算法描述