首页 / 算法 / JAVA数据结构(十一)—— 堆及堆排序
JAVA数据结构(十一)—— 堆及堆排序
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了JAVA数据结构(十一)—— 堆及堆排序,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2123字,纯文字阅读大概需要4分钟。
内容图文
![JAVA数据结构(十一)—— 堆及堆排序](/upload/InfoBanner/zyjiaocheng/617/26ee7595cab040d8ab51e5cbf9c6fd84.jpg)
堆
堆基本介绍
堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,最坏,最好,平均时间复杂度都是O(nlogn),不稳定的排序
堆是具有以下性质的完全二叉树:每个节点的值都大于或等于其左右孩子节点的值称为大顶堆
小于或等于左右孩子节点的值称为小顶堆
堆排序
基本思想
将待排序的序列构造成一个大顶堆(数组)
此时 ,整个序列的最大值就是堆顶的根节点
将其与末尾元素进行交换,此时末尾为最大值
然后将剩余n-1个元素重新构造成一个堆,这样就会得到n个元素的次小值。如此反复执行便能得到一个有序序列
基本步骤
构造初始堆,顺序存放
从最后一个非叶子节点:arr.length/2-1,开始,从左至右,从下至上进行调整
找到第二个非叶子节点,比较其与子节点的大小进行交换
这会导致其交换子树的顺序混乱则继续向下交换
堆顶出堆,针对剩余元素重复上列步骤
代码实现
package com.why.tree;
?
import java.util.Arrays;
import java.util.jar.JarEntry;
?
/**
- @Description TODO 堆排序
- @Author why
- @Date 2020/11/26 18:05
- Version 1.0
/
public class HeapSort {
public static void main(String[] args) {
int[] arr = {4,6,8,5,9};
heapSort(arr);
}
?
/- 堆排序
- @param arr
/
public static void heapSort(int[] arr){
int temp = 0;
//调整成大顶堆
for (int i = arr.length/2 - 1; i >= 0 ; i--) {
adjustHeap(arr,i,arr.length);
}
//将堆顶元素与末尾元素交换,将最大元素沉到数组末端
for (int i = arr.length - 1; i > 0; i--) {
//交换
temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
adjustHeap(arr,0, i);
}
System.out.println(Arrays.toString(arr));
}
?
/* - 将数组(二叉树)调整为大顶堆
- 完成将i对应的的非叶子节点调整成大顶堆
- 自下向上调整
- @param arr 待调整的数组
- @param i 表示非叶子节点在数组中的索引
- @param lengt 表示对多少个元素进行调整,lengt逐渐减小
*/
public static void adjustHeap(int[] arr,int i,int lengt){
//取出当前的值,保存至临时变量
int temp = arr[i];
//开始调整
//j = i * 2 + 1,j是i节点的左子节点
for (int j = i * 2 + 1; j < lengt; j = j * 2 + 1) {
if(j + 1< lengt &&arr[j] < arr[j+1]){//左子节点小于右子节点
j++;//j指向右子节点
}
if (arr[j] > temp){//如果子节点大于父节点
arr[i] = arr[j];//把子节点较大的值与父节点交换
i = j;//i指向j继续循环比较
}else {
break;
}
}
//for循环结束后已将以i为父节点的的树的的最大值放到了堆顶(局部)
arr[i] = temp;//将temp赋值放到最后的位置
}
}
内容总结
以上是互联网集市为您收集整理的JAVA数据结构(十一)—— 堆及堆排序全部内容,希望文章能够帮你解决JAVA数据结构(十一)—— 堆及堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。