基础数据结构

image.png

数据结构比较

image.png

堆

堆也称为优先队列（队列+排序规则）
堆是一种特殊的基于树的满足某些特性的数据结构，整个结构中，所有的父子节点的键值都会满足某种相同的排序规则。堆更准确地可以分为最大堆与最小堆，在最大堆中，父节点的键值永远大于或者等于子节点的值，并且整个堆中的最大值存储于根节点；而最小堆中，父节点的键值永远小于或者等于其子节点的键值，并且整个堆中的最小值存储于根节点。

时间复杂度:

  • 访问最大值 / 最小值: O(1)
  • 插入: O(log(n))
  • 移除最大值 / 最小值: O(log(n))

图一为最大堆，图二为最小堆；

image.png

JAVA 定时任务使用的任务队列 DelayedWorkQueue 基于堆的数据结构实现。see:

  1. static class DelayedWorkQueue extends AbstractQueue<Runnable>
  2.         implements BlockingQueue<Runnable> {
  4.         /*
  5.          * A DelayedWorkQueue is based on a heap-based data structure
  6.          * like those in DelayQueue and PriorityQueue, except that
  7.          * every ScheduledFutureTask also records its index into the
  8.          * heap array. This eliminates the need to find a task upon
  9.          * cancellation, greatly speeding up removal (down from O(n)
  10.          * to O(log n)), and reducing garbage retention that would
  11.          * otherwise occur by waiting for the element to rise to top
  12.          * before clearing. But because the queue may also hold
  13.          * RunnableScheduledFutures that are not ScheduledFutureTasks,
  14.          * we are not guaranteed to have such indices available, in
  15.          * which case we fall back to linear search. (We expect that
  16.          * most tasks will not be decorated, and that the faster cases
  17.          * will be much more common.)
  18.          *
  19.          * All heap operations must record index changes -- mainly
  20.          * within siftUp and siftDown. Upon removal, a task's
  21.          * heapIndex is set to -1. Note that ScheduledFutureTasks can
  22.          * appear at most once in the queue (this need not be true for
  23.          * other kinds of tasks or work queues), so are uniquely
  24.          * identified by heapIndex.
  25.          */
  27.         private static final int INITIAL_CAPACITY = 16;
  28.         private RunnableScheduledFuture<?>[] queue =
  29.             new RunnableScheduledFuture<?>[INITIAL_CAPACITY];
  30.         private final ReentrantLock lock = new ReentrantLock();
  31.         private int size = 0;
  32.     }

JAVA数据结构和算法笔记.pdf

参考：link