首页
登录 | 注册

数据结构之堆的插入、取值、排序(细致讲解+图片演示)

数据结构之堆(Heap):插入、取值、排序。

堆是一种数据结构,分为最小堆和最大堆,可以用二叉树来表示。

在二叉树的任意的一个三角结构中(一个父节点,两个子节点),需要满足以下两个条件:

1、父节点要是最小的,就是最小堆(或最大的,就是最大堆),两个子节点之间没有要求

2、数据插入的顺序是一层一层的,只有上一层存满,才会有下一层

 

下面我们以图片的形式演示最小堆的插入、取值、和排序操作,只要知道最小堆的原理,那么最大堆也就明白了。

 

假设我们有一个原始的最小堆如下:

 数据结构之堆的插入、取值、排序(细致讲解+图片演示)

 

插入操作:

当插入一个新值时,首先将值放到树的最后的位置,如下图所示。

然后将这个值与父元素比较,如果不满足规则1,则与父元素替换(如下图所示)。

 第一步数据结构之堆的插入、取值、排序(细致讲解+图片演示)

第二步数据结构之堆的插入、取值、排序(细致讲解+图片演示)

第三步数据结构之堆的插入、取值、排序(细致讲解+图片演示)

 

由图可知,在插入操作中,交换次数最大即为树的高度(log n

 

最小值操作:

在最小堆中,拿出一个最小值,当然就是拿出第一个数啦~不过拿完以后树不就没有“头”了?

不用担心,我们可以把最后一个数放到头的位置,这样树的结构就不会改变,而且操作简单(因为是最后一个数)。

当然,因为是最后一个数,必然会出现不满足条件1的情况,所以我们需要把新的树头与子元素比较替换,下面是图片演示:

假设我们有一个原始的最小堆如下所示,接下来我们要取最小值:

 数据结构之堆的插入、取值、排序(细致讲解+图片演示)
数据结构之堆的插入、取值、排序(细致讲解+图片演示)

不过交换完很可能是不满足条件1的,那么我们就需要比较替换,替换规则是和两个子元素中最小的一个替换

数据结构之堆的插入、取值、排序(细致讲解+图片演示)
数据结构之堆的插入、取值、排序(细致讲解+图片演示)

由图可知,在取值操作中,交换次数最大也为树的高度(log n

 

堆的排序:

我们知道了如何取最小值,那么堆的排序简单啦~只要依次取堆的最小值,那么当堆取完时,我们取出的数据不就是一个从小到大的序列嘛!


相关文章

  • 目录 引入 简单工厂 抽象工厂 Spring的bean工厂 模拟Spring工厂实现 模拟IOC 引入 假设有一个司机, 需要到某个城市, 于是我们给他一辆汽车 public class Demo { public static void ...
  • 一.前言 在日常开发中,我们经常会碰到需要在运行时才知道对象个数的情况,这种情况不能使用数组,因为数组是固定数量的,这个时候我们就会使用集合,因为集合可以存储数量不确定的对象. 集合类是特别有用的工具类,不仅可以存储数量不等的对象,还可以实 ...
  • MongoDB【快速入门】
    1.MongDB 简介 MongoDB(来自于英文单词"Humongous",中文含义为"庞大")是可以应用于各种规模的企业.各个行业以及各类应用程序的开源数据库.作为一个适用于敏捷开发的数据库,Mo ...
  • Linux的内存分页管理
    作者:Vamei 出处:http://www.cnblogs.com/vamei 严禁转载   内存是计算机的主存储器.内存为进程开辟出进程空间,让进程在其中保存数据.我将从内存的物理特性出发,深入到内存管理的细节,特别是了解虚拟内存和内存 ...
  • 对于初学者,或者没有接触过网络编程的程序员,会觉得网络编程涉及的知识很高深,很难,其实这是一种误解,当你的语法熟悉以后,其实基本的网络编程现在已经被实现的异常简单了. 网络通信作为互联网的技术支持,已被广泛应用在软件开发中,无论是Web,服 ...
  • Spring入门(二):自动化装配bean
    Spring从两个角度来实现自动化装配: 组件扫描(component scanning):Spring会自动发现应用上下文中需要创建的bean. 自动装配(autowiring):Spring会自动满足bean之间的依赖. 为了更形象的解 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.076 s.
京ICP备10005923号