作者:zhengxing | 来源:互联网 | 2023-09-24 16:34
构建大顶堆、堆排序实现(java)构建大顶堆、堆排序实现(java)堆排序介绍:①堆排序是利用堆的数据结构设计的一种排序算法,堆排序是一种选择排序,时间复杂度为O(nlogn),是
构建大顶堆、堆排序实现(java)
构建大顶堆、堆排序实现(java)
堆排序介绍:
①堆排序是利用堆的数据结构设计的一种排序算法,堆排序是一种选择排序,时间复杂度为O(nlogn),是不稳定排序;
②堆是具有以下性质的完全二叉树:每个节点的值都大于或者等于其左右孩子节点的值,称为大顶堆;(没有要求其左右孩子节点的值谁大谁小)
③每个节点的值都小于或者等于其左右孩子节点的值,称为小顶堆
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/bf99ca37268d25f2.jpeg)
对堆中的节点按层进行编号,映射到数组中:
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/1d558c10d5641caa.jpeg)
大顶堆的特点:
arr[i] >= arr[2 * i + 1] && arr[i] >= arr[2 * i + 2]; //i对应的是第几个节点,i从0开始
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/0a858ba17cee1ac0.jpeg)
小顶堆特点:
arr[i] <= arr[2 * i + 1] && arr[i] <= arr[2 * i + 2]; //i对应第几个节点,i从0开始编号
一般升序的时候采用大顶堆,降序的时候采用小顶堆
堆排序的基本思想:
①将待排序序列构造成一个大顶堆
②此时,整个序列的最大值就是堆顶的根节点
③将其与末尾元素进行交换,此时末尾就是最大值
④然后将剩余 n-1 个元素重新调整成一个堆,这样会得到n个元素的次小值,反复执行,就能得到一个有序序列
在构建大顶堆的过程中,元素的个数逐渐减少,最后就能得到一个有序序列;
例如: 将{4,6,8,5,9}使用堆排序,将数组升序排序
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/5ed9054934a78cd2.jpeg)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/a2ca4c02c10955cf.png)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/0ddcea7ba7837304.jpeg)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/7a1b86441c1bdf47.jpeg)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/36dc76abaa4e4494.jpeg)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/018654fddacde4c2.jpeg)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/4f795e0f5da78529.jpeg)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/e766397ae1978063.jpeg)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/f0118fac41cff443.jpeg)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/f3f268e9a73b90ee.jpeg)
![《java大顶堆类,构建大顶堆、堆排序实现(java)》](https://img7.php1.cn/3cdc5/cc8a/243/8fcffcd08581a146.jpeg)
调整大顶堆代码
/**
* 功能:完成将以 i 对应的非叶子节点的树调整成为大顶堆
*
* @param arr 待调整的数组
* @param i 表示非叶子节点在数组中的索引
* @param length 表示对多少个元素进行调整,每排序好一趟,length的长度就减1
*/
public static void adjustHeap(int[] arr, int i, int length) {
int temp = arr[i]; //先取出当前元素的值,保存在临时变量中
//开始调整
//1.k = i * 2 + 1 是i 节点的左子节点
for (int k = i * 2 + 1; k if (k + 1 k++; //k指向右子节点,目的是为了找到左右孩子节点中的最大值
}
if (arr[k] > temp) { //如果子节点大于父节点,说明需要调整
arr[i] = arr[k]; //把较大的值作为当前的树的父节点
i = k; // i 指向 k,继续循环比较
} else {
break;
}
}
//当for循环结束后,已经将以 i 为父节点的树的最大值,放在了顶端(局部)
arr[i] = temp; //将temp值放到调整后的位置
}
堆排序代码:
public static void heapSort(int[] arr) {
System.out.println(&#8220;堆排序&#8221;);
//将无序序列构建成一个大顶堆
for (int i = arr.length / 2 &#8211; 1; i >= 0; i&#8211;) {
adjustHeap(arr, i, arr.length);
}
//将堆顶元素和末尾元素进行交换,将最大的数放到数组的末尾
//再重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行 调整+交换 步骤,直到整个序列有序
for (int j = arr.length &#8211; 1; j >= 0; j&#8211;) {
//交换
int temp = arr[j];
arr[j] = arr[0];
arr[0] = temp;
adjustHeap(arr, 0, j);
}
// System.out.println(&#8220;调整后的数组 = &#8221; + Arrays.toString(arr));
}
构建大顶堆、堆排序实现(java)相关教程
每日算法&#8212;-删除排序数组中的重复项&#8212;-202010/5(4/4)(补)
每日算法&#8212;-删除排序数组中的重复项&#8212;-202010/5(4/4)(补) 目录 1. 题目描述 2. 示例 3. 思路 4. 遇上的问题 5. 具体实现代码 6. 学习收获,官方一如既往的妙啊 7 题目来源 1. 题目描述 给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元
冒泡排序时间 / 空间复杂度
冒泡排序时间 / 空间复杂度 ** 借鉴转载自十大经典排序算法 ** 十大算法复杂度: 冒泡排序 思想: 两两比较,A[i+1]A[i] 交换位置,循环i次 代码实现: class Solution { public static void main(String[] args) { int[] array = new int[]{2,2,3,1}; for(in
【排序】插入排序
【排序】插入排序 1、插入排序法介绍 插入式排序属于内部排序法,是对于欲排序的元素以插入的方式找寻该元素的适当位置,以达到排序的目的。 2、插入排序法思想 插入排序(Insertion Sorting)的基本思想是: 把n个待排序的元素看成为一个有序表和一个无序表
php如何实现排序算法
php实现排序算法的方法:1、冒泡排序,两两相比,每循环一轮就不用再比较最后一个元素;2、选择排序,选定一个作为基本值,剩下的和这个比较,再调换位置。 php实现排序算法的方法: 1、冒泡排序: 两两相比,每循环一轮就不用再比较最后一个元素了,因为最
LeetCode第 426 题:将二叉搜索树转化为排序的双向链表(C++)
LeetCode第 426 题:将二叉搜索树转化为排序的双向链表(C++) 426. 将二叉搜索树转化为排序的双向链表 一样的剑指 Offer 36. 二叉搜索树与双向链表_zj-CSDN博客,中序遍历一边遍历一边调整指针 class Solution {public: //left, right对应前驱、后继 Node *hea
C++ partial_sort(部分排序)
C++ partial_sort(部分排序) 参考:http://c.biancheng.net/view/564.html 假设有一个容器,它保存了 100 万个数值,但我们只对其中最小的 100 个感兴趣。可以对容器的全部内容排序,然后选择前 100 个元素,但这可能有点消耗时间。这时候需要使用部分排序
牛客IOI周赛19-普及组 A:小y的考试 (自定义排序)
牛客IOI周赛19-普及组 A:小y的考试 (自定义排序) 吐槽:这道题没什么难的,题意也很好懂,但是我竟然忘了 自定义排序函数时使用时还需要加上cmp,结果就很尴尬了,另外 sort 的时候也要注意数组的范围 sort(0,3) 只能将数组中 [0,3) 中的数进行排序 。 题面: 水题
按字典值排序&#8211;找出大小最大的十个文件
按字典值排序&#8211;找出大小最大的十个文件 问题分析: 需要确认某路径下所有文件的大小 需要排序,找出最大的十个 以字典的形式保存数据 准备知识: operator模块: fun = operator.itemgetter(1), fun 是一个由operator.itemgetter(1) 返回的函数,当函数fun作