12.12_黑马数据结构与算法笔记Java
目录
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方法的含义就是在
----------啊啊啊这里不懂
?
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
093?阻塞队列 双锁实现 3
094?阻塞队列 双锁实现 4
095?阻塞队列 双锁实现 5
096 堆 heapify 1
097 堆 heapify 2zhzh
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！