如何建立国际网站,用dw做的网页怎么连到网站上,正规网络游戏平台,彩票网站注册目录 基础堆排序
一、概念及其介绍
二、适用说明
三、过程图示
四、Java 实例代码
src/runoob/heap/Heapify.java 文件代码#xff1a; 基础堆排序
一、概念及其介绍
堆排序#xff08;Heapsort#xff09;是指利用堆这种数据结构所设计的一种排序算法。
堆是一个近…目录 基础堆排序
一、概念及其介绍
二、适用说明
三、过程图示
四、Java 实例代码
src/runoob/heap/Heapify.java 文件代码 基础堆排序
一、概念及其介绍
堆排序Heapsort是指利用堆这种数据结构所设计的一种排序算法。
堆是一个近似 完全二叉树的结构并同时满足堆积的性质即子结点的键值或索引总是小于或者大于它的父节点。
二、适用说明
我们之前构造堆的过程是一个个数据调用 insert 方法使用 shift up 逐个插入到堆中这个算法的时候时间复杂度是 O(nlogn)本小节介绍的一种构造堆排序的过程称为 Heapify算法时间复杂度为 O(n)。
三、过程图示
完全二叉树有个重要性质对于第一个非叶子节点的索引是 n/2 取整数得到的索引值其中 n 是元素个数(前提是数组索引从 1 开始计算)。 索引 5 位置是第一个非叶子节点我们从它开始逐一向前分别把每个元素作为根节点进行 shift down 操作满足最大堆的性质。
索引 5 位置进行 shift down 操作后22 和 62 交换位置。 对索引 4 元素进行 shift down 操作 对索引 3 元素进行 shift down 操作 对索引 2 元素进行 shift down 操作 最后对根节点进行 shift down 操作整个堆排序过程就完成了。 四、Java 实例代码
源码包下载Downloadhttps://www.runoob.com/wp-content/uploads/2020/09/runoob-algorithm-Heapify.zip
src/runoob/heap/Heapify.java 文件代码
package runoob.heap; import runoob.sort.SortTestHelper; /** * 用heapify进行堆排序 */ public class HeapifyT extends Comparable { protected T[] data; protected int count; protected int capacity; // 构造函数, 通过一个给定数组创建一个最大堆 // 该构造堆的过程, 时间复杂度为O(n) public Heapify(T arr[]){ int n arr.length; data (T[])new Comparable[n1]; capacity n; for( int i 0 ; i n ; i ) data[i1] arr[i]; count n; //从第一个不是叶子节点的元素开始 for( int i count/2 ; i 1 ; i -- ) shiftDown(i); } // 返回堆中的元素个数 public int size(){ return count; } // 返回一个布尔值, 表示堆中是否为空 public boolean isEmpty(){ return count 0; } // 像最大堆中插入一个新的元素 item public void insert(T item){ assert count 1 capacity; data[count1] item; count ; shiftUp(count); } // 从最大堆中取出堆顶元素, 即堆中所存储的最大数据 public T extractMax(){ assert count 0; T ret data[1]; swap( 1 , count ); count --; shiftDown(1); return ret; } // 获取最大堆中的堆顶元素 public T getMax(){ assert( count 0 ); return data[1]; } // 交换堆中索引为i和j的两个元素 private void swap(int i, int j){ T t data[i]; data[i] data[j]; data[j] t; } //******************** //* 最大堆核心辅助函数 //******************** private void shiftUp(int k){ while( k 1 data[k/2].compareTo(data[k]) 0 ){ swap(k, k/2); k / 2; } } private void shiftDown(int k){ while( 2*k count ){ int j 2*k; // 在此轮循环中,data[k]和data[j]交换位置 if( j1 count data[j1].compareTo(data[j]) 0 ) j ; // data[j] 是 data[2*k]和data[2*k1]中的最大值 if( data[k].compareTo(data[j]) 0 ) break; swap(k, j); k j; } } // 测试 heapify public static void main(String[] args) { int N 100; Integer[] arr SortTestHelper.generateRandomArray(N, 0, 100000); HeapifyInteger heapify new HeapifyInteger(arr); // 将heapify中的数据逐渐使用extractMax取出来 // 取出来的顺序应该是按照从大到小的顺序取出来的 for( int i 0 ; i N ; i ){ arr[i] heapify.extractMax(); System.out.print(arr[i] ); } // 确保arr数组是从大到小排列的 for( int i 1 ; i N ; i ) assert arr[i-1] arr[i]; } }
