`
小篮子java的家
  • 浏览: 30755 次
  • 性别: Icon_minigender_2
社区版块
存档分类
最新评论

优先队列、treeset内部结构大比拼

阅读更多

 

首先要了解队列的存储结构里是数组,而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.pdf

    Java数据结构--13.Java8数据结构TreeSet 前⾔ ,上⼀篇中对 Set 接⼝最终实现类 HashSet 与 LinkedHashSet 做了介绍与分析,本篇将对另⼀种 Set 接⼝的最终实现类 TreeSet 进⾏ 介绍与分析。 先来看下 TreeSet 完整...

    TreeSet 红黑树结构算法

    文档摘录 文档摘录文档摘录文档摘录文档摘录文档摘录文档摘录

    TreeSet集合用法

    介绍TreeSet集合用法,向TreeSet集合中添加类的对象,此类需实现Comparable接口,有实例,供需要的朋友下载学习。

    java泛型 用了treeset

    使用TreeSet和Comparator,编写TreeSetTest2类,要求对TreeSet中的元素1-元素10进行排列,排序逻辑为奇数在前偶数在后,奇数按照升序排列,偶数按照降序排列。 如果需要的话可以下载,有写成文章的。有写了一点中文...

    java集合-TreeSet的使用

    TreeSet 是 Java 中的一个集合类,它实现了 SortedSet 接口,并且使用红黑树作为底层数据结构。TreeSet 具有以下主要特点: 排序性:TreeSet 中的元素是有序的,默认按照元素的自然顺序进行排序。或者,可以在创建 ...

    HashSet和TreeSet_围墙之外

    HashSet和TreeSet_围墙之外.rar

    java 集合框架(TreeSet练习)

    毕向东Java基础视频教程-集合框架(TreeSet练习).

    treemap treeset hashset hashmap 简要介绍

    treemap treeset hashset hashmap 简要介绍

    C#的6种常用集合类大比拼

    集合、数组和队列的对比。 1.数组是固定大小的,不能伸缩。虽然System.Array.Resize这个泛型方法可以重置数组大小,但是该方法是重新创建新设置大小的数组,用的是旧数组的元素初始化。随后以前的数组就废弃!而集合...

    用java的TreeSet写的一个求并集算法

    用JAVA集合TreeSet写的求并集算法

    Java SE程序 TreeSet类中自定义CompareTo类

    Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类Java SE程序 TreeSet类中自定义CompareTo类...

    TreeSet 不用自然排序自己做比较器

    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方式实现)

    通过TreeSet类直接对学生成绩实现了排序功能,不必要进行相关额外的排序来实现!

    数据结构与算法分析_Java语言描述(第2版)

    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 选取...

    day05-迭代器,数据结构,List,Set ,TreeSet集合,Collections工具类 - 副本.md

    这是为了方便大家了解集合类的相关知识所找的一个MarkDown文档,读者可以通过阅读了解各种子类集合的实现原理,红黑树的实现也会有所介绍.

    HashSet和TreeSet.doc

    HashSet和TreeSet的区别

    数据结构java版 梁志敏译

    数据结构java版 pdf ,书中有霍夫曼压缩、Dijkstra最小路径算法,平衡搜索树,八皇后问题,RSA加密算法、TreeSet、TreeMap、队列、优先队列、堆栈等算法

    尚硅谷-实验:TreeSet的自然排序与定制排序.pdf

    ·全程内容涵盖数据结构、设计模式、JVM内存结构等深度技术 ·企业级笔试面试题目深入源码级讲解,拒绝死记硬背 4.代码量更大、案例更丰富、更贴近实战: ·Java语言基础阶段:12720行代码,Java语言高级阶段:...

    数据结构与算法分析_Java语言描述(第2版)]

    堆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 ...

Global site tag (gtag.js) - Google Analytics