堆的定义

这里说的堆是指二叉堆,二叉堆是完全二叉树或者是近似完全二叉树。
二叉堆满足二个特性：

• 父结点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
• 每个结点的左子树和右子树都是一个二叉堆（都是最大堆或最小堆）。

当父结点的键值总是大于或等于任何一个子节点的键值时为最大堆。当父结点的键值总是小于或等于任何一个子节点的键值时为最小堆

因为堆的本质是完全二叉树，因此

1

对于一个结点数为n的堆，其高度为lgn，证明过程可以设高度为h，则n>=2^h-1且n<2^(h+1)-1，即可推导出结果

因此插入或者移除一个元素的时间复杂度即为O(lgn)

优先队列

优先队列是一个无界队列，可以按照默认排序或者指定的comparator来排序，本质上仍然是一个堆，注意到这是非线程安全的。

堆的基本操作

往堆中添加元素其实就是要维护堆的属性，这里直接分析Java中优先队列的实现:

siftUpComparable是add的核心实现

1
2
3
4
5
6
7
8
9
10
11
12

private void siftUpComparable(int k, E x) {
    Comparable<? super E> key = (Comparable<? super E>) x;
    while (k > 0) {
        int parent = (k - 1) >>> 1;
        Object e = queue[parent];
        if (key.compareTo((E) e) >= 0)
            break;
        queue[k] = e;
        k = parent;
    }
    queue[k] = key;
}

其中

1

int parent = (k - 1) >>> 1;

volatile的引入是为了解决java并发编程中的可见性与有序性的问题。
java并发编程要注意以下三个问题

• 原子性
• 可见性
• 有序性

同时满足以上三个性质才能解决并发的问题

java内存模型

Java内存模型规定所有的变量都是存在主存当中（物理内存），每个线程都有自己的工作内存（高速缓存）。线程对变量的所有操作都必须在工作内存中进行，而不能直接对主存进行操作。并且每个线程不能访问其他线程的工作内存。

Happens-before原则

原子性

原子性即某个操作CPU可以用一条指令执行完成的，要么执行，要么不执行，不存在中途停下的问题。
如下：

1
2
3

x = 4
x = y
x++

只有第一句为原子操作，通常Java内存模型只保证了基本读取和赋值是原子性操作，变量之间的复制也不是原子操作

可见性

有序性

volatile做了什么事情？

经过volatile修饰的变量保证了如下两件事：

• 可见性：不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的
• 有序性：禁止进行指令重排序

1
2

为什么会有指令重排？
因为处理器为了有更高的效率，编译器可能会将单线程下不影响执行效果的代码重排序