PriorityQueue 是线性结构吗?90% 的人都搞错了!

时间:2022-08-26 20:48:51

PriorityQueue 是线性结构吗?90% 的人都搞错了!

其实这个问题的完整描述是:Java 中的 PriorityQueue 实现,其数据的逻辑结构是线性结构吗?其数据的物理结构又是什么?

估计很多人的答案是:PriorityQueue 是线性结构,因为 PriorityQueue 是优先级队列的实现,队列不就是线性结构的吗?但在 PriorityQueue 的实现中,其数据的逻辑结构是树形结构,其物理结构是顺序存储结构。

要弄明白这个问题,我们必须先弄明白什么是数据的逻辑结构,什么是数据的物理结构。

顾名思义,数据的逻辑结构指的是数据是怎么组织起来的,数据的物理结构指的是数据是怎么存储的。 数据的逻辑结构与物理结构,是数据结构两个非常重要的要素。但你知道数据有几种逻辑结构、几种物理结构吗?

数据的逻辑结构

数据的逻辑结构指的是数据是如何组织起来的,反映数据元素之间的逻辑关系,它更加贴近于现实。 例如现实生活中树干与树叶就是树形结构,排队的队伍就是线性关系。

数据的逻辑结构一般有四种,分别是:线性结构、集合结构、树形结构、网络结构。 其中,我们把集合、树形结构、网络结构统称为非线性结构。

线性结构

线性结构指的是数据结构中的元素存在一对一的相互关系。 例如:数组是一种线性结构,其下标与元素一一对应。链表也是一种线性结构,其元素之间是一个接着一个的。生活中有很多类似的例子,例如排队买票的队伍就是一个线性结构。超市里排布整齐的商品,也是一个线性结构。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

逻辑结构之线性结构

集合结构

集合结构指的是元素之间除了「同属一个集合」的关系之外,再无其他关系。 例如数学中的整数就是一个集合,所有小数也是一个集合。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

逻辑结构之集合

树形结构

树形结构指的是元素存在一对多的关系。 例如水果有香蕉、草莓、西瓜等,这种逻辑结构就是树形结构。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

逻辑结构之线树形结构

网络结构

网络结构指的是元素存在多对多的关系。 网络结构也叫做网状结构,它是多对多的关系。比如城市的交通网络,每栋房子与其他房子都有许多条路。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

逻辑结构之线网络结构

数据的物理存储结构

数据的物理结构指的是数据是如何存储的,反映数据的存储结构。 数据的存储结构分为四种:顺序存储、链式存储、索引存储、散列存储。 一般我们将这四种物理结构分为顺序存储结构与非顺序存储结构。顺序存储是顺序存储结构,链式存储、索引存储、散列存储均属于非顺序存储结构。

数据的顺序存储结构的特点是:借助元素的相对位置来表示数据元素之间的逻辑关系。非顺序存储的特点是:借助指示元素存储地址的指针表示数据元素之间的逻辑关系。

注:有些朋友说数据的物理存储结构只有顺序存储、链式存储两种,索引存储和散列存储是不存在的。对此,后续我专门写篇文章来聊聊这个事情。

顺序存储

顺序存储指的是数据在内存当中是按照顺序存储的,逻辑结构上相邻的元素在物理结构上也是相邻的。Java 中的 ArrayList 就是通过顺序存储的方式实现的。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

物理结构之顺序存储

链式存储

链式存储指的是元素之间的逻辑顺序,并不是通过内存顺序来分配的,而是通过一个引用组织起来的。也就是说,逻辑上相邻的元素,在物理存储位置上是不相邻的。Java 中的 LinkedList 就是通过链式存储的方式实现的。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

物理结构之链式存储

索引存储

索引存储指的是元素之间的逻辑关系,是通过一张索引表来存储的。这张索引表有很多个索引项,每个索引项存储两个信息:关键字、数据存储地址。我们通过关键字可以找到对应的数据存储地址。这就像书籍的目录一样,关键字就是章节名,数据存储地址就是页码。我们通过章节名可以快速地找到对应的页码,从而快速地找到书籍对应内容。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

物理结构之索引存储

散列存储

散列存储也称之为哈希存储,其与索引存储非常类似,都是通过索引值以及对应的值来实现快速查找。唯一不同的区别是,索引存储会对索引值进行哈希。应该说散列存储是索引存储的一种更加复杂的实现。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

物理结构之散列存储

辨别思路

看到这里,我们对数据的逻辑结构、物理结构已经有了基本的认识,也知道它们的常见种类。那我们到底如何去判断它们是属于哪种逻辑结构、哪种物理结构呢?

拿 Java 中对于优先级队列的 PriorityQueue 实现为例。通过阅读源码我们得知其底层使用了二叉堆实现,而二叉堆本身其实就是一颗二叉树。即对于 PriorityQueue 来说,其数组最终是通过下图这种逻辑结构组织起来的,因此 PriorityQueue 的逻辑结构是树形结构。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

PriorityQueue 的逻辑结构

从 PriorityQueue 的源码,我们可以知道 PriorityQueue 的数据最终是通过一个对象数组存储的,而数组的物理结构是顺序存储的。因此对于 PriorityQueue 来说,其物理结构是顺序存储结构。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

PriorityQueue 的类成员变量

通过 PriorityQueue 这个例子,我们可以总结出判断数据的逻辑结构、物理结构的思路:判断逻辑结构,要看数据是如何组织起来的。要判断物理结构,则是要看数据最终是如何存储的。

如果对 PriorityQueue 的源码实现感兴趣,可以阅读:集合系列 Queue(九):PriorityQueue - 陈树义的博客

我们再用这个办法来判断一下 TreeMap 这个类。

TreeMap 是 Java 中非常经典的实现,其底层是基于红黑树的实现,即其最终会将所有数据组织成一颗红黑树,因此 TreeMap 的逻辑结构是树形结构。通过阅读 TreeMap 的源码,我们知道 TreeMap 的数据最终是通过 Entry 这个类存储的,因此 TreeMap 的物理结构是链式存储结构。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

TreeMap 的类成员变量

最后我们拿比较复杂的 LinkedBlockingQueue 来分析一下。

很多人会说队列就是一种特殊的数组,而数组是顺序存储的,因此队列就是顺序存储的。如果将这个结论套用在 LinkedBlockingQueue 上,那是否可以得出同样的结论,即 LinkedBlockingQueue 也是顺序存储的呢?

前面我们说过:不要用直觉去判断,而要根据定义去判断。 即判断数据的逻辑结构、物理结构的思路是:判断逻辑结构,要看数据是如何组织起来的。要判断物理结构,则是要看数据最终是如何存储的。

LinkedBlockingQueue 是 Java 中的阻塞队列实现,其最终会将数组组织成一个队列,因此其逻辑结构上属于线性表。通过阅读源码,我们可以知道 LinkedBlockingQueue 的元素是存储在 Node 节点上的,因此 LinkedBlockingQueue 的物理结构属于链式存储。

PriorityQueue 是线性结构吗?90% 的人都搞错了!

LinkedBlockingQueue 的类成员变量

总结

本文一开始通过 PriorityQueue 的例子,引入了逻辑结构与物理结构这个话题。接着介绍了四种逻辑结构:线性表、集合、树状结构、网络结构。

原文地址:https://mp.weixin.qq.com/s/makT8acCJYH_0rqWI5_hNQ