【排序算法】二叉树的实际应用堆排序

简介: 【排序算法】二叉树的实际应用堆排序

堆排序

堆排序基本介绍

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复 杂度均为 O(nlogn),它也是不稳定排序。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆, 注意 : 没有 要求结点的左孩子的值和右孩子的值的大小关系。

每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆


大顶堆

2.png


小顶堆

3.png


堆排序基本思想

将待排序序列构造成一个大顶堆

此时,整个序列的最大值就是堆顶的根节点。

将其与末尾元素进行交换,此时末尾就为最大值。

然后将剩余 n-1 个元素重新构造成一个堆,这样会得到 n 个元素的次小值。如此反复执行,便能得到一个有序序列了。

可以看到在构建大顶堆的过程中,元素的个数逐渐减少,最后就得到一个有序序列了.


堆排序步骤图解说明

步骤一 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆)。 原始的数组 [4, 6, 8, 5, 9]

假设给定无序序列结构如下

4.png



此时我们从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点


arr.length/2-1=5/2-1=1,也就是下面的 6 结点),从左至右,从下至上进行调整。

5.png



找到第二个非叶节点 4,由于[4,9,8]中 9 元素最大,4 和 9 交换。

6.png



这时,交换导致了子根[4,5,6]结构混乱,继续调整,[4,5,6]中 6 最大,交换 4 和 6。

7.png



此时,我们就将一个无序序列构造成了一个大顶堆。


步骤二 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换.


得到第二大元素。如此反复进行交换、重建、交换。


.将堆顶元素 9 和末尾元素 4 进行交换

8.png



重新调整结构,使其继续满足堆定义

9.png



再将堆顶元素 8 与末尾元素 5 进行交换,得到第二大元素 8

10.png



后续过程,继续进行调整,交换,如此反复进行,最终使得整个序列有序

11.png

12.png

总结下堆排序的基本思路:

将无序序列构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;

将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤, 直到整个序列有序.


代码实现

要求:给你一个数组 {4,6,8,5,9} , 要求使用堆排序法,将数组升序排序。


堆排序不是很好理解,老师通过 Debug 帮助大家理解堆排序

堆排序的速度非常快,在我的机器上 8 百万数据 3 秒左右。O(nlogn)

package com.hyc.DataStructure.tree;


package com.hyc.DataStructure.tree;
/**
 * @projectName: DataStructure
 * @package: com.hyc.DataStructure.tree
 * @className: HeapSort
 * @author: 冷环渊 doomwatcher
 * @description: TODO
 * @date: 2022/2/6 23:52
 * @version: 1.0
 */
public class HeapSort {
    public static void main(String[] args) {
        int[] test = new int[8000000];
        //测试数据
        for (int i = 0; i < 8000000; i++) {
            test[i] = (int) (Math.random() * 800000);
        }
        long time = System.currentTimeMillis();
        heapsort(test);
        long end = System.currentTimeMillis();
        long t = ((end - time) / 1000);
        System.out.println("一共用时 " + t + "秒");
        int arr[] = {4, 6, 8, 5, 9};
    }
    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 j = arr.length - 1; j > 0; j--) {
            temp = arr[j];
            arr[j] = arr[0];
            arr[0] = temp;
            adjustHeap(arr, 0, j);
        }
        //System.out.println("排序后的数组是 = " + Arrays.toString(arr));
    }
    /**
     * @author 冷环渊 Doomwatcher
     * @context:
     * 大顶堆交换思路, 判断左右节点大小,之后判断左右节点的比对结果,与父节点判断,将最大值交还给父节点
     * @date: 2022/2/6 23:54
     * @param arr 存放需要将交换节点的数组
     * @param i   需要做调整的父节点索引
     * @param length 有多少节点需要调整
     * @return: void
     */
    public static void adjustHeap(int[] arr, int i, int length) {
        int temp = arr[i];
        //   开始调整
        /* 说明
         * k =i*2+1按照之前线索查找树的公式,找出左子树的节点位置
         * */
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            //判断条件 k(节点索引)首先不能大于我们要遍历的结点索引总数,之后判断左右节点的大小,交换
            if (k + 1 < length && arr[k] < arr[k + 1]) {
                k++;
            }
            //找出最大的子节点,与父节点的值比对,
            if (arr[k] > temp) {
                //将较大的值放入到父节点
                arr[i] = arr[k];
                i = k; //i指向k , 继续循环比较
            } else {
                break;
            }
        }
        //    for 循环结束之后 我们i已经是父节点以及最大值的索引了
        // 将 temp 调整到最后得位置
        arr[i] = temp;
    }
}


相关文章
|
1月前
|
存储 监控 JavaScript
基于布隆过滤器的 Node.js 算法在局域网电脑桌面监控设备快速校验中的应用研究
本文探讨了布隆过滤器在局域网电脑桌面监控中的应用,分析其高效空间利用率、快速查询性能及动态扩容优势,并设计了基于MAC地址的校验模型,提供Node.js实现代码,适用于设备准入控制与重复数据过滤场景。
69 0
|
10天前
|
机器学习/深度学习 资源调度 算法
遗传算法模型深度解析与实战应用
摘要 遗传算法(GA)作为一种受生物进化启发的优化算法,在复杂问题求解中展现出独特优势。本文系统介绍了GA的核心理论、实现细节和应用经验。算法通过模拟自然选择机制,利用选择、交叉、变异三大操作在解空间中进行全局搜索。与梯度下降等传统方法相比,GA不依赖目标函数的连续性或可微性,特别适合处理离散优化、多目标优化等复杂问题。文中详细阐述了染色体编码、适应度函数设计、遗传操作实现等关键技术,并提供了Python代码实现示例。实践表明,GA的成功应用关键在于平衡探索与开发,通过精心调参维持种群多样性同时确保收敛效率
52 7
|
10天前
|
存储 算法 搜索推荐
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
专攻软考高频算法,深度解析二分查找、堆排序、快速排序核心技巧,对比九大排序算法,配套动画与真题,7天掌握45%分值模块。
52 0
软考算法破壁战:从二分查找到堆排序,九大排序核心速通指南
|
10天前
|
机器学习/深度学习 边缘计算 人工智能
粒子群算法模型深度解析与实战应用
蒋星熠Jaxonic是一位深耕智能优化算法领域多年的技术探索者,专注于粒子群优化(PSO)算法的研究与应用。他深入剖析了PSO的数学模型、核心公式及实现方法,并通过大量实践验证了其在神经网络优化、工程设计等复杂问题上的卓越性能。本文全面展示了PSO的理论基础、改进策略与前沿发展方向,为读者提供了一份详尽的技术指南。
36 0
粒子群算法模型深度解析与实战应用
|
10天前
|
机器学习/深度学习 算法 安全
小场景大市场:猫狗识别算法在宠物智能设备中的应用
将猫狗识别算法应用于宠物智能设备,是AIoT领域的重要垂直场景。本文从核心技术、应用场景、挑战与趋势四个方面,全面解析这一融合算法、硬件与用户体验的系统工程。
|
2月前
|
机器学习/深度学习 人工智能 算法
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
AI-Compass 强化学习模块:理论到实战完整RL技术生态,涵盖10+主流框架、多智能体算法、游戏AI与金融量化应用
|
1月前
|
算法 数据可视化
matlab版本粒子群算法(PSO)在路径规划中的应用
matlab版本粒子群算法(PSO)在路径规划中的应用
|
2月前
|
存储 监控 算法
公司员工泄密防护体系中跳表数据结构及其 Go 语言算法的应用研究
在数字化办公中,企业面临员工泄密风险。本文探讨使用跳表(Skip List)数据结构优化泄密防护系统,提升敏感数据监测效率。跳表以其高效的动态数据处理能力,为企业信息安全管理提供了可靠技术支持。
53 0
|
4天前
|
传感器 机器学习/深度学习 算法
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
【使用 DSP 滤波器加速速度和位移】使用信号处理算法过滤加速度数据并将其转换为速度和位移研究(Matlab代码实现)
|
5天前
|
传感器 算法 数据挖掘
基于协方差交叉(CI)的多传感器融合算法matlab仿真,对比单传感器和SCC融合
基于协方差交叉(CI)的多传感器融合算法,通过MATLAB仿真对比单传感器、SCC与CI融合在位置/速度估计误差(RMSE)及等概率椭圆上的性能。采用MATLAB2022A实现,结果表明CI融合在未知相关性下仍具鲁棒性,有效降低估计误差。

热门文章

最新文章