算法基础:堆【以大根堆为例】

这篇具有很好参考价值的文章主要介绍了算法基础:堆【以大根堆为例】。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

二叉堆

二叉堆的逻辑结构就是一棵完全二叉树,所以也叫完全二叉堆

◼️ 鉴于完全二叉树的一些特性,二叉堆的底层(物理结构)一般用数组实现即可

◼️ 索引 i 的规律( n 是元素数量)

如果 i = 0 ,它是根节点

如果 i > 0 ,它的父节点的索引为 floor( (i – 1) / 2 ) (向下取整)

如果 2i + 1 ≤ n – 1,它的左子节点的索引为 2i + 1

如果 2i + 1 > n – 1 ,它无左子节点

如果 2i + 2 ≤ n – 1 ,它的右子节点的索引为 2i + 2

如果 2i + 2 > n – 1 ,它无右子节点
文章来源地址https://www.toymoban.com/news/detail-733611.html

大根堆的例子

public class HeapSort {

    public static void main(String[] args) {
        System.out.println("大顶堆测试");
        int[] arr = {68, 72, 43, 50, 38, 10, 90, 65};

        MyHeapSort obj = new MyHeapSort();
        for (int i : arr) {
            obj.add(i);
        }

        for (int i = 0; i < arr.length; i++) {
            arr[i] = obj.remove();
        }

        System.out.println("堆排序后:");
        for (int i : arr) {
            System.out.print(i + "  ");
        }
        // 90  72  68  65  50  43  38  10
        System.out.println();
        for (int i : arr) {  //堆空了,重新添加元素进去
            obj.add(i);
        }
        System.out.println("获取堆顶元素:" + obj.get());


        System.out.println("替换堆顶元素为13:" + obj.replace(13));
        System.out.println("替换堆顶元素为13后的堆顶元素:" + obj.get());
    }


    static class MyHeapSort {  //大根heap  由大到小的排序
        public int[] arr;
        public int size;
        public int defaultSize = 10;

        public MyHeapSort() {
            size = 0;
            arr = new int[defaultSize];
        }

        //扩容代码
        public void ensureCap(int cap) {
            int oldcap = arr.length;
            if (oldcap >= cap) return;
            //新容量为旧容量的1.5倍
            int newcap = oldcap + oldcap >> 1;
            int[] newarr = new int[newcap];
            for (int i = 0; i < size; i++) {
                newarr[i] = arr[i];
            }
            arr = newarr;
        }

        public void add(int val) {
            ensureCap(size + 1);
            arr[size++] = val;
            shiftup(size - 1);
        }

        //上滤
        public void shiftup(int index) {
            int cur = arr[index];
            while (index > 0) {
                int pindex = (index - 1) / 2;
                int parent = arr[pindex];
                if (parent >= cur) break;
                arr[index] = parent;
                index = pindex;
            }
            arr[index] = cur;
        }

        //删除:二叉堆的删除是删除堆顶元素
        //思路:最后一个元素代替堆顶元素,删除最后一个元素,然后下窜
        public int remove() {
            int last = --size;
            int root = arr[0];
            arr[0] = arr[last];
            //arr[last] 不用管了,因为长度要减1,减1后,最后一个元素也不存在了
            shiftdown(0);
            return root;
        }

        public void shiftdown(int index) {
            int half = size >> 1;
            int root = arr[0];
            while (index < half) {
                //index:只有左子节点,或者左右子节点都有
                int pos = (index << 1) + 1;
                int child = arr[pos];
                int right = pos + 1;
                if (right < size && arr[right] > arr[pos]) {
                    pos = right;
                    child = arr[right];
                }

                if (root > child) break;
                arr[index] = child;
                index = pos;
            }
            arr[index] = root;
        }


        public int get() {  //获取堆顶元素
            if (size == 0) return Integer.MIN_VALUE;
            return arr[0];
        }

        //删除堆顶的元素的同时,插入一个新元素
        public int replace(int ele) { //替换堆顶元素
            int root = Integer.MIN_VALUE;
            if (size == 0) {
                arr[0] = ele;
                size++;
            } else {
                root = arr[0];
                arr[0] = ele;
                shiftdown(0);
            }

            return root;
        }
    }
}



/*
大顶堆测试
堆排序后:
90  72  68  65  50  43  38  10
获取堆顶元素:90
替换堆顶元素为13:90
替换堆顶元素为13后的堆顶元素:72
 */

到了这里,关于算法基础:堆【以大根堆为例】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 数据结构与算法基础

    1.1、数组 已知5行5列的二维数组a中的各元素占两个字节,求元素a[2][3]按行优先存储的存储地址? 按行存:a+(5*2+3) 2=a+26 按列存:a+(5 3+2)*2=a+34 1.2、稀疏矩阵 在矩阵中,若数值为0的元素数目远远多于非0元素的数目,并且非0元素分布没有规律时,则称该矩阵为 稀疏矩阵 ;与之

    2024年02月04日
    浏览(40)
  • 【算法基础】数据结构

    826. 单链表 - AcWing题库 827. 双链表 - AcWing题库 828. 模拟栈 - AcWing题库 3302. 表达式求值 - AcWing题库 遍历输入的操作 如果是数字就存入num的堆栈 (同时注意123,2123这种长数字要一次性存入) 如果是(  直接存入op的堆栈 如果是  )就一直运算,直到遇到( 如果是操作符(如

    2024年02月12日
    浏览(45)
  • 【算法与数据结构】--算法基础--算法设计与分析

    一、贪心算法 贪心算法是一种解决优化问题的算法设计方法,其核心思想是在每一步选择当前状态下的最优解,从而希望最终达到全局最优解。下面将介绍贪心算法的原理、实现步骤,并提供C#和Java的实现示例。 1.1 原理: 贪心算法的原理基于局部最优选择,通过在每一步选

    2024年02月07日
    浏览(52)
  • 数据结构基础之排序算法

    在数据结构中,常见的排序算法有以下几种: 冒泡排序(Bubble Sort):通过比较相邻元素并交换它们的位置,每轮将最大(或最小)的元素冒泡到末尾,重复执行直到排序完成。 特点:简单易懂,但对于大型数据集效率较低。 时间复杂度: 最优情况:O(n)(当数组已经排序好

    2024年02月15日
    浏览(40)
  • 《数据结构与算法》之十大基础排序算法

    冒泡排序是一种交换排序,它的思路就是在待排序的数据中,两两比较相邻元素的大小,看是否满足大小顺序的要求,如果满足则不动,如果不满足则让它们互换。 然后继续与下一个相邻元素的比较,一直到一次遍历完成。一次遍历的过程就被成为一次冒泡,一次冒泡的结束

    2024年02月05日
    浏览(99)
  • 算法竞赛:初级算法(第一章:基础数据结构)

    动态链表 动态链表需要 临时分配链表节点 ,使用完毕后释放。 优点 :能及时释放空间,不使用多余内存 缺点 :需要管理空间,容易出错(竞赛一般不用动态链表) 静态链表 静态链表使用 预先分配的一段连续空间 存储链表,这种链表在逻辑上是成立的。 有两种做法:

    2024年01月19日
    浏览(49)
  • 【算法基础】(二)数据结构 --- 单链表

    ✨个人主页:bit me ✨当前专栏:算法基础 🔥专栏简介:该专栏主要更新一些基础算法题,有参加蓝桥杯等算法题竞赛或者正在刷题的铁汁们可以关注一下,互相监督打卡学习 🌹 🌹 🌹 实现一个单链表,链表初始为空,支持三种操作: 向链表头插入一个数; 删除第 k 个插

    2023年04月17日
    浏览(98)
  • 【算法集训】基础数据结构:十、矩阵

    矩阵其实就是二维数组,这些题目在9日集训中已经做过,这里做的方法大致相同。

    2024年02月04日
    浏览(40)
  • 【Go基础】加密算法和数据结构

    加密过程的每一步都是可逆的 加密和解密用的是同一组密钥 异或是最简单的对称加密算法 DES(Data Encryption Standard)数据加密标准,是目前最为流行的加密算法之一 对原始数据(明文)进行分组,每组64位,最后一组不足64位时按一定规则填充,每一组上单独施加DES算法 DES子

    2024年02月02日
    浏览(33)
  • C++基础-介绍·数据结构·排序·算法

    C++是一门风格严谨又不失自由的开发语言,提供了完整的内存管理、支持函数式编程和面向对象编程,支持模板、多继承、多实现、重载、重写等多态特性。 优势在于目前90%的操作系统、数据库、应用基础架构、硬件嵌入式等都是使用C/C++制作的,而C++是对C的标准扩展,掌握

    2024年02月03日
    浏览(45)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包