Day01

数据结构–树

基本概念

每棵树都父节点和子节点，有且只有一个根节点，树有n层，每一层的节点称为兄弟节点，上下层为父子节点，最后一层为叶子结点。一个有n层的树，高度为n-1，深度为n-1。

分类

二叉树，完全二叉树，堆

二叉树，二叉查找树，二叉平衡树，红黑树

满二叉树即每个节点都有两个子节点。

完全二叉树，从左到右都是满的，如果有空缺，按照先缺右边再少左边，不允许缺左满右！

二叉查找树，左边的节点小，右边的节点大，相对于公共节点。因为有退化为链表的风险，因此出现了二叉平衡树。

Java内存模型

java内存模型是虚拟概念，在实际的硬件中是没有的。

java内存模型是一种规范：

所有的变量都存储在主内存（Main Memory）中。

每个线程都有一个私有的本地内存（Local Memory），本地内存中存储了该线程以读/写共享变量的拷贝副本。

线程对变量的所有操作都必须在本地内存中进行，而不能直接读写主内存。

不同的线程之间无法直接访问对方本地内存中的变量。

为了更好的控制主内存和本地内存的交互，Java 内存模型定义了八种操作来实现：

lock：锁定。作用于主内存的变量，把一个变量标识为一条线程独占状态。

unlock：解锁。作用于主内存变量，把一个处于锁定状态的变量释放出来，释放后的变量才可以被其他线程锁定。

read：读取。作用于主内存变量，把一个变量值从主内存传输到线程的工作内存中，以便随后的load动作使用

load：载入。作用于工作内存的变量，它把read操作从主内存中得到的变量值放入工作内存的变量副本中。

use：使用。作用于工作内存的变量，把工作内存中的一个变量值传递给执行引擎，每当虚拟机遇到一个需要使用变量的值的字节码指令时将会执行这个操作。

assign：赋值。作用于工作内存的变量，它把一个从执行引擎接收到的值赋值给工作内存的变量，每当虚拟机遇到一个给变量赋值的字节码指令时执行这个操作。

store：存储。作用于工作内存的变量，把工作内存中的一个变量的值传送到主内存中，以便随后的write的操作。

write：写入。作用于主内存的变量，它把store操作从工作内存中一个变量的值传送到主内存的变量中。

指令重排序

java中有指令重排序的概念，学过的都知道用volatile可以防止重排序。在java并发编程里面，三大原则，原子性，可见性，有序性。下面就深入底层一探究竟。

在硬件架构中，有cpu，内存，缓存，首先CPU的计算速度是最快的，内存相对较慢，很难满足cpu’的计算能力，所以在cpu和内存之间加上了高速缓存，先把内存中的数据放入缓存，再从缓存中读取数据。由于每个cpu都有自己的缓存，所以就会出现一个新的问题，即缓存一致性问题，

在多CPU的系统中(或者单CPU多核的系统)，每个CPU内核都有自己的高速缓存，它们共享同一主内存(Main Memory)。当多个CPU的运算任务都涉及同一块主内存区域时，CPU 会将数据读取到缓存中进行运算，这可能会导致各自的缓存数据不一致。

因此需要每个 CPU 访问缓存时遵循一定的协议，在读写数据时根据协议进行操作，共同来维护缓存的一致性。

CPU性能优化

为了进一步增加CPU的性能，人们又采取一个新的措施，就是处理器优化。

为了使处理器内部的运算单元能够最大化被充分利用，处理器会对输入代码进行乱序执行处理，这就是处理器优化。

处理器优化其实也是重排序的一种类型，这里总结一下，重排序可以分为三种类型：

编译器优化的重排序。编译器在不改变单线程程序语义放入前提下，可以重新安排语句的执行顺序。

指令级并行的重排序。现代处理器采用了指令级并行技术来将多条指令重叠执行。如果不存在数据依赖性，处理器可以改变语句对应机器指令的执行顺序。

内存系统的重排序。由于处理器使用缓存和读写缓冲区，这使得加载和存储操作看上去可能是在乱序执行

上面说的『可见性问题』、『原子性问题』、『有序性问题』其实就对应『缓存一致性』、『处理器优化』、『指令重排序』。

出了问题总是要解决的，那有什么办法呢？首先想到简单粗暴的办法，干掉缓存让 CPU 直接与主内存交互就解决了可见性问题，禁止处理器优化和指令重排序就解决了原子性和有序性问题，但这样一夜回到解放前了，显然不可取。

所以技术前辈们想到了在物理机器上定义出一套内存模型， 规范内存的读写操作。内存模型解决并发问题主要采用两种方式：限制处理器优化和使用内存屏障。

堆排序

public class Test_Heap {
    public static void headSort(int[] list) {
        //构造初始堆,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
        for (int i = (list.length) / 2 - 1; i >= 0; i--) {
            headAdjust(list, list.length, i);
        }
        //排序，将最大的节点放在堆尾，然后从根节点重新调整
        for (int i = list.length - 1; i >= 1; i--) {
            list[0] = list[0] ^ list[i];
            list[i] = list[0] ^ list[i];
            list[0] = list[0] ^ list[i];
            headAdjust(list, i, 0);
        }
    }

    private static void headAdjust(int[] list, int len, int i) {
        int k = i, temp = list[i], index = 2 * k   1;
        while (index < len) {
            if (index   1 < len) {
                if (list[index] < list[index   1]) {
                    index = index   1;
                }
            }
            if (list[index] > temp) {
                list[k] = list[index];
                k = index;
                index = 2 * k   1;
            } else {
                break;
            }
        }
        list[k] = temp;
    }


    public static void main(String[] args) {
        int[] arr=new int[]{66,13,51,76,81,26,57,69,23};
        //堆排序
        headSort(arr);

        System.out.println("堆排序后的结果是:");
        for(int i=0;i<arr.length;i  )
            System.out.print(arr[i] "\t");
    }

}

这篇好文章是转载于：学新通技术网