堆的调整方法:shift up 和 shift down

发布时间: 2024-05-02 06:31:31 阅读量: 8 订阅数: 12
![堆的调整方法:shift up 和 shift down](https://img-blog.csdn.net/20161127085050890?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQv/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center) # 1. 向上调整 ### 2.1.1 Shift Up 的基本原理 Shift Up 是堆调整的一种操作,用于将一个新元素插入堆中并保持堆的性质。其基本原理是: - 将新元素插入堆的末尾。 - 比较新元素与其父节点的值。 - 如果新元素的值大于父节点,则交换新元素和父节点的位置。 - 重复上述步骤,直到新元素到达堆的正确位置。 ### 2.1.2 Shift Up 的实现步骤 ```python def shift_up(heap, i): """向上调整堆中索引为 i 的元素。 Args: heap: 堆的列表表示。 i: 要调整元素的索引。 """ while i > 0: parent = (i - 1) // 2 if heap[i] > heap[parent]: heap[i], heap[parent] = heap[parent], heap[i] i = parent else: break ``` # 2. 堆的调整方法 堆的调整操作是维持堆性质的关键,分为向上调整(Shift Up)和向下调整(Shift Down)两种方式。 ### 2.1 Shift Up:向上调整 #### 2.1.1 Shift Up 的基本原理 向上调整操作用于将一个新元素插入堆中时,将其向上移动到适当的位置,以满足堆的性质。具体而言,新元素会与它的父节点进行比较,如果新元素的值比父节点大(对于最大堆)或小(对于最小堆),则将新元素与父节点交换,并继续与父节点的父节点进行比较,直至新元素找到合适的位置。 #### 2.1.2 Shift Up 的实现步骤 ```python def shift_up(heap, i): """向上调整堆中第 i 个元素。 Args: heap: 堆列表。 i: 要调整的元素的索引。 """ while i > 0: parent = (i - 1) // 2 if heap[i] > heap[parent]: # 对于最大堆 heap[i], heap[parent] = heap[parent], heap[i] i = parent ``` **逻辑分析:** * `while i > 0`:循环直到到达堆的根节点。 * `parent = (i - 1) // 2`:计算父节点的索引。 * `if heap[i] > heap[parent]`:对于最大堆,比较新元素与父节点的值。如果新元素更大,则交换它们。 * `i = parent`:将当前索引更新为父节点的索引,继续向上比较。 ### 2.2 Shift Down:向下调整 #### 2.2.1 Shift Down 的基本原理 向下调整操作用于删除堆顶元素后,将堆中最后一个元素移动到适当的位置,以满足堆的性质。具体而言,最后一个元素会与它的左右子节点进行比较,如果最后一个元素的值比子节点小(对于最大堆)或大(对于最小堆),则将最后一个元素与较大的子节点交换,并继续与较大的子节点的左右子节点进行比较,直至最后一个元素找到合适的位置。 #### 2.2.2 Shift Down 的实现步骤 ```python def shift_down(heap, i, size): """向下调整堆中第 i 个元素。 Args: heap: 堆列表。 i: 要调整的元素的索引。 size: 堆的大小。 """ while 2 * i + 1 < size: left = 2 * i + 1 right = 2 * i + 2 if right < size and heap[right] > heap[left]: # 对于最大堆 max_child = right else: max_child = left if heap[i] < heap[max_child]: heap[i], heap[max_child] = heap[max_child], heap[i] i = max_child ``` **逻辑分析:** * `while 2 * i + 1 < size`:循环直到到达堆的最后一个节点。 * `left = 2 * i + 1`:计算左子节点的索引。 * `right = 2 * i + 2`:计算右子节点的索引。 * `if right < size and heap[right] > heap[left]`:对于最大堆,比较左右子节点的值。如果右子节点更大,则将 `max_child` 设置为右子节点的索引。 * `if heap[i] < heap[max_child]`:比较当前元素与 `max_child` 的值。如果当前元素更小,则交换它们。 * `i = max_child`:将当前索引更新为 `max_child` 的索引,继续向下比较。 # 3. 堆的构建 ### 3.1 堆的构建方法 堆的构建方法主要有两种:直接构建法和堆化法。 #### 3.1.1 直接构建法 直接构建法是指从空堆开始,逐个插入元素,并对每个新插入的元素进行向上调整,直到堆满足堆的性质。 ```python def build_heap_direct(arr): ```
corwn 最低0.47元/天 解锁专栏
赠618次下载
profit 百万级 高质量VIP文章无限畅学
profit 千万级 优质资源任意下载
profit C知道 免费提问 ( 生成式Al产品 )

相关推荐

专栏简介
本专栏深入探讨了堆的数据结构,从基本概念和操作原理到各种应用场景。它涵盖了堆排序算法、优先队列、Top K 问题、滑动窗口最大值问题、连续中值问题等应用。此外,它还比较了堆与快速排序和二叉搜索树,分析了堆的构建方法和调整方法。专栏还介绍了堆在操作系统、定时任务调度和数据流中位数问题中的应用。它还探讨了堆的扩展应用,如外部排序算法和最小生成树算法。通过深入的分析和示例,本专栏旨在为读者提供对堆及其广泛应用的全面理解。
最低0.47元/天 解锁专栏
赠618次下载
百万级 高质量VIP文章无限畅学
千万级 优质资源任意下载
C知道 免费提问 ( 生成式Al产品 )

最新推荐

MATLAB换行符在教育中的价值:提升教学质量,培养未来技术人才

![MATLAB换行符在教育中的价值:提升教学质量,培养未来技术人才](https://segmentfault.com/img/bVUW5e?w=1920&h=1006) # 1. MATLAB 换行符基础** 换行符是 MATLAB 中用于分隔代码行的特殊字符。它在代码可读性、可维护性、效率和协作方面发挥着至关重要的作用。在 MATLAB 中,换行符通常由回车键(Enter)表示,并在代码编辑器中显示为一个空行。 换行符有助于将代码逻辑地组织成不同的段落,使代码更易于阅读和理解。它还可以通过减少内存占用和执行时间来提高代码效率。此外,换行符促进团队协作,确保代码一致性和可读性,从而促进

MATLAB图像锐化行业应用:图像锐化在医学、工业、安防等领域的应用,探索图像锐化的广阔前景

![MATLAB图像锐化行业应用:图像锐化在医学、工业、安防等领域的应用,探索图像锐化的广阔前景](https://www.pvmedtech.com/upload/2020/8/ffa1eb14-e2c1-11ea-977c-fa163e6bbf40.png) # 1. 图像锐化的理论基础** 图像锐化是一种图像处理技术,旨在增强图像的清晰度和细节。其基本原理是通过突出图像中的边缘和纹理,从而使图像看起来更清晰、更锐利。 图像锐化的理论基础基于空间域和频域两种不同的图像表示方式。在空间域中,图像被视为像素阵列,每个像素具有亮度和颜色值。通过应用卷积核(一个小的过滤器)对图像进行卷积运算,

Matlab自相关函数并行化技巧:大数据分析效率提升

![Matlab自相关函数并行化技巧:大数据分析效率提升](https://blog.v8080.com/usr/uploads/2023/07/3801385758.png) # 1. Matlab自相关函数简介 自相关函数是时域信号处理中一种重要的分析工具,它可以用来衡量信号自身在不同时间偏移下的相似性。在Matlab中,自相关函数可以通过`xcorr`函数计算。该函数接受两个输入信号,并输出一个表示信号自相关性的向量。 自相关函数在信号处理中有着广泛的应用,例如: * **模式识别:**自相关函数可以用来识别信号中的重复模式。 * **故障诊断:**自相关函数可以用来检测信号中的异

Matlab坐标轴范围3D坐标轴教程:创建3D图表,展示多维数据,提升数据可视化

![Matlab坐标轴范围3D坐标轴教程:创建3D图表,展示多维数据,提升数据可视化](https://img-blog.csdnimg.cn/img_convert/1a36558cefc0339f7836cca7680c0aef.png) # 1. Matlab 3D 坐标轴简介** Matlab 3D 坐标轴是一种用于在三维空间中可视化数据的工具。它允许用户创建和操作 3D 坐标系,并绘制各种类型的图表,包括散点图、折线图、曲面图和体积图。 3D 坐标轴由三个正交轴组成:x 轴、y 轴和 z 轴。这些轴定义了空间中的三个维度,并且可以根据需要进行缩放和旋转。坐标轴还可以带有标签和标题

避免MATLAB高斯拟合的常见陷阱:规避错误,保障拟合准确性

![matlab高斯拟合](https://img-blog.csdnimg.cn/89e4a15fbfac4a259e236e75fbb89488.png) # 1. 高斯拟合的理论基础 高斯拟合是一种统计建模技术,用于拟合正态分布的数据。它在科学、工程和商业等领域有着广泛的应用。 **高斯分布** 高斯分布,又称正态分布,是一种连续概率分布。其概率密度函数由以下公式给出: ``` f(x) = (1 / (σ√(2π))) * e^(-(x - μ)² / (2σ²)) ``` 其中: * μ 是分布的均值 * σ 是分布的标准差 * π 是圆周率 高斯分布具有对称的钟形曲线

MATLAB高通滤波案例:语音降噪,体验滤波在语音降噪中的卓越

![MATLAB高通滤波案例:语音降噪,体验滤波在语音降噪中的卓越](https://img-blog.csdnimg.cn/direct/97eec48b5c4a4ff3a3dcdf237706a1f7.png) # 1. 语音降噪概述** 语音降噪旨在消除或减弱语音信号中的噪声,以提高语音清晰度和可懂度。在现实环境中,语音信号经常受到各种噪声的污染,例如背景噪音、风噪和电子噪声。语音降噪技术通过滤波、谱减法和盲源分离等方法,可以有效地从语音信号中去除噪声,从而提升语音质量。 高通滤波是语音降噪中常用的技术之一。高通滤波器允许高频分量通过,而衰减低频分量。由于噪声通常具有较低的频率,因此

MATLAB图像去噪数据结构选择指南:影响性能和效率的关键因素,做出最佳选择

![MATLAB图像去噪数据结构选择指南:影响性能和效率的关键因素,做出最佳选择](https://img-blog.csdnimg.cn/20191029163305400.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjM0OTg1NQ==,size_16,color_FFFFFF,t_70) # 1. MATLAB图像去噪概述 MATLAB是一种用于数值计算和数据分析的高级编程语言。它提供了广泛的图像处理

正态分布函数在MATLAB中的机器学习应用:分类与回归,赋能机器学习模型,预测未来趋势

![正态分布函数在MATLAB中的机器学习应用:分类与回归,赋能机器学习模型,预测未来趋势](https://img-blog.csdnimg.cn/img_convert/0f9834cf83c49f9f1caacd196dc0195e.png) # 1. 正态分布函数概述 正态分布函数,也称为高斯分布函数,是一种连续概率分布,其概率密度函数为钟形曲线。它在自然界和统计学中广泛存在,描述了大量随机变量的分布。 正态分布函数的参数为均值(μ)和标准差(σ)。均值表示分布的中心,而标准差表示分布的离散程度。正态分布函数具有以下特性: * 对称性:分布在均值两侧是对称的。 * 钟形曲线:概率

MATLAB进度条性能监控指南:实时跟踪,优化性能,提升用户满意度

![MATLAB进度条性能监控指南:实时跟踪,优化性能,提升用户满意度](https://img-blog.csdnimg.cn/direct/bbc475f2af594ade95f583e33d7a5dd3.png) # 1. MATLAB进度条概述 MATLAB进度条是一种图形化用户界面元素,用于在长时间运行的操作期间向用户提供视觉反馈。它显示一个进度条,该进度条随着操作的进行而填充,并可能包括其他信息,例如估计的完成时间或已完成的任务数。 进度条在MATLAB中非常有用,因为它可以帮助用户了解操作的进度,并防止他们因长时间等待而感到沮丧。它还可以帮助识别性能问题,例如缓慢的算法或资源

MATLAB数组排序与材料科学:排序在材料科学中的应用

![MATLAB数组排序与材料科学:排序在材料科学中的应用](https://img-blog.csdnimg.cn/2021032110220898.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM5MTgxODM5,size_16,color_FFFFFF,t_70) # 1. MATLAB数组排序基础 MATLAB数组排序是根据特定规则对数组元素进行重新排列的过程。它在材料科学中有着广泛的应用,例如晶体结构分析、材料成