首先要了解队列的存储结构里是数组,而treeset的存储结构是链表
队列中逻辑结构是二叉堆(小顶堆),treeset中逻辑结构是排序二叉树
先解释一下什么是二叉堆和排序二叉树首先从树说起
树
它的每一个结点都可以有不止一个直接后继,除根结点外的所有结点都有且只有一个直接前驱。
二叉树
在树的基础上,所有结点的子结点个数小于或等于二
完全二叉树
首先在二叉树的基础上,除了最后一个节点所有节点都有左右两个子节点的二叉树
二叉堆(小顶堆)
* 是一个完全二叉树
* 最小的元素在顶端
* 每个元素都比它的父节点大,或者和父节点相等。
排序二叉树
(1) 是一个二叉树
(2)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(3)若右子树不空,则右子树上所有结点的值均大于它的根结点的值;
(4)左、右子树也分别为二叉排序树
优先队列的和treeset的内部结构展示
优先队列和treeset的思路实现
优先队列
* 添加元素 首先把要添加的元素加到数组的末尾,然后和它的父节点比较,如果新元素比父节点元素小则交换这两个元素,然后再和新位置的父节点比较,直到它的父节点不再比它大,结束。
* 删除元素 删除元素的过程和添加类似,只不过添加元素是“向上比较”,而删除元素是先“向下比较”:找到要删除元素的下标位置,把最后一个元素移到该位置,然后和它的两个子节点比较
1如果较小的子节点比它小就将它们交换,直到两个子节点都比它大。
2如果移到该位置时,它已经比子节点小则像添加元素那样“向上比较”,直到父结点比它大为止。
treeset
*添加元素 从根节点往下比较,小于往左走,大于往右走,依次循环。直到和其比较的结点为空。空结点的父结点,即为要加入元素的父节点。实例化成结点对象,再比较大小后,将结点挂在其父节点下。
<图略>
*删除元素 找到元素所在的节点位置
1--当结点node有左右子女时,往下所搜与node中的元素最为接近的元素的结点,找到后将该结点的元素值赋给node,让node指向该结点, 接下来删除这个结点。 注意:最后要去掉的节点的子女个数都是小于2的。
2---当结点node只有一个子女时,然后直接将子女链在其父结点后。
3----当结点node无子女时,使其为null,即删除
分享到:
相关推荐
Java数据结构--13.Java8数据结构TreeSet 前⾔ ,上⼀篇中对 Set 接⼝最终实现类 HashSet 与 LinkedHashSet 做了介绍与分析,本篇将对另⼀种 Set 接⼝的最终实现类 TreeSet 进⾏ 介绍与分析。 先来看下 TreeSet 完整...
文档摘录 文档摘录文档摘录文档摘录文档摘录文档摘录文档摘录
介绍TreeSet集合用法,向TreeSet集合中添加类的对象,此类需实现Comparable接口,有实例,供需要的朋友下载学习。
使用TreeSet和Comparator,编写TreeSetTest2类,要求对TreeSet中的元素1-元素10进行排列,排序逻辑为奇数在前偶数在后,奇数按照升序排列,偶数按照降序排列。 如果需要的话可以下载,有写成文章的。有写了一点中文...
TreeSet 是 Java 中的一个集合类,它实现了 SortedSet 接口,并且使用红黑树作为底层数据结构。TreeSet 具有以下主要特点: 排序性:TreeSet 中的元素是有序的,默认按照元素的自然顺序进行排序。或者,可以在创建 ...
HashSet和TreeSet_围墙之外.rar
毕向东Java基础视频教程-集合框架(TreeSet练习).
treemap treeset hashset hashmap 简要介绍
集合、数组和队列的对比。 1.数组是固定大小的,不能伸缩。虽然System.Array.Resize这个泛型方法可以重置数组大小,但是该方法是重新创建新设置大小的数组,用的是旧数组的元素初始化。随后以前的数组就废弃!而集合...
用JAVA集合TreeSet写的求并集算法
Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类...
public int compare(String o1,String o2) { return o1.length()-o2.length();... TreeSet ts = new TreeSet(com); ts.add("string"); ts.add("char"); ts.add("nothing�"); System.out.println(ts);
通过TreeSet类直接对学生成绩实现了排序功能,不必要进行相关额外的排序来实现!
6.9 标准库中的优先队列 小结 练习 参考文献 第7章 排序 7.1 预备知识 7.2 插入排序 7.2.1 算法 7.2.2 插入排序的分析 7.3 一些简单排序算法的下界 7.4 希尔排序 7.5 堆排序 7.6 归并排序 7.7 快速排序 7.7.1 选取...
这是为了方便大家了解集合类的相关知识所找的一个MarkDown文档,读者可以通过阅读了解各种子类集合的实现原理,红黑树的实现也会有所介绍.
HashSet和TreeSet的区别
数据结构java版 pdf ,书中有霍夫曼压缩、Dijkstra最小路径算法,平衡搜索树,八皇后问题,RSA加密算法、TreeSet、TreeMap、队列、优先队列、堆栈等算法
·全程内容涵盖数据结构、设计模式、JVM内存结构等深度技术 ·企业级笔试面试题目深入源码级讲解,拒绝死记硬背 4.代码量更大、案例更丰富、更贴近实战: ·Java语言基础阶段:12720行代码,Java语言高级阶段:...
堆6.6 左式堆6.6.1 左式堆性质6.6.2 左式堆操作6.7 斜堆6.8 二项队列6.8.1 二项队列结构6.8.2 二项队列操作6.8.3 二项队列的实现6.9 标准库中的优先队列小结练习参考文献第7章 排序7.1 预备知识7.2 插入排序7.2.1 ...