数据结构 + 算法-todo

作者: 一只狗被牵着走 | 来源:发表于2020-09-06 18:06 被阅读0次

0、总纲-数据结构分布图

# 1、基本的数据结构知识树
[图片上传失败...(image-14e376-1599732804125)]

# 2、10种最常见的数据结构
数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie树

## 2.0、数据结构分类
| 逻辑结构 | 线性结构 | 非线性结构 |
| :---: | :---: | :---: |
| | 顺序表（比如数组便实现了逻辑上的顺序表）、栈、队列等 | 树、图、堆 |
| 物理结构 | 顺序储存结构 | 链式储存结构 |
| | 数组 | 链表 |

## 2.1、数组

### 2.1.1、数组的逻辑结构
[图片上传失败...(image-d149f1-1599732804125)]

### 2.1.2、数组在内存中的存储形式
[图片上传失败...(image-e72c88-1599732804125)]

### 2.1.3、基本数据类型在java内存中的存储方式
[图片上传失败...(image-137ba4-1599732804125)] 这里需要关注一个点，int类型的基本数据类型，作为局部变量时是直接存储在栈帧中的 局部变量表 中的；但是作为成员变量，是引用储存在 方法区 中，值“1”是储存在堆中，引用指向这个“1”的地址；作为int[]数组如图。
> 这个点参考 java中，成员变量 int a = 1, a存在哪, 1存在哪 (存在JVM哪)?
> “成员变量的引用储存在方法区”这个概念适用于特定的JVM模型，见Java方法区、堆、栈、本地方法区及新生代、老年代、元空间整合，在“经典的JVM内存布局”中应该在Metaspace（元数据区）中的klass（类元信息）区中（见《码出高效Java开发手册》-P128中对“元数据区”的描述，里面提到“......其他内容包括类元信息、 字段 、静态属性、方法、常量等都移至源空间内”）
> 按照另一种说法，“方法区又称为永久代”--见Java字符串在内存中的存储位置

    [图片上传失败...(image-7083c1-1599732804125)]

### 2.2.4、字符串数组在java内存中的存储方式
> String arr = "aa" 和 String arr = new String("aa") 的区分参见 Java String —— 字符串常量池

    [图片上传失败...(image-99a6d5-1599732804125)]<br />

    > 这里涉及到一个点，字符串常量池是否存在，存在的话在堆中的哪个区（新生代、老年代）？
    > 应该是用到的模型不一样，原始的模型，字符串常量池的存在是在堆中的Perm区（即永久代，JDK8及以后Perm区被“淘汰”，Perm区中的字符串常量移至堆内存（不知道是在Yong区还是在Old区） -- 见《码出高效Java开发手册》-P128
    > 字符串常量池应该既不在新生代，也不在老年代（需要判断是否参与GC回收，这点不确定-todo）--见[字符串常量池和运行时常量池是在堆还是在方法区？](https://www.cnblogs.com/cosmos-wong/p/12925299.html)

    [图片上传失败...(image-9458be-1599732804125)]

### 2.2.5、对象数组在java内存中的存储方式
[图片上传失败...(image-76a710-1599732804125)]

### 2.2.6、二维数组在java内存中的存储方式
参考上述#2.2.1、#2.2.2、#2.2.3，下图以元素为基本数据类型为例 [图片上传失败...(image-538485-1599732804125)]

### 2.2.7、Java中的ArrayList
ArrayList底层是数组，它在内存中的存储可以参考对象 -> 数组的存储形式 [图片上传失败...(image-4075f4-1599732804125)]
> 在数组和 ArrayList 中做选择时，是否选用ArrayList的标准有两个：
> 1、是否会用到ArrayList的大部分方法
> 2、是否数组不能满足需要

#### 2.2.7.1、（相对比数组）ArrayList的优点

    - 将很多数组的操作细节封装起来了，一些操作都是性能比较高的写法
    - 支持动态扩容（数组的扩容需要手动敲代码实现 新建大容量数组 -> 复制数组元素）

#### 2.2.7.2、（相对比数组）ArrayList的缺点

    - ArrayList不支持存放基本数据类型
    - AarrayList的方法实现（相对比数组）没有那么清晰，从代码易读性方面有一定的理解成本

### 2.2.8、数组的应用场景

    - 应用于性能要求比较高的开发场景，比如底层框架开发，需要将性能压榨到极致
    - 对于内存使用要求没那么苛刻，因为数组需要一段连续的内存空间，即使内存总容量大于数组要求的总容量，但是没有足够多的连续空间，数组也不能生存

## 2.2、链表

### 2.2.1、链表的逻辑结构
[图片上传失败...(image-8bde3f-1599732804125)] [图片上传失败...(image-d1acde-1599732804125)]

### 2.2.2、单向链表在内存中的存储形式
> 对于链表的同一个节点，节点和值是一块分配的，内存地址是连续的；不同节点之间可能是连续的，也可能是跳跃的。
> java中的实现是 LinkedList（貌似除了LinkedList，没有其他的集合/java类底层使用了链表，LinkedHashMap底层除了散列表还用多维护了一个双向链表用于排序）

    [图片上传失败...(image-328be2-1599732804125)]

### 2.2.3、双向链表在内存中的存储形式
参考 #2.2.1 和 #2.2.2 
 [图片上传失败...(image-5ce2b1-1599732804125)]

### 2.2.4、链表vs数组的性能比较（时间复杂度）
> 数组适用于：读多写少场景
> 链表使用与：频繁地插入、删除元素场景

    |  | 查找 | 更新 | 插入 | 删除 |
    | :---: | :---: | :---: | :---: | :---: |
    | 数组 | O(1) | O(1) | O(n) | O(n) |
    | 链表 | O(n) | O(1) | O(1) | O(1) |

## 2.3、栈（stack）

### 2.3.1、栈的逻辑结构
> 参考单向链表

    [图片上传失败...(image-efef83-1599732804125)]

### 2.3.2、栈在内存中的存储形式
参考#2.2.2

### 2.3.3、栈的应用场景
面包屑导航 [图片上传失败...(image-9f19b0-1599732804125)]
> 栈的出栈和入栈顺序相反，便于“回溯”历史

## 2.4、队列

### 2.4.1、队列的逻辑结构
[图片上传失败...(image-1fa00-1599732804125)]

### 2.4.2、队列在内存中的存储形式
参考#2.2.2

### 2.4.3、队列的应用场景

    - 多线程中，争夺 `公平锁` 的等待队列

    [图片上传失败...(image-3d0d9d-1599732804125)]

    - 网络爬虫实现网站抓取时，先将待爬取的URL放入队列，再依照先后顺序来抓取和解析

    [图片上传失败...(image-9c2b2d-1599732804125)]

    - #2.7.2 二叉堆是实现堆排序及 **优先队列**   的基础
    >  优先队列：优先队列不再遵循“先入先出”的原则，分两种情况
    >    - 最大优先队列，无论入队顺序如何，都是当前最大的元素先出队
    >    - 最小优先队列，无论入队顺序如何，都是当前最小的元素先出队

## 2.5、散列表
> HashMap的底层实现的是散列表（JDK1.8之后还有散列表转数组+红黑树的延伸）

### 2.5.1、散列表的逻辑结构
[图片上传失败...(image-619a25-1599732804125)]
> 图中的“hashCode就是对象在JVM中的内存地址”一说法不对，hashCode确实是对象的唯一身份标识，但不是内存地址，获取对象的hashCode使用的是navie方法（不是java代码实现的）
> 对key的hashCode进行hash运算,求hash值的方式（HashMap源码）：

    ```java
    (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)
    ```
    > 根据hash值求数组下标（HashMap源码-630行）：
    > 为什么要进行这一步操作，直接使用hash值作为数组下标不好吗？-- hash值的范围大概为40亿，内存放不下，所以要对hash值进行（取模 或 与运算+位移）运算来对这些Entry分组，可以理解成一个hash槽是一组元素

    ```java
    i = (n - 1) & hash
    ```
    > 还有一种比较简单的方法（对hashCode进行取模），根据key的hashCode求数组下标（《漫画算法》-P55）：

    ```java
    index = HashCode(key) % Array.length;
    ```
    > 本节（#2.5.1）参考：
    > - HashMap源码（JDK1.6）
    > - 《漫画算法》-P54前后
    > - 《码出高效》-P206
    > - [HashMap中Entry以及Hash值的理解](https://blog.csdn.net/linton1/article/details/90084524)
    > - [总结HashMap实现原理分析](https://blog.csdn.net/hefenglian/article/details/79763634)
    > - [JAVA 两个对象不同为什么他们的hashcode有可能相同](https://blog.csdn.net/n13151125/article/details/83623296) 
    > - [HashMap如何计算数组下标](https://blog.csdn.net/duihsa156165/article/details/106860412/) 
    > - [Java 对象的内存地址是否就是hash code?](https://blog.csdn.net/Freeman19960215/article/details/104429334)

### 2.5.2、hash碰撞的原因
key的hash值返回的是int类型，int类型的值最多有2^32个--是有限的，所以一定存在相同的hash值 2.5.3、规避hash碰撞的方式 当hash值相等时，通过equals判等，判断key是否一致。因为equals()方法和hashCode()方法是有语义关联的，需要满足： A.equals(B) == true --> A.hashCode == B.hashCode
> 正是因为这个关系，所以重写equals方法的同时一定要重写hashCode,因为对象原hashCode还是根据对象自身的内存地址计算的，同一个Class new出来的对象的hashCode自然不会一样，所以equals自然也不会相等
> 这里参见：为什么重写equals一定要重写hashcode？

    又知，不同对象的hashCode就是各自在JVM中的内存地址，所以一定是唯一的（如果采用的计算hashCode的算法不一致，可能出现一样的hashCode，出现了hashCode一样的情况会怎么样这里就不清楚了-  ）

### 2.5.3、散列表在内存中的存储形式
参照#2.1.2和#2.2.2

### 2.5.4、散列表（HashMap）的优缺点
> 这里列的可能并不全，就酱紫吧。。

#### 2.5.4.1、散列表（HashMap）的优点

    - 作为KV对形式的数据结构，HashMap 的优势就是查找和操作的时间复杂度都是O (1)

#### 2.5.4.2、散列表（HashMap）的缺点

    - 依赖hash算法，有一定的时间成本，并且存储的key需要重写hashCode方法（String默认重写了hashCode方法）
    - 扩容对性能的损耗（参考数组的扩容）
    - 是线程不安全的（为什么是线程不安全的？见#2.5.7.1）

### 2.5.5、散列表（HashMap）的应用场景
参考HashMap的应用场景

### 2.5.6、附：Java中几种数据结构的优缺点对比
| | 遍历速度 | 插入删除速度 | 随机访问速度 | 备注 |
| --- | --- | --- | --- | --- |
| Set | 快 | 快 | 慢 | 比list多占一个指针的存储空间 |
| List | 快 | 慢 | 快 | 必须之前知道数组元素个数，因为申请内存是连续长度明确的 |
| HashMap | 慢 | 快 | 快 | 适合海量数据，o(1)的随机访问速度，不是可遍历 |
| 变体Set | 快 | 快 | 快 | set的基础上多占一个List的控件，不过各种性能都好 |
| 变体List | 快 | 插入快不能删除 | 快 | 各种性能都好就是不能有删除操作 |

    > 本节（#2.5.5参考[Set、List、HashMap优缺点比较，高性能集合](https://www.cnblogs.com/541g/p/10014289.html)）

### 2.5.7、HashMap的几个常见问题

#### 2.5.7.1、HashMap为什么是线程不安全的

    - put的时候，多线程造成数据不一致（这个好理解）
    - 多线程情况下，HashMap的扩容操作可能因为resize导致 死循环/死链（有点绕，还是没太理得过来-  ）

    [图片上传失败...(image-77cf59-1599732804125)]

#### 2.5.7.2、什么情况下发生resize（扩容）操作？
java this.threshold = tableSizeFor(initialCapacity) ... if (++size > threshold) resize();
当实际总元素个数（HashMap.size）大于阈值（桶元素容量 * 加载因子，即threshold = loadFactor * capacity，没扩容前capacity就是初始容量 threshold ）时扩容
> 参考：
> - 源码
> - HashMap的扩容机制---resize()中的#3
> - HashMap默认容量为何为16？中的 #扩容部分

#### 2.5.7.2、HashMap的加载因子是干什么的?加载因子为什么是0.75?
负载因子是用以权衡资源利用率和分配空间的系数（可以理解为一个加权系数） 提高空间利用率和减少查询成本的折中，主要是泊松分布的话，0.75的概率最小

    > 参考：
    >    - 《码出高效Java开发手册》-P206~P212
    >    - [HashMap默认加载因子为什么选择0.75？(阿里)](https://www.cnblogs.com/aspirant/p/11470928.html)

#### 2.5.7.3、HashMap的初始容量为什么是16？
为了降低hash碰撞的几率(（参见为什么HashMap的初始容量是16文末）
> “初始容量”指的是桶元素的多少 -- 即数组的大小
> HashMap中设置默认大小的语句是（而不是直接给出 16，是照顾到可读性，实际上 16不涉及运算，自然是 16的效率更高），源码：

    ```java

/**

The default initial capacity - MUST be a power of two.
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
```
> 这里可以回忆有16把椅子坐12个人的例子，即12个人的会议，安排16把椅子，产生同一把椅子坐两个人（hash碰撞）的概率要小很多；而不是一个极大数（是16）的原因是考虑空间占用
> 选用16（即24）正好是2的整数次幂，不选用23（貌似）是考虑扩容概率/还是hash的均匀分布？（记得看到过这个说法，但是忘了出处是哪里）
> 参考：
> - 《码出高效Java开发手册》-P206~P212

#### 2.5.7.4、为什么HashMap的扩容是2的幂次方？
同理初始容量为16（即2`4），数组的总容量是2的整数次幂，能够保证不同key算出的hash值相同的概率更小，让hash分布更均匀，为后续的其他操作（查找、插入、删除等）降低时间复杂度
> 参考：
> - 为什么hashMap的容量扩容时一定是2的幂次

## 2.6、二叉树
> 推荐一个学习树结构的网站 https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

### 2.6.1、树
树（tree）是n（n≥0）个节点的有限集。当n=0时，称为空树。在任意非空树中，有如下特点：

    - 有且仅有一个特定的称为根的节点
    - 当n>1时，其余节点可分为m（m>0）个互不相交的有限集，每一个集合本身又是一个树，称为根的子树

    [图片上传失败...(image-1c05de-1599732804125)]<br />

### 2.6.2、二叉树
每个节点最多有两个孩子节点的树

#### 2.6.2.1、几种二叉树的逻辑结构
[图片上传失败...(image-ea65b7-1599732804125)]

    - 二叉树节点的两个孩子节点，一个被称为左孩子（left child）,一个被称为右孩子（right child），这两个孩子节点的顺序是固定的，就像人的左手就是左手，右手就是右手，不能颠倒顺序或混淆
    - “满二叉树”--二叉树的一种特殊形式：一个二叉树的所有非叶子节点都存在左右孩子，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树

    [图片上传失败...(image-e9ecf-1599732804125)]

    - “完全二叉树”--二叉树的另一种特殊形式：对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号从1到n。如果这个树所有节点和同样深度的满二叉树的编号为从1到n的节点位置相同，则这个二叉树为完全二叉树

    [图片上传失败...(image-cb6828-1599732804125)]<br />

#### 2.6.2.2、二叉树的两种物理结构

##### 2.6.2.2.1、链式储存结构
[图片上传失败...(image-845766-1599732804125)]

##### 2.6.2.2.2、数组
[图片上传失败...(image-55279c-1599732804125)]

### 2.6.3、二叉树的应用场景
二叉树包含许多特殊的形式，每一种形式都有自己的作用（比如上面提的满二叉树、完全二叉树），但是最主要的应用还是进行查找操作和维持相对顺序这两个方面。

####

#### 2.6.3.1、进行查找操作（使用二叉查找树-binary search treee）
二叉查找树在二叉树的基础上增加了以下几个条件：

    - 如果左子树不为空，则左子树上所有的节点的值均小于根节点的值
    - 如果右子树不为空，则右子树上所有的节点的值均大于根节点的值
    - 左、右子树也都是二叉查找树
    > 这样的话，在二叉查找树构建的时候，对树内各节点已经进行了排序、分组，保证了二叉树的有序性，查找的时候自然会省事很多

    [图片上传失败...(image-828f1-1599732804125)]
    > 以下，关于二叉查找树的查找方式、构建方式等参考[[经验] 二叉查找树（GIF动图讲解）](https://bbs.elecfans.com/jishu_1152233_1_2.html)

#### 2.6.3.1.1、二叉查找树（BST）的查找方式（动图）
在二叉查找树b中查找x的过程： a、若b是空树，则搜索失败，否则 b、若x等于b的根节点的数据域之值，则查找成功；否则 c、若x小于b的根节点的数据域之值，则搜索左子树；否则 d、查找右子树 [图片上传失败...(image-ddf88b-1599732804125)]

##### 2.6.3.1.2、从有序数组构造一个二叉查找树（BST）的方式（动图）
[图片上传失败...(image-3f1b1-1599732804125)

##### 2.6.3.1.3、往BST（二叉查找树）中插入元素的方式
向一个二叉搜索树b中插入一个节点s的算法，过程为： a、若b是空树，则将s所指节点作为根节点插入，否则 b、若s->data等于b的根节点的数据域之值，则返回，否则 c、若s->data小于b的根节点的数据域之值，则把s所指的节点插入到左子树中，否则 d、把s所指节点插入到右子树中（新插入的节点总是叶子节点）
> 分析二叉查找树的定义，发现：不会存在“插入了一个节点导致原树结构发生重排”的情况

    [图片上传失败...(image-d2262e-1599732804125)]

##### 2.6.3.1.4、BST转成有序数组
[图片上传失败...(image-222ad1-1599732804125)]

#### 2.6.3.2、维持相对顺序（使用二叉排序树-binary sort tree）
> 晕。。二叉排序树其实就是二叉查找树，只是应用的场景不一样，根据功能不同，又起了个名字

    具体实现参见#2.6.3.1.2 和 #2.6.3.1.3<br />

### 2.6.4、二叉树的遍历方式（4种）
> 关注二叉树的遍历方式是因为
> 对于传统的线性结构进行遍历的操作是线性操作，比较简单；相对比线性结构的遍历，二叉树是非线性结构，对其遍历之前需要将非线性关联的各节点转化成一个线性的序列，之后对这个线性序列进行遍历--这就造成，遍历的方式不一样，遍历出的序列顺序也不同。所以，我们需要分析不同的遍历方式，根据实际需要选择遍历方式

    [图片上传失败...(image-2891a5-1599732804125)]
    > 本节（#2.6.4）参考：
    > - 《漫画算法》-P71~P87
    > - [【图解数据结构】一组动画彻底理解二叉树三种遍历](https://www.jianshu.com/p/45d75aeb3b01) 
    > - [二叉树三种遍历（动态图+代码深入理解）](https://blog.csdn.net/weixin_45525272/article/details/105837185)

#### 2.6.4.1、深度优先遍历（3种）
> 特点是纵向的“一头扎到底”

    - **三种深度优先遍历的代码实现 ** 
    ```java

/**

使用LinkedList递归构建二叉树
@param inputList 输入序列

@return TreeNode 头结点
*/
public static TreeNode createBinaryTree(LinkedList<Integer> inputList) {
TreeNode node = null;
if (inputList == null || inputList.isEmpty()) {
return null;
}

 /**
  * 移除链表头节点
  */
 Integer data = inputList.removeFirst();
 if (data != null) {
 node = new TreeNode(data);
 node.leftChild = createBinaryTree(inputList);
 node.rightChild = createBinaryTree(inputList);
 }
 return node;
 }

/**

递归进行二叉树的前序遍历
@param node 二叉树节点
*/
public static void preOrderTravel(TreeNode node) {
if (node == null) {
return;
}
System.out.println(node.data);
preOrderTravel(node.leftChild);
preOrderTravel(node.rightChild);
}

/**

使用栈的方式（栈具有回溯性，递归也具有回溯性）进行二叉树的（非递归）前序遍历
@param root 二叉树的根节点
*/
public static void preOrderTravelWithStack(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode treeNode = root;
while (treeNode != null || !stack.isEmpty()) {
// 迭代访问节点的左孩子，并入栈
while (treeNode != null) {
System.out.println(treeNode.data);
stack.push(treeNode);
treeNode = treeNode.leftChild;
}
// 如果节点没有左孩子，则弹出栈顶节点，访问节点右孩子
if (!stack.isEmpty()) {
treeNode = stack.pop();
treeNode = treeNode.rightChild;
}
}
}

/**

递归进行二叉树的中序排列
@param node 二叉树节点
*/
public static void inOrderTravel(TreeNode node) {
if (node == null) {
return;
}
inOrderTravel(node.leftChild);
System.out.println(node.data);
inOrderTravel(node.rightChild);
}

/**

递归进行二叉树的后序遍历
@param node 二叉树节点
*/
public static void postOrderTravel(TreeNode node) {
if (node == null) {
return;
}
postOrderTravel(node.leftChild);
postOrderTravel(node.rightChild);
System.out.println(node.data);
}

/**

二叉树的节点
*/
private static class TreeNode {
int data;
TreeNode leftChild;
TreeNode rightChild;

TreeNode(int data) {
this.data = data;
}
}

public static void main(String[] args) {
/**
* LinkedList底层使用的是双向链表，维护的是有序的数据集合。既支持FIFO，也支持FILO(看LinkedList源码，发现新加入的元素是放到链表尾的，删除的时候是删除表头元素，这样看应该是FIFO)
* 通过debug也证实了，元素按照3-2-9-10-8-4的顺序进入树的构建序列
*/
LinkedList<Integer> inputList = new LinkedList<Integer>(Arrays.asList(new Integer[]{3, 2, 9, null, null, 10,
null, null, 8, null, 4
}));
TreeNode treeNode = createBinaryTree(inputList);
```
 System.out.println("非递归实现-借用栈的回溯性-前序遍历");
 preOrderTravelWithStack(treeNode);

 System.out.println("递归实现-前序遍历");
 preOrderTravel(treeNode);

 System.out.println("递归实现-中序遍历");
 inOrderTravel(treeNode);

 System.out.println("递归实现-后序遍历");
 postOrderTravel(treeNode);
```
}


        - **代码运行结果 ** 

        [图片上传失败...(image-e1012f-1599732804125)]

        - **代码中的二叉树结构** 

        [图片上传失败...(image-ec1ad2-1599732804125)]<br />


<br />
        ##### 2.6.4.1.1、前序遍历
        根 -> 左子树 -> 左... -> 右子树 -> 右...<br />[图片上传失败...(image-d17149-1599732804125)]<br />[图片上传失败...(image-73a67e-1599732804125)]

<br />
        ##### 2.6.4.1.2、中序遍历
        左子树（左叶子节点） -> 根节点 -> 右子树 -> 根节点 -> 右子树 -> ...<br />[图片上传失败...(image-9e4534-1599732804125)]<br />[图片上传失败...(image-753ff-1599732804125)]

<br />
        ##### 2.6.4.1.3、后序遍历
        左子树（左叶子节点） -> 右子树 -> 根节点 -> 右子树 -> 根节点 -> ...<br />[图片上传失败...(image-cb10e0-1599732804125)]<br />[图片上传失败...(image-736d9-1599732804125)

<br />
        #### 2.6.4.2、广度优先遍历（1种）
        > 特点是横向的优先


<br />
        ##### 2.6.4.2.1、层序遍历
        二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点<br />[图片上传失败...(image-7eef0b-1599732804125)]

<br />
        ##### 2.6.4.2.2、层序遍历的代码实现
        ```java
/**
 * 递归实现-二叉树的层序遍历
 *
 * @param root 二叉树的根节点
 */
public static void levelOrderTravelsal(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        // 插入节点到队列
        queue.offer(root);
        while (!queue.isEmpty()) {
        // Retrieves and removes the head of this queue
        TreeNode node = queue.poll();
        System.out.println(node.data);
        if (node.leftChild != null) {
        queue.offer(node.leftChild);
        }
        if (node.rightChild != null) {
        queue.offer(node.rightChild);
        }
        }
        }
        ```

<br />
        ##### 2.6.4.2.3、代码执行结果
        [图片上传失败...(image-918bfb-1599732804125)]<br />


<br />
        ## 2.7、堆（heap）
        二叉堆本质是完全二叉树，通常可以被看作为一棵树的 **** 对象，常见的堆有二叉堆、斐波那契堆、Pairing堆。（有些书上--比如《漫画算法》P89--直接用“二叉堆”代替“堆”，不晓得二者有木有区别）堆满足以下两点性质：

        - 堆中某个节点的值总是不大于或不小于其父节点的值
        - 堆总是一棵完全二叉树
        > 这个网站除了树的学习之外，还可以模拟树的结构学习 [https://www.cs.usfca.edu/~galles/visualization/Algorithms.html](https://www.cs.usfca.edu/~galles/visualization/Algorithms.html)
        > 这一节参考：
        > - 度娘
        > - 《漫画算法》-P89
        > - [基本数据结构――堆的基本概念及其操作](https://www.cnblogs.com/JVxie/p/4859889.html)


<br />
        ### 2.7.1、二叉堆（这里暂且理解为 二叉堆是堆中的一个子分类）

<br />
        #### 2.7.1.1、二叉堆的逻辑结构和内存结构
        参见#2.6.2.1的 完全二叉树
        > 子节点和父节点的下标满足 2 * parentIndex + 1 = childIndex 或者 2 * parentIndex + 2 = childrenIndex

        [图片上传失败...(image-6b9bb1-1599732804125)]<br />


<br />
        #### 2.7.1.2、最大堆（或叫 大根堆）
        最大堆的任何一个父节点的值，都大于或等于它左、右孩子节点的值<br />


<br />
        #### 2.7.1.3、最小堆（或叫 小根堆）
        最小堆的任何一个父节点的值，都小于或等于它左、右孩子节点的值<br />


<br />
        #### 2.7.1.4、二叉堆的几种操作
        -- 粗粒度操作分类

        - 插入节点

        插入节点时，插入的位置是完全二叉树的最后一个位置。随后可能需要进行 上浮 操作进行调整
        > 插入节点的时间复杂度为 O(1) ~ O(logn)

        - 删除节点

        删除节点时，删除的是处于堆顶点的节点，同时将最后一个位置的节点补到原本堆顶的位置，再对那个节点进行 下沉 操作）
        > 删除节点的时间复杂度为 O(logn)

        - 构建二叉树

        这个概念貌似等同于“堆排序”，就是把一个无序的完全二叉树调整为二叉堆，本质就是让所有的非叶子节点依次 下沉（从最后一个非叶子节点开始）
        > 构建二叉树的时间复杂度为 O(1) ~ O(n)?（晕。。这个不等式不晓得咋并项了  ）


<br />-- 细粒度操作分类

        - 上浮 shift_up
        - 下沉 shift_down
        - 插入 push
        - 弹出 pop
        - 取顶 top
        - 堆排序 heap_sort




<br />
        #### 2.7.1.5、二叉堆的代码实现
        > 二叉堆的存储方式并不是链式存储，是顺序存储。换言之，二叉堆所有的节点都存储在数组中。

        ```java
/**
 * （对叶子节点进行）单节点“上浮”调整
 *
 * @param array 待调整的堆
 */
public static void upAdjust(int[] array) {
        int childIndex = array.length - 1;
        // 假定这个是左子节点，子节点和父节点的下标满足 2 * parentIndex + 1 = childIndex 或者 2 * parentIndex + 2 = childrenIndex
        int parentIndex = (childIndex - 1) / 2;
        // temp保存插入的叶子节点值，用于最后的赋值
        int temp = array[childIndex];
        while (childIndex > 0 && temp < array[parentIndex]) {
        // 无需真正交换，单向赋值即可--这里其实是父节点下沉
        array[childIndex] = array[parentIndex];
        // 指针上移，父节点变成子节点
        childIndex = parentIndex;
        // 指针上移，父节点的父节点变成父节点
        parentIndex = (parentIndex - 1) / 2;
        }
        // temp的上移操作完成，进行实际赋值
        array[childIndex] = temp;
        }

/**
 * （对指定节点进行）单节点“下沉”调整
 *
 * @param array       待调整的堆
 * @param parentIndex 要“下沉”的父节点
 * @param length      堆的有效大小
 */
public static void downAdjust(int[] array, int parentIndex, int length) {
        // temp保存父节点值，用于最后的赋值
        int temp = array[parentIndex];
        // 左子节点
        int childIndex = 2 * parentIndex + 1;
        while (childIndex < length) {
        // 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
        if (childIndex + 1 < length && array[childIndex + 1] < array[childIndex]) {
        childIndex++;
        }
        // 如果父节点小于任何一个孩子的值，则直接跳出
        if (temp <= array[childIndex]) {
        break;
        }
        // 无需真正交换，单向赋值即可
        array[parentIndex] = array[childIndex];
        // 指针下移，子节点变父节点
        parentIndex = childIndex;
        // 指针下移，子节点的子节点变子节点
        childIndex = 2 * childIndex + 1;
        }
        // 下沉操作完成，赋值
        array[parentIndex] = temp;
        }

/**
 * 构建最小堆
 *
 * @param array 待调整的堆
 */
public static void buildHeap(int[] array) {
        // 从最后一个非叶子节点开始，一次做“下沉”调整
        for (int i = (array.length - 2) / 2; i >= 0; i--) {
        downAdjust(array, i, array.length);
        }
        }

public static void main(String[] args) {
        // 这个数组只用一次叶子节点的上浮操作就能形成最小堆
        int[] array = new int[]{1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
        // 对叶子节点进行上移操作，得到最小堆
        upAdjust(array);
        System.out.println(Arrays.toString(array));

        array = new int[]{7, 1, 3, 10, 5, 2, 8, 9, 6};
        // 构建最小堆
        buildHeap(array);
        System.out.println(Arrays.toString(array));
        }
        ```

<br />
        #### 2.7.1.6、代码运行结果
        [图片上传失败...(image-8689d0-1599732804125)]

        - 第一个数组的节点上浮操作

        [图片上传失败...(image-ce02ea-1599732804125)]

<br />
        ### 2.7.2、二叉堆的应用-优先队列（以二叉堆作为实现基础的数据结构）

        - 二叉堆是实现堆排序及 **优先队列**   的基础
        >  优先队列：优先队列不再遵循“先入先出”的原则，分两种情况
        >    - 最大优先队列，无论入队顺序如何，都是当前最大的元素先出队
        >    - 最小优先队列，无论入队顺序如何，都是当前最小的元素先出队

        所以，最大优先队列可以使用最大堆实现，最小优先队列可以使用最小堆实现<br />


<br />
        #### 2.7.2.1、优先队列的代码实现
        ```java
public class PriorityQueue {
    private int[] array;

    // 等同于 int size = 0;
    private int size;

    public PriorityQueue() {
        // 队列初始长度为32
        array = new int[32];
    }

    /**
     * 入队，入队元素若更大则上浮
     * @param key 入队元素
     */
    public void enQueue(int key){
        // 队列长度超出范围，扩容
        if (size >= array.length){
            resize();
        }
        array[size++] = key;
        upAdjust();
    }

    /**
     * 出队
     * @return int
     * @throws Exception
     */
    public int deQueue() throws Exception{
        if (size <= 0){
            throw new Exception("the queue is empty!");
        }
        // 获取堆顶元素
        int head = array[0];
        // 让最后一个元素移动到堆顶
        array[0] = array[--size];
        downAdjust();
        return head;
    }

    /**
     * “上浮”调整
     */
    private void upAdjust(){
        int childIndex = size - 1;
        // 因为 -1/2=0(补码、移码相关)，所以childIndex==0时，parentIndex==0
        int parentIndex = (childIndex - 1) / 2;
        // temp保存插入的叶子节点值，用于最后的赋值
        int temp = array[childIndex];
        while (childIndex > 0 && temp > array[parentIndex]){
            // 无须真正交换，单向赋值即可
            array[childIndex] = array[parentIndex];
            childIndex = parentIndex;
            parentIndex = parentIndex / 2;
        }
        array[childIndex] = temp;
    }

    /**
     * “下沉”调整
     */
    private void downAdjust(){
        // temp保存父节点的值，用于最后的赋值
        int parentIndex = 0;
        int temp = array[parentIndex];
        int childIndex = 1;
        while (childIndex < size){
            // 如果有右孩子，且右孩子大于左孩子的值，则定位到右孩子
            if (childIndex + 1 < size && array[childIndex + 1] > array[childIndex]){
                childIndex++;
            }
            // 如果父节点大于任何一个孩子的值，直接跳出
            if (temp >= array[childIndex]){
                break;
            }
            // 无须真正交换，单向赋值即可
            array[parentIndex] = array[childIndex];
            parentIndex = childIndex;
            childIndex = 2 * childIndex + 1;
        }
        array[parentIndex] = temp;
    }

    /**
     * 队列扩容
     */
    private void resize(){
        // 队列容量翻倍
        int newSize = this.size * 2;
        this.array = Arrays.copyOf(this.array, newSize);
    }

    public static void main(String[] args) throws Exception {
        // 最大优先队列
        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.enQueue(3);
        priorityQueue.enQueue(5);
        priorityQueue.enQueue(10);
        priorityQueue.enQueue(2);
        priorityQueue.enQueue(7);
        System.out.println("原队列：" + JSON.toJSONString(priorityQueue.array) + "\n出队元素： " + priorityQueue.deQueue() +
                "\n新队列：" + JSON.toJSONString(priorityQueue.array));
        System.out.println("原队列：" + JSON.toJSONString(priorityQueue.array) + "\n出队元素： " + priorityQueue.deQueue() +
                "\n新队列：" + JSON.toJSONString(priorityQueue.array));
    }
}

#### 2.7.2.2、代码执行结果
[图片上传失败...(image-bdb22b-1599732804125)] 
 2.8、跳表 
 2.9、图 
 2.10、Trie树（单次查找树/前缀树/字典树）

# 3、10种最常见的算法
递归、排序、二分查找、搜索、哈希算法、贪心算法、分值算法、回溯算法、动态规划、字符串匹配算法

    > 参考视频：[https://time.geekbang.org/column/article/40036?gk_activity=0](https://time.geekbang.org/column/article/40036?gk_activity=0)
    > userName : 15072170772
    > pwd : alishuangji666

数据结构 + 算法-todo

0、总纲-数据结构分布图

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读