算法与数据结构全阶班-左程云版(二)基础阶段之4.堆和比较器(上)

简介: 本文主要介绍了堆和比较器:堆包括大根堆和小根堆;比较器的实质就是重载比较运算符,可以用于普通方式的排序和自定义的排序。

前言

本文主要介绍了堆和比较器:堆包括大根堆和小根堆;比较器的实质就是重载比较运算符,可以用于普通方式的排序和自定义的排序。

1.堆

完全二叉树

上面层的节点都是满的,最下层要么是满的,要么左边节点是满的且连续的。

数组也能实现完全二叉树:

2345_image_file_copy_132.jpg

有的实现中,0位置不用,从1开始:

2345_image_file_copy_133.jpg

这样做的原因是可以直接使用位运算代替算术运算,提高运算速度。

堆结构:

1)堆结构就是用数组实现的完全二叉树结构;

2)完全二叉树中如果每棵子树的最大值都在顶部就是大根堆;

3)完全二叉树中如果每棵子树的最小值都在顶部就是小根堆;

4)堆结构的heapInsert与heapify操作;

5)堆结构的增大和减少;

6)优先级队列结构,就是堆结构。

堆是在完全二叉树的基础上实现的,分为大根堆和小根堆:

大根堆:

每一个子树的最大值都是该子树头节点的值。

举例如下:


2345_image_file_copy_134.jpg

2345_image_file_copy_135.jpg

小根堆:

每一个子树的最小值都是该子树头节点的值。

将给定的一系列数组成为大根堆。

图示如下:

2345_image_file_copy_137.jpg

实现大根堆如下:

package heap04;
/**
 * @author Corley
 * @date 2021/10/12 20:16
 * @description LeetCodeAlgorithmZuo-heap04
 */
public class Heap {
    class MaxHeap {
        private int[] heap;
        private final int limit;
        private int heapSize;
        MaxHeap(int limit) {
            heap = new int[limit];
            this.limit = limit;
            heapSize = 0;
        }
        /*
        加入新元素
         */
        public void push(int value) {
            if (heapSize == limit) {
                throw new RuntimeException("Heap is full!");
            }
            heap[heapSize++] = value;
            heapInsert(heap, heapSize);
        }
        /*
        新加进来的数,现在停在了index位置,请依次往上移动
         */
        private void heapInsert(int[] arr, int index) {
            while (arr[index] > arr[(index - 1) / 2]) {
                swap(arr, index, (index - 1) / 2);
            }
        }
        public void swap(int[] arr, int i, int j) {
            int tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
    }
}

现在分析加入元素时调整堆结构的代价:

堆的深度为LogN级别;

所以加入新元素时调整为二根堆的代价也为LogN。

实现找到大根堆中的最大值,并删除最大值,然后再调整为大根堆。

示意如下:

2345_image_file_copy_138.jpg

实现如下:

/*
* 实现找到大根堆中的最大值,并删除最大值,然后再调整为大根堆
* */
public int pop() {
    int ans = heap[0];
    swap(heap, 0, --heapSize);
    heapify(heap, 0, heapSize);
    return ans;
}
/*
从index位置,往下看,不断的下沉
停:较大的子节点都不再比index位置的数大;已经没子节点
 */
public void heapify(int[] arr, int index, int heapSize) {
    int left = 2 * index + 1;
    while (left < heapSize) {
        int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
        largest = arr[largest] > arr[index] ? largest : index;
        if (largest == index) {
            break;
        }
        swap(arr, largest, index);
        index = largest;
        left = 2 * index + 1;
    }
}

显然,heapify方法的复杂度也是LogN。


相关文章
基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究
跳表(Skip List)是一种基于概率的数据结构,适用于企业局域网监控中海量连接记录的高效处理。其通过多层索引机制实现快速查找、插入和删除操作,时间复杂度为 $O(\log n)$,优于链表和平衡树。跳表在异常连接识别、黑名单管理和历史记录溯源等场景中表现出色,具备实现简单、支持范围查询等优势,是企业网络监控中动态数据管理的理想选择。
16 0
|
4月前
|
算法系列之数据结构-二叉树
树是一种重要的非线性数据结构,广泛应用于各种算法和应用中。本文介绍了树的基本概念、常见类型(如二叉树、满二叉树、完全二叉树、平衡二叉树、B树等)及其在Java中的实现。通过递归方法实现了二叉树的前序、中序、后序和层次遍历,并展示了具体的代码示例和运行结果。掌握树结构有助于提高编程能力,优化算法设计。
105 10
 算法系列之数据结构-二叉树
|
4月前
|
算法系列之数据结构-Huffman树
Huffman树(哈夫曼树)又称最优二叉树,是一种带权路径长度最短的二叉树,常用于信息传输、数据压缩等方面。它的构造基于字符出现的频率,通过将频率较低的字符组合在一起,最终形成一棵树。在Huffman树中,每个叶节点代表一个字符,而每个字符的编码则是从根节点到叶节点的路径所对应的二进制序列。
124 3
 算法系列之数据结构-Huffman树
|
4月前
|
算法系列之数据结构-二叉搜索树
二叉查找树(Binary Search Tree,简称BST)是一种常用的数据结构,它能够高效地进行查找、插入和删除操作。二叉查找树的特点是,对于树中的每个节点,其左子树中的所有节点都小于该节点,而右子树中的所有节点都大于该节点。
114 22
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
145 30
机器人路径规划和避障算法matlab仿真,分别对比贪婪搜索,最安全距离,RPM以及RRT四种算法
本程序基于MATLAB 2022A实现机器人路径规划与避障仿真,对比贪婪搜索、最安全距离、RPM和RRT四种算法。通过地图模拟环境,输出各算法的路径规划结果,展示其在避障性能与路径优化方面的差异。代码包含核心路径搜索逻辑,并附有测试运行图示,适用于机器人路径规划研究与教学演示。
111 64
基于精英个体保留策略遗传优化的生产调度算法matlab仿真
本程序基于精英个体保留策略的遗传算法,实现生产调度优化。通过MATLAB仿真,输出收敛曲线与甘特图,直观展示调度结果与迭代过程。适用于复杂多约束生产环境,提升资源利用率与调度效率。
基于FPGA的图像退化算法verilog实现,分别实现横向和纵向运动模糊,包括tb和MATLAB辅助验证
本项目基于FPGA实现图像运动模糊算法,包含横向与纵向模糊处理流程。使用Vivado 2019.2与MATLAB 2022A,通过一维卷积模拟点扩散函数,完成图像退化处理,并可在MATLAB中预览效果。
|
24天前
|
基于BigBangBigCrunch优化(BBBC)的目标函数求解算法matlab仿真
本程序基于BigBang-BigCrunch优化算法(BBBC)实现目标函数求解的MATLAB仿真,具备良好的全局搜索与局部收敛能力。程序输出适应度收敛曲线及多变量变化曲线,展示算法迭代过程中的优化趋势。使用MATLAB 2022A运行,通过图形界面直观呈现“大爆炸”与“大坍缩”阶段在解空间中的演化过程,适用于启发式优化问题研究与教学演示。
基于PSO粒子群优化的BiLSTM双向长短期记忆网络序列预测算法matlab仿真,对比BiLSTM和LSTM
本项目基于MATLAB2022a/2024b开发,结合粒子群优化(PSO)算法与双向长短期记忆网络(BiLSTM),用于优化序列预测任务中的模型参数。核心代码包含详细中文注释及操作视频,涵盖遗传算法优化过程、BiLSTM网络构建、训练及预测分析。通过PSO优化BiLSTM的超参数(如学习率、隐藏层神经元数等),显著提升模型捕捉长期依赖关系和上下文信息的能力,适用于气象、交通流量等场景。附有运行效果图预览,展示适应度值、RMSE变化及预测结果对比,验证方法有效性。

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问