java数据结构

Java中元素的大小比较

    equals-Object 类：默认比较两个对象地址是否相等
    Comparable接口： return > 0 标志当前对象 > 0

Return = 0 表示当前对象= 0

Return < 0 表示当前对象< 0

    Comparator:接口(更灵活)：对原来Student类无影响 可以实现无数种比较———策略模式

return =0  o1 =o2

Return > 0 o1 >o2;

Return < 0 o1 <o2

Java.lang.Comparable:一个类实现了这个接口，就说明该类具备了可比较的能力

Public int compareTo(Object o):当前对象和传入对象o比较（死板）

Java.lang.Comparator：比较器。Student类无需事先此接口，专门的比较Student的类大小关系实现此皆苦，这种类称为比较器

Public int compare(Object o1,Object o2):比较o1和o2的大小

AgeSec

AgeDesc
优先级队列&TopK

    PriorityQueue优先级队列(基于堆)：满足队列的三大操作：

入队offer：调用堆的add方法

出队poll：按照优先级出队，最高先出调用堆的extractMax()

查看队首元素peek：查看堆顶元素

操作系统的作业调度（JDK的PriorityQueue基于最小堆实现,需要调整为最大堆（原o1-o2改为o2-o1）2）

    TopK问题：取大构建小堆 取小构建大堆

时间复杂度 O（nlogk）

       空间复杂度 O（k）

两种解决思路：1.排序法Nlogn 2.优先级队列 nlogk 3.最优解 ：快排partition思想O（n）
Map和BST

二叉树：理论基础

二分搜索树——TreeMap(红黑树，二分搜索树)

哈希表——HashSet,HashMap

    Map和Set:

set存储不重复的线性表——若只是判断元素是否存在，或者过滤重复元素，使用Set集合

Map:存储的数据是一种映射关系：需要根据不重复的key对应value，需要使用Map集合

**，Map和Set是一种专门用来进行搜索的容器或者数据结构，其搜索德效率 与具体的实例化子类有关。****

尽量不要使用Map和Set集合进行遍历，对于这俩集合的遍历操作是效率比较低的操作。使用Set和Map集合的核心操作在于搜索

    Map集合的常用操作：

    Map集合内部的元素之间的先后顺序与插入顺序关系不大（put(key,value）
    根据Key 取得value: get(key) getOrDefault（key,dafaultValue）
    Map集合中删除元素 ：remove(key)
    Map集合的遍历：（不到万不得已，不要使用）：collection 接口及其子类可以很方便的使用for_each循环进行遍历，但是Map和Collection几个没有任何关系：keySet(); values();entrySet()【Set<map.Entry<K,V>> entrySet()】
    Map集合的搜索 contains方法在Map中是非常高效的

（HashMap中接近O(1)）TreeMap中接近O（logN）

    Set集合的使用，等同于List,都是Collection的子接口 最常用Set集合的场景，（元素去重）

***Map 存映射 Set存不重复元素，用于去重***

    二分搜索树（BST）

    核心操作在于查找 3 {1.是个二叉树；2,。所有节点值满足：根节点 }左子树的所有节点，根节点<右子树的所有节点，此处不考虑等于的情况（JDK中的BST没有重复元素3；存储的元素必须具备可比较性，Comparable或者传入Comparator）
    规律：{1,；中序遍历得到的结果就是一个升序集合 2.源于最小最大值 最小值：第一个node.left==null 最大值：第一个node.right == null；3.在BST中插入一个新元素,这个元素一定是叶子结点位置插入！}）