首页

# 其他集合

因为像 ArrayList，LinkedList 之类的容器比较简单，此处不会过多解释，只会列出一些需要注意的点。

ArrayList：

  • ArrayList 为了效率没有实现同步，有需求的情况下需要自己实现。
  • 向 ArrayList 中加入元素（add）时，都会进行容量检查，扩容都会交给 grow 方法。
  • remove 函数中，删除中间某一个元素会导致后面的元素向前移动，需要将最后一个位置赋为 null（为了让 GC 起作用）。
  • tirmToSize() ，将数组容量修改为当前元素个数大小； indexOf() 与 lastIndexOf()
    就是获取元素第一次 / 最后一次出现的 index。
  • modCount 是指集合创建以来修改的次数，他保证在迭代器循环中，如果出现集合的修改就停止迭代。

LinkedList：

  • LinkedList 可以考虑作为栈 / 队列，Java 官方不建议使用 Stack。但是 ArrayDeque 是栈或者队列的
    首选，性能更好。
  • LinkedList 没有哑节点，当链表为空的时候 first 和 last 都指向 null。

ArrayDeque：

  • Deque 是 "double ended queue", 表示双向的队列，英文读作 "deck".。

  • ArrayDeque 是非线程安全的，不允许加入 null。

# PriorityQueue

优先队列保证每次取出的元素都是队列中最小的（构造时可以传入比较器 Comparator ，所以想要每次取出都是最大的，只需要反过来即可）。

PriorityQueue 不允许放入 null 元素，内部通过数组实现小根堆，小根堆抽象上可以理解为完全二叉树。

数组映射完全二叉树的算数关系为：

  • leftNode = ParentNode*2 + 1
  • rightNode = ParentNode*2 + 2
  • ParentNode = (node - 1)/2

PriorityQueue 的 peek() 和 element 操作是常数时间， add() , offer() , 无参数的 remove() 以及 poll() 方法的时间复杂度都是 log (N)。

add() 和 remove() 失败后就会抛出异常，而 offer() 和 poll() 就是返回 false 。

# 小根堆解析

此处不讲解 PriorityQueue 源码，而是理解小根堆的维护流程

加入节点：队列只允许从队尾加入元素，大致流程如下图。

删除节点：

  • 优先队列出队操作会导致根节点被删除，此时需要将最后一个节点放到根节点的位置在进行下降调整。

  • 如果是其他关于小根堆的删除，当删除节点是尾节点时，直接删除即可。
  • 当节点在中间，我们就只看以该节点尾根节点的子树，将数组最后一个节点移到当前节点，再调整。

# 小根堆代码

// 模拟小根堆的增加
    public void add(int[] minHeap ,int size , int val) {
        // 假设参数合法，数组不出现越界
        if(size == 0) { minHeap[size++] = val;return;}
        // 当前父节点，index 是当前 val 位于的位置
        int p = (size - 1) >> 1,index = size;
        while(minHeap[p] > val) {
            minHeap[index] = minHeap[p];
            if(p == 0) break;
            index = p;
            p = (p-1) >> 1;
        }
        minHeap[p] = val;
    }
    public void remove(int[] minHeap , int size , int index) {
        if(size-1 == index) {minHeap[size] = -1;return;}// 假设 - 1 为 null
        /** 小根堆是完全二叉树，左节点下标为奇数，右节点为偶数
            一直向下找右节点直到到达最后一层，在倒数第二层会出现
            1） 该层不存在右孩子
            2） 该层存在右孩子
         */
        minHeap[index] = minHeap[--size];
        int l = (index << 1) + 1,r = l + 1;
        // 权值大的节点向下沉
        while(l < size && r < size) {
            if(minHeap[l] < minHeap[index]) {
                minHeap[index] = minHeap[l];
                index = l;
                l = (index << 1) + 1;r = l + 1; 
                continue;
            } else if (minHeap[r] < minHeap[index]) {
                minHeap[index] = minHeap[r];
                index = r;
                l = (index << 1) + 1;r = l + 1;
                continue;
            }
            // 如果当前节点小于左右子节点，则完成
            return;
        }
        
        if(l < size && minHeap[l] < minHeap[index]) {
            minHeap[index] = minHeap[l];
            minHeap[l] = -1;
        } 
    }
# 参考
http://www.cnblogs.com/CarpenterLee/p/5488070.html
https://pdai.tech/md/java/collection/java-collection-PriorityQueue.html