什么网站可以做英语题,安徽水安建设集团网站,门户网站建设计入什么科目,wordpress5.0大更新转载自 漫画#xff1a;什么是堆排序
在上一篇漫画中#xff0c;小灰介绍了 二叉堆 这样一种强大的数据结构#xff1a;
漫画#xff1a;什么是二叉堆#xff1f;#xff08;修正版#xff09;
那么#xff0c;这个二叉堆怎样来使用呢#xff1f;我们这一期将会详…转载自 漫画什么是堆排序
在上一篇漫画中小灰介绍了 二叉堆 这样一种强大的数据结构
漫画什么是二叉堆修正版
那么这个二叉堆怎样来使用呢我们这一期将会详细讲述。 让我们回顾一下二叉堆和最大堆的特性
1.二叉堆本质上是一种完全二叉树
2.最大堆的堆顶是整个堆中的最大元素
当我们删除一个最大堆的堆顶并不是完全删除而是替换到最后面经过自我调节第二大的元素就会被交换上来成为最大堆的新堆顶。 正如上图所示当我们删除值为10的堆顶节点经过调节值为9的新节点就会顶替上来当我们删除值为9的堆顶节点经过调节值为8的新节点就会顶替上来.......
由于二叉堆的这个特性我们每一次删除旧堆顶调整后的新堆顶都是大小仅次于旧堆顶的节点。那么我们只要反复删除堆顶反复调节二叉堆所得到的集合就成为了一个有序集合过程如下
删除节点9节点8成为新堆顶 删除节点8节点7成为新堆顶 删除节点7节点6成为新堆顶 删除节点6节点5成为新堆顶 删除节点5节点4成为新堆顶 删除节点4节点3成为新堆顶 删除节点3节点2成为新堆顶 到此为止我们原本的最大堆已经变成了一个从小到大的有序集合。之前说过二叉堆实际存储在数组当中数组中的元素排列如下 由此我们可以归纳出堆排序算法的步骤
1. 把无序数组构建成二叉堆。
2. 循环删除堆顶元素移到集合尾部调节堆产生新的堆顶。 public class HeapSort {
/**
* 下沉调整
* param array 待调整的堆
* param parentIndex 要下沉的父节点
* param parentIndex 堆的有效大小
*/
public static void downAdjust(int[] array, int parentIndex, int length) {// temp保存父节点值用于最后的赋值int temp array[parentIndex];int childIndex 2 * parentIndex 1;while (childIndex length) {// 如果有右孩子且右孩子大于左孩子的值则定位到右孩子if (childIndex 1 length array[childIndex 1] array[childIndex]) {childIndex;}// 如果父节点小于任何一个孩子的值直接跳出if (temp array[childIndex])break;//无需真正交换单向赋值即可array[parentIndex] array[childIndex];parentIndex childIndex;childIndex 2 * childIndex 1;}array[parentIndex] temp;
}/**
* 堆排序
* param array 待调整的堆
*/
public static void heapSort(int[] array) {// 1.把无序数组构建成二叉堆。for (int i (array.length-2)/2; i 0; i--) {downAdjust(array, i, array.length);}System.out.println(Arrays.toString(array));// 2.循环删除堆顶元素移到集合尾部调节堆产生新的堆顶。for (int i array.length - 1; i 0; i--) {// 最后一个元素和第一元素进行交换int temp array[i];array[i] array[0];array[0] temp;// 下沉调整最大堆downAdjust(array, 0, i);}
}public static void main(String[] args) {int[] arr new int[] {1,3,2,6,5,7,8,9,10,0};heapSort(arr);System.out.println(Arrays.toString(arr));
}
} 二叉堆的节点下沉调整downAdjust 方法是堆排序算法的基础这个调节操作本身的时间复杂度是多少呢 假设二叉堆总共有n个元素那么下沉调整的最坏时间复杂度就等同于二叉堆的高度也就是Ologn。
我们再来回顾一下堆排序算法的步骤
1. 把无序数组构建成二叉堆。
2. 循环删除堆顶元素移到集合尾部调节堆产生新的堆顶。
第一步把无序数组构建成二叉堆需要进行n/2次循环。每次循环调用一次 downAdjust 方法所以第一步的计算规模是 n/2 * logn时间复杂度Onlogn。
第二步需要进行n-1次循环。每次循环调用一次 downAdjust 方法所以第二步的计算规模是 n-1 * logn 时间复杂度 Onlogn。
两个步骤是并列关系所以整体的时间复杂度同样是 Onlogn。
