堆排序,以及大顶堆构造过程Java实现

这篇具有很好参考价值的文章主要介绍了堆排序,以及大顶堆构造过程Java实现。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

import java.util.Arrays;

public class Main {
    public static void main(String[] args) {
        int a[] = new int[] { 1, 1, 23, 456, 0 };
        // int a初始化方式
        int bb[] = { 1, 2, 3, 4 };
        // int c[5] = {1,2,34,5,6};//错误
        int d[] = new int[6]; // 初始为0
        // int e[] = new int[5]{1,2,34,52,2}; 错误
        int f[] = new int[] { 1, 2, 3, 4, 5, 6 };
        for (int i = 0; i != 6; ++i) {
            System.out.println("ay i=" + d + ",value=" + d[i]);
        }
        System.out.println("------------");
        // Arrays.fill(a, 0, 6, 1);
        Arrays.parallelSort(a, 0, 5);
        // 快速升序排序

        for (int i = 0; i != 5; ++i) {
            System.out.println("ay i=" + i + ",value=" + a[i]);
        }

        int[] b = Arrays.copyOfRange(a, 1, 7);
        // Array是copy,是浅copy,from需要小于长度,to超过长度将初始化为0
        for (int i = 0; i != 6; ++i) {
            System.out.println("by i=" + i + ",value=" + b[i]);
        }
        int heap_max[] = { 111, 2121, 222, 113, 11111114, 5111, 1, 3, 24, 1, 213, 123 };
        // maxHeap(heap_max, 5);
        int size = 12;

        while (size > 0) {
            maxHeap(heap_max, size);
            int last = heap_max[size - 1];
            heap_max[size - 1] = heap_max[0];
            heap_max[0] = last;
            size--;

        }

    }

    static void maxHeap(int a[], int size) {
        int last_index = size - 1;

        // 自下而上检测
        while (last_index > 0) {
            int root_index = last_index / 2;
            if (last_index % 2 == 0) {
                root_index = root_index - 1;
            } else {
            }
            int root = a[root_index];
            int left = a[root_index * 2 + 1];
            int right = 0;
            if (root_index * 2 + 2 < size) {
                right = a[root_index * 2 + 2];
            }
            if (root < left) {
                if (left < right) {
                    int rc = root;
                    a[root_index] = right;
                    a[root_index * 2 + 2] = rc;
                } else {
                    int rc = root;
                    a[root_index] = left;
                    a[root_index * 2 + 1] = rc;
                }
            } else {
                if (root < right) {
                    int rc = root;
                    a[root_index] = right;
                    a[root_index * 2 + 2] = rc;
                }
            }
            last_index -= 2;
            // System.out.println(Arrays.toString(a));
        }

        // 自上而下检测所有根节点
        int index = 0;
        while (index < size) {
            int root_index = index;
            int root = a[root_index];
            int left_index = root_index * 2 + 1;
            int left = 0;
            if (left_index < size) {
                left = a[left_index];
            } else {
                left = -1;
                break;
            }
            int right_index = root_index * 2 + 2;
            int right = 0;
            if (right_index < size) {
                right = a[right_index];
            } else {
                right = -1;
                break;
            }
            if (root < left) {
                if (left < right) {
                    int rc = root;
                    a[root_index] = a[right_index];
                    a[right_index] = rc;
                } else {
                    int rc = root;
                    a[root_index] = a[left_index];
                    a[left_index] = rc;
                }
            } else {
                if (root < right) {
                    int rc = root;
                    a[root_index] = a[right_index];
                    a[right_index] = rc;
                }
            }
            index++;
            // System.out.println(Arrays.toString(a));
        }
        System.out.println(Arrays.toString(a));
    }
}

先上代码,堆排序一直是稀里糊涂的。找了视频,一看就明白了,自己动手撸了一下。

一般用数组构建一种堆的关系。在数组中

每个根节点的下标

root_index = left_child_index/2

root_index = right_child_index/2 -1;

 文章来源地址https://www.toymoban.com/news/detail-697816.html

left_child_index = 2*root_index+1;

right_child_index = 2*root_index+2;

 

记住这个关系,然后按照i堆的构建顺序执行:

1.   构建2叉树,即按照上述位置关系构建

2.  自下而上检测:

         依次从最后一个节点开始,查找每个节点的根节点,然后根据根节点,继续找出左右子节点,在三个节点中取最大值和根节点交换位置

3.  自上而下检测

        依次从一个节点开始,查找每个节点的左右子节点,在三个节点中取最大值和根节点交换位置

 

记住这三条顺序,就行了。

Tips:

     具体编码建议,在第二步中,如果依次遍历,将会存在大量重复计算节点的操作。因为是从叶节点开始,那么每个节点有两个叶节点,就会找两次,所以每次找完,下标-2就行,直接进入下一个根节点

        第三步中,有可能找不到叶节点,当找不到左右节点时,直接跳出循环就行了,说明已经将所有的根节点找完了。根找完了,就说明调整完毕。

最后是打印的顺序。

[11111114, 2121, 5111, 113, 213, 222, 1, 3, 24, 1, 111, 123]
[5111, 2121, 222, 113, 213, 123, 1, 3, 24, 1, 111, 11111114]
[2121, 213, 222, 113, 111, 123, 1, 3, 24, 1, 5111, 11111114]
[222, 213, 123, 113, 111, 1, 1, 3, 24, 2121, 5111, 11111114]
[213, 113, 123, 24, 111, 1, 1, 3, 222, 2121, 5111, 11111114]
[123, 113, 3, 24, 111, 1, 1, 213, 222, 2121, 5111, 11111114]
[113, 111, 3, 24, 1, 1, 123, 213, 222, 2121, 5111, 11111114]
[111, 24, 3, 1, 1, 113, 123, 213, 222, 2121, 5111, 11111114]
[24, 1, 3, 1, 111, 113, 123, 213, 222, 2121, 5111, 11111114]
[3, 1, 1, 24, 111, 113, 123, 213, 222, 2121, 5111, 11111114]
[1, 1, 3, 24, 111, 113, 123, 213, 222, 2121, 5111, 11111114]
[1, 1, 3, 24, 111, 113, 123, 213, 222, 2121, 5111, 11111114]

堆排序的过程。

第一步:
    每次用数组中的[0,N)个元素构建堆。构建结束后,最大的数位于0下标位置。

第二步:将0下标和数组中最后一个元素交换位置。交换后,最大的数位于最后一个位置上

第三步:N=N-1 ,重复第一步,N=1跳出循环就行了

总结:

还是用java刷题爽,用C++没那么方便。后面干到200题去面MS

 

 

到了这里,关于堆排序,以及大顶堆构造过程Java实现的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 从前序与中序遍历序列来构造二叉树         1.1 实现从前序与中序遍历序列来构造二叉树思路            1.2 代码实现从前序与中序遍历序列来构造二叉树         2.0 从中序

    2024年02月05日
    浏览(75)
  • 用Java(C语言也可以看)实现冒泡排序和折半查找(详细过程图)+逆序数组

      目录 一、冒泡排序 1.冒泡排序介绍 2.排序的思路 3.完整代码 二、折半查找 1.折半查找介绍 2.查找的思路 3.完整代码 三、逆序数组 1.逆序思路 2..完整代码 冒泡排序是众多排序的一种,无论在C语言或者Java中都很常见,后续在数据结构中也会用到 1.冒泡排序介绍 (1)冒泡排

    2024年02月05日
    浏览(43)
  • LeetCode·每日一题·1851. 包含每个查询的最小区间·优先队列(小顶堆)

        离线查询:  输入的结果数组queries[]是无序的。如果我们按照输入的queries[]本身的顺序逐个查看,时间复杂度会比较高。 于是,我们将queries[]数组按照数值大小,由小到大逐个查询,这种方法称之为离线查询。 位运算:  离线查询的时候,queries[]可以按照数值大小逐个

    2024年02月16日
    浏览(48)
  • 【LeetCode力扣】75 快速排序的子过程partition(荷兰国旗问题)

    目录 1、题目介绍 2、解题思路 2.1、冒泡排序暴力破解 2.2、快速排序的子过程partition 2.2.1、详细过程描述 2.2.2、代码描述 原题链接: 75. 颜色分类 - 力扣(LeetCode) 示例 1: 输入:nums = [2,0,2,1,1,0] 输出:[0,0,1,1,2,2] 示例 2: 输入:nums = [2,0,1] 输出:[0,1,2]   提示: n == nums.len

    2024年02月08日
    浏览(36)
  • 【经典算法】 leetcode88.合并排序的数组(Java/C/Python3实现含注释说明,Easy)

    作者主页: 🔗进朱者赤的博客 精选专栏:🔗经典算法 作者简介:阿里非典型程序员一枚 ,记录在大厂的打怪升级之路。 一起学习Java、大数据、数据结构算法( 公众号同名 ) ❤️觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论,💬支持博主,记得点个大大的 关

    2024年04月22日
    浏览(39)
  • 人工智能(Pytorch)搭建GRU网络,构造数据实现训练过程与评估

    大家好,我是微学AI,今天给大家介绍一下人工智能(Pytorch)搭建模型3-GRU网络的构建,构造数据实现训练过程与评估,让大家了解整个训练的过程。 GRU(Gated Recurrent Unit,门控循环单元)是一种循环神经网络(RNN)的变体,用于处理序列数据。对于每个时刻,GRU模型都根据当前

    2023年04月09日
    浏览(55)
  • 【ElasticSearch】使用 Java 客户端 RestClient 实现对文档的查询操作,以及对搜索结果的排序、分页、高亮处理

    在 Elasticsearch 中,通过 RestAPI 进行 DSL 查询语句的构建通常是通过 HighLevelRestClient 中的 resource() 方法来实现的。该方法包含了查询、排序、分页、高亮等所有功能,为构建复杂的查询提供了便捷的接口。 RestAPI 中构建查询条件的核心部分是由一个名为 QueryBuilders 的工具类提供

    2024年01月16日
    浏览(59)
  • 【Java EE】-HTTP请求构造以及HTTPS的加密流程

    作者 :学Java的冬瓜 博客主页 :☀冬瓜的主页🌙 专栏 :【JavaEE】 分享 : 在满园弥漫的沉静的光芒之前,一个人更容易看到时间,并看到自己的身影。——史铁生《我与地坛》 主要内容 :构造http请求,不需要写代码直接发送http请求:地址栏输入地址,html中 img标签,scri

    2024年02月02日
    浏览(43)
  • 全面理解java中的构造方法以及this关键字的用法(超详细)

    Hello,各位铁汁们!我是小🐟儿哈!今天我又来更新我的Java基础学习博客了。 本篇主要内容概述: 1、🍚如何用构造方法初始化对象 2、🍚为啥要有this这个 3、🍚this.属性名访问成员变量、成员方法 4、🍚this.方法名 || this.()的用法 目录 初识构造方法  构造方法的使

    2023年04月09日
    浏览(62)
  • 归并排序的具体实现过程

    作者主页: paper jie的博客_CSDN博客-C语言,算法详解领域博主 本文作者: 大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文录入于 《算法详解》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造,将算法基础知识一网打尽,希望

    2024年02月12日
    浏览(28)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包