12.12_黑马数据结构与算法笔记Java

目录

079 优先级队列 无序数组实现

080 优先级队列 有序数组实现

081 优先级队列 堆实现 1

082 优先级队列 堆实现 2

083 优先级队列 堆实现 3

084 优先级队列 e01 合并多个有序链表1

084 优先级队列 e01 合并多个有序链表2

085 阻塞队列 问题提出

086 阻塞队列 单锁实现 1

087 阻塞队列 单锁实现 2

088 阻塞队列 单锁实现 3

089 阻塞队列 单锁实现 4

090?阻塞队列 单锁实现 5

091?阻塞队列 双锁实现 1

092?阻塞队列 双锁实现 2

093?阻塞队列 双锁实现 3

094?阻塞队列 双锁实现 4

095?阻塞队列 双锁实现 5

096 堆 heapify 1

097 堆 heapify 2

---

079 优先级队列 无序数组实现

普通队列和优先级队列

相同：一端进，另一端出

不同：

普通队列 遵循先进先出

优先级队列 优先级高的先出来，优先级低的后出来 5的优先级大于4的优先级

理解：

加入的时候，不用看优先级

M指针指向的是最高的优先级

i是遍历的指针

逐一将M指针和i指针所指向的级别进行比较，如果M大于i，则M指针不动，i继续遍历，如果M小于i，则M指针指向i指针所指向的元素，i继续遍历。

?--------------------------------------------------------------------------------------------------------------------------------

在remove那里

如果是最后一个元素，直接让size减减

如果不是最后一个元素，要进行移动

?--------------------------------------------------------------------------------------------------------------------------------

?

---------------------------------------------------------------------------------------------------------------------------------

在selectmax那里

array（size++），意思是赋值给索引，再加加，因此i＜size 是因为size指向的是最后元素的下一个位置，而这个位置是没有元素的

?--------------------------------------------------------------------------------------------------------------------------------

080 优先级队列 有序数组实现

--------------------------------------------------------------------------------------------------------------------------------

从最上面开始比较，一直和下一个元素进行比较，如果符合while条件，就把这个元素往出口移动一位，然后指针向出口反方向移动一次，直到不符合while条件，指针的上一个位置就是e该插入的位置

?--------------------------------------------------------------------------------------------------------------------------------

081 优先级队列 堆实现 1

完全二叉树的定义：除了最后一层，其他层数都是填满的，意思就是左分支和右分支都有元素。噢，最后一层如果也是填满的话，也算是二叉树。

而且，从左到右依次填满。

082 优先级队列 堆实现 2

?--------------------------------------------------------------------------------------------------------------------------------

用自己的话说一遍：要加入的元素从末尾最左边开始插入，先找到它的父节点，这里是3。要加入的元素与父节点进行比较，如果比父节点小，则直接插入左边位置，如果比父节点大，则要和父节点的父节点进行比较。这里的4大于3，所以要将3移动到向下移动到左边位置，再将4和3的父节点进行比较，发现4小于3的父节点，因此，4插入3的父节点?

?--------------------------------------------------------------------------------------------------------------------------------

移除顶部的步骤：

先将根部的节点直接下潜到最下面的左侧（7），然后与7进行交换，再将100进行删除。随后，将100与子节点中较大的子节点进行交换位置，一直下潜，保持父节点的值大于子节点的值，然后下潜到最下面?

?--------------------------------------------------------------------------------------------------------------------------------

083 优先级队列 堆实现 3

084 优先级队列 e01 合并多个有序链表1

?--------------------------------------------------------------------------------------------------------------------------------

用自己的话复述一遍：

从上往下的指针命名：p1，p2，p3

一开始指针们都指向第一个元素，p1指针指向的元素（1)被放入小顶堆，p2指针指向的元素（1）被放入小顶堆，p3(2)指针指向的元素3被放入小顶堆，然后开始比较这三个数字(1，1，2),1比较小，所以将第一个1放入空链表，随后将p1指针向后移动一位，并将p1指针现在所指向的元素（4）放入小顶堆，要按顺序放入噢，然后开始比较这三个数字（1，2，4），1比较小，所以将1放入空链表，并将p2指针向后移动一位，并将p2指针现在所指向的元素（3）放入小顶堆......

?--------------------------------------------------------------------------------------------------------------------------------

084 优先级队列 e01 合并多个有序链表2

逐行解释：

1 前面一步创建了小顶堆，调用小顶堆的方法（offer），offer的含义是在队尾插入一个元素。

这里的遍历是这样子的，首先要先理解，ListNode本身也是一种数组，因此of是一次性添加多个元素，因此head打印出来的是一个数组。而我们现在处理的这道题，本质上就是添加了三个数组

因此lists中应该是这样一个情况：

{

[1,4,5],

[1,3,4],

[2,6]

}? ?

然后现在遍历得到的h，是每一个数组，比如第一次遍历得到了数组[1,4,5],第二次遍历得到了数组[1,3,4]。然后他后面又说调用offer方法，offer方法的含义就是在

----------啊啊啊这里不懂

使用了一下魔法，我明白啦！

——————————————以上是12.12的想法，以下是12.13——————————————

1.

首先，先来解释一下，以下这张图，它之所以可以以数组的方式进行打印，是因为它在ListNode那里进行了重写toString的方法，使其以数组的方式进行返回。

"为什么可以在输出head的时候，程序可以将链表的值以数组的形式进行打印"

"我理解您的疑问了。在Java中，如果没有对ListNode类进行特殊处理，直接输出ListNode对象时，默认会调用ListNode类的toString()方法来获得对象的字符串表示形式。如果ListNode类没有重写toString()方法，那么会调用Object类的toString()方法。

如果ListNode类中重写了toString()方法，将链表的值以数组的形式进行打印，那么在输出head时就会看到链表的值以数组的形式进行打印。

如果您想要输出链表的结构，而不是以数组的形式进行打印，您可以在ListNode类中重写toString()方法，以便按照链表的结构进行打印。"

"那打印的时候，一定是使用toString方法吗"

"在Java中，当您使用System.out.println打印对象时，会调用对象的toString方法来获取对象的字符串表示形式。如果对象没有重写toString方法，那么会调用Object类的toString方法，返回的是对象的哈希码的字符串表示。

如果您希望自定义对象的打印方式，可以重写对象的toString方法，以便返回您希望的字符串表示形式。"

再来解释一下，这道例题

"ListNode是数组吗"

"不是，ListNode是链表的数据结构，不是数组。链表是一种数据结构，其中的元素按顺序排列，并且每个元素都包含一个指向下一个元素的指针。而数组是一种数据结构，其中的元素按索引排列，并且具有固定的大小。"

"for（ListNode h ： lists）{if（h ！= null）{heap.offer(h）}},为什么这里的h是头指针"

"在这段代码中，lists是一个数组，而ListNode是链表的数据结构。for循环遍历数组lists中的每个元素，将每个元素赋值给变量h。由于lists是一个数组，h会依次指向数组中的每个元素。

在这段代码中，假设lists数组中的每个元素都是一个链表的头指针，所以h在每次迭代时都指向一个链表的头指针。然后，通过if (h != null)条件判断，确保链表不为空，然后将每个链表的头指针h加入到堆（heap）中。"

"为什么lists数组中的每个元素是链表的头指针"

"在这种上下文中，通常假设lists数组中的每个元素都是一个链表的头指针，这是因为在合并多个链表的场景中，我们通常会将每个链表的头指针放入一个数组中，然后对这些链表进行合并操作。

当我们要合并多个链表时，我们需要访问每个链表的元素，这就需要通过链表的头指针来访问整个链表。因此，假设lists数组中的每个元素是链表的头指针是为了方便在代码中访问和操作每个链表。

当然，这只是一种常见的假设，并不是绝对的。在实际情况中，可能会有不同的数据结构和设计，但在上述代码中，假设lists数组中的每个元素是链表的头指针是为了方便处理多个链表的合并操作。"

"ListNode head = ListNode.of(1,2,3,4,5,6)，为什么这里输出的head是[1,2,3,4,5,6]，而不是头指针"

"实际上，根据您提供的代码，ListNode.of(1,2,3,4,5,6)?返回的应该是一个链表的头指针，而不是一个数组。所以，head应该是一个指向链表头部的指针，而不是一个数组。

如果在代码中输出的是[1,2,3,4,5,6]，那可能是因为在输出head的时候，程序将链表的值以数组的形式进行了打印。但实际上，head应该是一个指向链表头部的指针，而不是一个数组。"

"刚刚你说，如果ListNode类没有重写toString()方法，那么会调用Object类的toString()方法。那for（ListNode h ： lists）{if（h ！= null）{heap.offer(h）}},为什么这里的h是头指针？"

"在Java中，对于foreach循环中的对象，不管是数组还是实现了Iterable接口的类，都会调用其迭代器的next()方法来获取元素，而不是调用toString()方法。因此，对于您提到的代码for (ListNode h : lists) {...}中的h是链表的头指针，而不是调用toString()方法得到的字符串形式。"

因此得出结论：

打印数组，是因为输出语句那里调用了toString方法，以及重写了toString方法。

遍历得到是头指针，是因为foreach中，会调用其迭代器的next()方法来获取元素。

foreach底层逻辑是迭代器遍历，而不是toString。?

Java for、foreach 循环底层实现原理，以及如何判断集合支持 foreach 循环_foreach循环判断-CSDN博客

“输出语句的底层逻辑是什么”

在Java中，System.out.println是一个输出语句，用于将内容打印到控制台。其底层逻辑是通过调用System.out????????对象的println方法来实现的。

System.out是Java标准库中的一个PrintStream对象，它提供了多种重载的println方法，用于打印不同类型的数据。当您调用System.out.println时，实际上是调用了PrintStream对象的println方法。

PrintStream对象的println方法会将传入的参数转换为字符串，然后输出到控制台。如果参数是一个对象，会调用该对象的toString方法来获取字符串表示形式，然后输出到控制台。

因此，当您调用System.out.println打印对象时，会调用对象的toString方法来获取字符串表示形式，然后输出到控制台。

再来解释一个之前的疑惑

可以通过head指针指向第一个节点?

p是红色那个箭头，它通过什么进行移动的呢？ 怎么知道下一步应该移动到哪里呢？就是通过p.next知道的。next就是紫色箭头。 我通过这个紫色的箭头，从而得知p下一步应该移动到哪里。

?好的，看看我们的题目

同理，我这个t就是刚刚上面那个p的效果，这个t可以通过哨兵节点知道第一个要指向的是什么

t.next = min 就是让这个紫色的东西箭头指向min，也可以理解为将min这个值放入紫色箭头指向的红色框框里面取。如图。然后 t = min 就是指红色箭头变成蓝色箭头

（一开始s在红色箭头指向的框内）

补充其他比较简单的步骤?

2.?创建新链表的哨兵节点。?

4.当这个堆不为空的时候，不断移除最小元素。把堆里的最小元素移除，最小元素就是min。因为这是一个小顶堆，offer加入的时候，会将最小的元素放在头部，因此poll的时候会从头部取出元素，那就是取出最小的元素

3."ListNode s =new ListNode(-1,null);ListNode t = s。这里的t是指针还是元素"

"在这个情况下，t是一个指针。因为s是一个ListNode对象，而t是指向s的指针。所以t是一个指针，指向s这个ListNode对象。"

在这段代码中，ListNode是一个链表节点的类。假设ListNode类中有两个属性：val表示节点的值，next表示指向下一个节点的引用。

在代码中，首先创建了一个新的ListNode对象s，值为-1，下一个节点为null。然后将t指向s，这意味着t和s引用了同一个ListNode对象。

在while循环内部，从heap中取出一个节点min，然后将t.next指向min，这样就将t所指向的节点的下一个节点指向了min（类似于我刚刚说的将min放入框框）。接着将t指向min，这样下一次循环时，t.next就会指向下一个从heap中取出的节点。

因此，在循环结束后，t指向链表中的最后一个节点，t.next为null。整个过程中，t和t.next都是对象的引用，t指向链表中的某个节点，t.next指向t所指节点的下一个节点。

在这段代码中，t.next = min; 和 t = min; 这两个语句是有不同的作用的。

当执行 t.next = min; 时，表示将t节点的下一个节点指向min节点。这样就在链表中建立了t到min的连接关系。

而执行 t = min; 时，表示将t指向min节点，也就是说t节点的指针指向了min节点，但是此时t节点的下一个节点仍然是原来的节点。这样就改变了t节点的指向，但是并没有改变链表结构。

因此，这两个语句的作用是不同的。在这段代码中，t.next = min; 是用来构建链表的，而 t = min; 是用来移动指针的。

?

?

再看看之前一些问题

remove.next 是紫色那个箭头，实际上就是说明4，因为这是引用。

那我现在要将这个箭头所指向的4交给谁？交给3去引用。

085 阻塞队列 问题提出

就是有可能线程一还没有执行完所有操作，线程二就进来执行了，这样就会很复杂。因此要用锁去解决这些问题。?

086 阻塞队列 单锁实现 1

?--------------------------------------------------------------------------------------------------------------------------------

要把可能会出现异常的代码写在try里面，然后将解锁卸载finally里面，保证即便这些代码出现异常，也会自动解锁。

这个lock.lock方法，必须得等线程一全部完毕，才可以将进入阻塞队列的线程二唤醒，不可以提前唤醒。

?--------------------------------------------------------------------------------------------------------------------------------

如果想提前唤醒，要使用以下方法。

?-------------------------------------------------------------------------------------------------------------------------------?

087 阻塞队列 单锁实现 2

细节：虽然是唤醒了，但是也要等锁解开了才可以继续执行下面的代码。?

088 阻塞队列 单锁实现 3

但是还有bug，以下

--------------------------------------------------------------------------------------------------------------------------------?

一般await都要配合while来使用?

--------------------------------------------------------------------------------------------------------------------------------

基本配置，以上?

?--------------------------------------------------------------------------------------------------------------------------------

089 阻塞队列 单锁实现 4

--------------------------------------------------------------------------------------------------------------------------------?

A线程：判断是否满，如果满，则进入等待。如果以后不满了，则继续下面的运行。

headWaits配合poll方法使用，因为poll是从头部获取元素并删除。

B线程：等线程A执行完之后，就可以执行poll方法了。

这里的锁是interrupt锁，就是可以提前被唤醒，但是也不可以获得锁。测试代码要trycatch，而且有写这个锁的方法要throw异常。

?--------------------------------------------------------------------------------------------------------------------------------

tailWaits配合poll方法使用，因为offer是从尾部添加元素。

?--------------------------------------------------------------------------------------------------------------------------------

090?阻塞队列 单锁实现 5

?--------------------------------------------------------------------------------------------------------------------------------

在有限的时间内去等待。?

?--------------------------------------------------------------------------------------------------------------------------------

091?阻塞队列 双锁实现 1

设置两把锁，一把保护头指针，一把保护尾指针，两把锁互不影响。

092?阻塞队列 双锁实现 2

?--------------------------------------------------------------------------------------------------------------------------------

size虽然看上去是一个步骤，但是执行起来是有三个步骤的。而且两把锁是可以同时执行的，offer的加加和poll的减减一起发生这样的情况是会发生的，因此也有可能发生多线程并发的问题。?

?--------------------------------------------------------------------------------------------------------------------------------

getandIncrement内部可以保证原子性，避免多线程并发的事情发生。?

?--------------------------------------------------------------------------------------------------------------------------------

093?阻塞队列 双锁实现 3

在tail那里，要图一，在head那里，要图二。因为tailLock和tailWaits要一起使用。?因为headLock和headWaits要一起使用。?

094?阻塞队列 双锁实现 4

?--------------------------------------------------------------------------------------------------------------------------------

但是这样会导致一个问题，大家都在等对方的锁，从而有死锁的问题。?

?--------------------------------------------------------------------------------------------------------------------------------

?让这两把锁平级，就可以解决死锁问题。

?--------------------------------------------------------------------------------------------------------------------------------

095?阻塞队列 双锁实现 5

?--------------------------------------------------------------------------------------------------------------------------------

这里的getAndDecrement返回的值是减少前的值?

?--------------------------------------------------------------------------------------------------------------------------------

?

针对在offer中唤醒poll的理解：在offer这边，如果有offer1 offer2 offer3，那只要offer1去执行poll的加锁，唤醒，解锁就可以了，其余的offer2 offer3只要遵守自己的offer锁就可以了。那offer1只能唤醒poll1啊，那怎么可以唤醒poll2，poll3呢？那就由poll方法自己去唤醒，当我从offer这边唤醒了poll1之后，poll1执行完毕之后，就自动唤醒poll2，以此类推唤醒poll3.从而减少在offer方法上堆poll进行很多的加锁解锁的操作。

从offer这边推导过去poll，因为是offer，只能从0到非空。

?--------------------------------------------------------------------------------------------------------------------------------

096 堆 heapify 1

建堆：形成大顶堆

叶子节点：没有孩子的节点

非叶子节点：有孩子的节点

097 堆 heapify 2

h=总高度? ?2的h次方??i每一层高度