基础数据结构，动手写一遍

动态Array

从最基本的动态Array开始实现（实际上可以理解成自己动手实现了个ArrayList）总共实现下面这些方法：

底层还是使用数组，不过为了实现动态缩容扩容，我们包装了一些方法在里面：

• 字段

    public class Array<E>{
        //底层还是用数组实现
        private E[] data;
        //size记录data中真实存在的元素个数
        private int size;
         ...
    }

• 构造器

    public Array() {
        //默认实现给10个空间
        this(10);
    }
    
    public Array(E[] data) {//这块是拷贝，不是让底层的data直接指向传入的参数
        //这是Java不允许泛型数组，所以要Object数组强转
        this.data = (E[])new Object[data.length];
        for(int i = 0; i < data.length; i++) {
            this.data[i] = data[i];
        }
        size = data.length;
    }
    
    public Array(int Capacity) {
        //这是Java不允许泛型数组，所以要Object数组强转
        data = (E[]) new Object[Capacity];
        size = 0;
    }

• 封装一个异常检查
  用于下面各种方法中的Index或者findelement的检查，

    private void checkIndexRange(int index) {
        if (index < 0 || index >= data.length) {
            throw new IllegalArgumentException();
        }
    }

• 扩容函数
  我们的扩容策略会在下面add和remove中具体介绍，这里扩容函数就是New一个新容量的数组，然后把原数组的值复制进去就可以了。

    private void resize(int newCapacity) {
        E[] newArray = (E[]) new Object[newCapacity];
        
        for(int i = 0; i < size; i++) {
            newArray[i] = data[i];
        }
        
        data = newArray;
    }

• 一系列get和判空以及contains和find和set

    public int getSize() {
        return size;
    }
    
    public int getCapacity() {
        return data.length;
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public E get(int index) {
        checkIndexRange(index);
        return data[index];
    }
    
    public E getFirst() {
        return get(0);
    }
    
    public E getLast() {
        return get(size - 1);
    }
    
    public boolean contains(E element) {
        for(int i = 0; i < size; i++) {
            if (Objects.equals(data[i], element)) {
                return true;
            }
        }
        
        return false;
    }

    public int find(E element) {
        for(int i = 0; i < size; i++) {
            if (Objects.equals(data[i], element)) {
                return i;
            }
        }
        
        return -1;
    }

    public void set(int index, E element) {
        checkIndexRange(index);
        
        data[index] = element;
    }

• 增加和扩容策略
  我们在增加时候检查容量，采用最简单的扩容策略，在size等于最大容量时候，扩容为原来size的二倍。

    public void add(int index, E element) {
        checkIndexRange(index);
        
        if (size == data.length) {
            resize(2 * size);
        }
        
        for(int i = size; i > index; i--) {
            data[i] = data[i-1];
        }
        
        data[index] = element;
        
        size ++;
    }

    public void addFirst(E element) {
        add(0, element);
    }
    
    public void addLast(E element) {
        add(size, element);
    }

• 删除和缩容策略
  每次在删除元素时候检查size，缩容策略也很简单，最直白的策略就是size == data.length/2时候，又给缩回去，但是这样就会导致一种极端情况，如果数组的元素数目在data.length/2周围反复横跳add/remove，这样就会不停的缩容，扩容，改变容量的复杂度都是O(n)，这毫无疑问是一个负担。所以改变一下缩容的策略，在size== data.length/4时候去缩容到原来容量的一半。

    public E remove(int index) {
        checkIndexRange(index);
        //先保存下来要删除（返回）的值
        E ret = data[index];
        
        //然后从index开始把后一个元素赋值给前一个
        for(int i = index; i < size - 1; i++) {
            data[i] = data[i+1];
        }
        
        //最后一个元素赋为Null
        data[size - 1] = null;
        //别忘了维护size
        size --;
        
        //size减小之后如果到了四分之一长度，那就缩容为原来容量的一半，但是同时要注意 data.length/2不是0
        if (size == data.length/4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }
        
        return ret;
    }
    
    public E removeFirst() {
        return remove(0);
    }
    
    public E removeLast() {
        return remove(size);
    }
    
    public E removeElement(E element) {
        int index = find(element);
        
        return remove(index);
    }

这样就基本完成了一个伪的ArrayList，集合框架的源码肯定写的更强一些，也考虑的更周到一些，后面在总结集合源码时候会进行分析。

PriorityQueue

首先基于上面实现的Array为底层，实现一个heap。
需要有下面的方法：

• 字段
  就只有一个底层的Array，我们用Array直接来模拟堆这个二叉树。需要理解的基本概念是是个节点对应下标如果是i（从0开始），那么它的左孩子就是2 * i+1，右孩子就是2 * i+2，而它的父亲节点是(i - 1) / 2。如果下标从1开始会有不同结果，自行推导即可。

    private Array<E> data;

• 构造器
  先写两个，最后一个最后介绍。

    public MaxHeap() {
        this.data = new Array<>();
    }
    
    public MaxHeap(int Capacity) {
        this.data = new Array<>(Capacity);
    }
    

• 判空和长度以及获取左右孩子和父亲节点

    public boolean isEmpty() {
        return data.isEmpty();
    }
    public int size() {
        return data.getSize();
    }
    private int parent(int index) {
        return (index-1)/2;
    }

    private int leftChild(int index) {
        return 2 * index + 1;
    }
    private int rightChild(int index) {
        return 2 * index + 2;
    }
    

• 最核心的shiftUp和shiftDown 都是logn。
  shiftUp，就是上浮，当新加入一个节点时候我们把一个值和它的父亲相比，如果它要比父亲节点的值更大，那么就交换节点，以此类推往上不断考察，直到父亲节点比他的值大为止。
  shiftDown则反之，是下沉，这个方法在取出最大值，和Heapify的过程中要用到。是把当前节点和儿子节点相比，不过需要考察两个节点，我们要把当前节点和左右儿子中更大的那个交换，而如果当前节点比左右儿子都大，那就下沉结束了。

    private void shiftDown(int index) {
        while(leftChild(index)< size()) {
            int j = leftChild(index);
            //第一步找到左右孩子中更大的那一个
            if(j + 1 < size() && data.get(j+1).compareTo(data.get(j))>0) {
                j = rightChild(index);
            }
            //j现在代表的不管是左还是右，反正都是最大的
            //如果当前节点比左右孩子更大的那个还要大，那就说明不再需要shiftDown了，不用再交换
            if (data.get(index).compareTo(data.get(j))>0) {
                break;
            }
            
            //如果上面的循环没有跳出去，那就说明肯定是孩子比他大的，不管左还是右，只管jjjjjj，交换一下即可
            data.swap(index, j);
            
            //再把指针挪到j上面
            index = j;
        }
    }
    
    private void shiftUp(int index) {
        while(parent(index) >= 0 && data.get(index).compareTo(data.get(parent(index)))>0) {
            data.swap(index, parent(index));
            index = parent(index);
        }
    }

写的代码上来看，shiftUp会更加简单一些，毕竟只需要比较一个节点，shiftDown写的时候，就是找到儿子中最大的那一个，并记录下标，然后把当前节点和最大的那个比一下，这是比较优秀的写法。

• 添加节点

    /* 
     * 添加过程是先在数组末尾添加新元素，
     * 然后为了保持堆的特性，要对最后添加的新元素进 
     * 行shiftUp操作
     */ 
    public void add(E e) {
        data.addLast(e);
        shiftUp(size() - 1);
    }

• 拿出最大元素

   /*
    * 拿出最大元素之后依然要保持堆的特性，
    *所以这里的方法是，先把最后一个节点值交换到第0位 
    *最大的位置，然后把最后一个位置删除掉，然后再对 
    *最大节点进行下沉操作维护堆的特性。
    */  
    public E extractMax() {
        E max = findMax();
        data.swap(0, size()-1);
        data.removeLast();
        
        shiftDown(0);
        return max;
    }
    
    public E findMax() {
        return data.getFirst();
    }

• 第三个构造器——Heapify
  最后我们再来谈一下第三个构造器的故事......从Heapify这个名字大概能猜到，我们这个构造器是把一个数组“堆化”，思想是把数组拷进来先放在“树”上，这时候它是按照原来数组的顺序依次放进去的，不是一个堆，我们从第一个非叶子节点开始到根节点依次shiftDown，就可以把这个数组变成一个堆。这个复杂度是O（n），暂时想不通，后面查找资料学习后来填坑。

    //这个构造函数对应的过程叫Heapify
    public MaxHeap(E[] array) {
        //先把数组弄进来
        data = new Array<>(array);
        //从第一个非叶子节点开始 shiftDown
        for(int i = parent(size() - 1); i >= 0; i--) {
            shiftDown(i);
        }
    }

这里基本上这个堆的结构是实现了，我们在它之上包装上PriorityQueue的接口就好了。

public class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
    private MaxHeap<E> maxHeap;
    public PriorityQueue() {
        maxHeap = new MaxHeap<>();
    }
    @Override
    public int getSize() {
        return maxHeap.size();
    }

    @Override
    public boolean isEmpty() {
        return maxHeap.isEmpty();
    }

    @Override
    public void enqueue(E e) {
        maxHeap.add(e);
    }

    @Override
    public E dequeue() {
        return maxHeap.extractMax();
    }

    @Override
    public E getFront() {
        return maxHeap.findMax();
    }

    
}

Java的util包下面的PriorityQueue是个最小堆，不过可以通过构造器传入自定义的Comparator来决定这个PriorityQueue的判定标准。

BST

二分搜索树是在是再常见不过了。
首先需要定义一个节点类，我们这里放成内部类。

• 节点内部类

public class BinarySearchTree<E> {
    class Node{
        public Node left,right;
        public E e;
        
        public Node(E e){
            this.e = e;
            left = null;
            right = null;
        }
    }
          .....
    
}

• 字段
  一个树根节点treeRoot，和一个节点数size。

    private Node treeRoot;
    private int size;

• 构造器

    public BinarySearchTree() {
        treeRoot = null;
        size = 0;
    }

• size()和判空

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return size == 0;
    }

• 添加节点
  我们对外提供一个public的void add(E e)方法，然后内部实现是一个返回值为Node的方法，它返回传入的root节点，并递归去找到需要添加的节点的位置，大于当前节点的值到右子树去找，小于当前节点的值到左子树去找。

    public void add(E e) {
        treeRoot = add(treeRoot, e);
    }
    
    private Node add(Node root, E e) {
        if (root == null) {
            size++;
            return new Node(e);
        }
        
        if (root.e.compareTo(e) == 0) {
            return root;
        }
        
        if (e.compareTo(root.e)>0) {
            root.right = add(root.right, e);
        }else {
            root.left = add(root.left, e);
        }
        
        return root;
    }

• contains
  和add的写法比较相似。递归去找e的位置。

    public boolean contains(E e) {
        return contains(treeRoot,e);
    }
    
    private boolean contains(Node root, E e) {
        if (root == null) {
            return false;
        }
        
        if (root.e.compareTo(e)==0) {
            return true;
        }
        
        if (e.compareTo(root.e) > 0) {
            return contains(root.right,e);
        } else {
            return contains(root.left, e);
        }
    }   

• 先序、中序、后序和层序遍历（还有一种在剑指上看到的之字形遍历，都可以通过栈模拟一下）
  先中后序遍历的递归实现。

    public void preOrder() {
        System.out.println("preOrder:");
        preOrder(treeRoot);
    }
    
    private void preOrder(Node root) {
        if (root == null) {
            return ;
        }
        
        System.out.println(root.e);
        preOrder(root.left);
        preOrder(root.right);
    }

    public void inOrder() {
        System.out.println("inOrder:");
        inOrder(treeRoot);
    }
    
    private void inOrder(Node root) {
        if (root == null) {
            return ;
        }
        
        inOrder(root.left);
        System.out.println(root.e);
        inOrder(root.right);    
    }
    
    public void postOrder() {
        System.out.println("postOrder:");
        postOrder(treeRoot);
    }
    
    private void postOrder(Node root) {
        if (root == null) {
            return ;
        }
        
        postOrder(root.left);
        postOrder(root.right);
        System.out.println(root.e);
    }

下面是先序的非递归实现，我们是用一个Stack去模拟系统的栈，从树根入栈开始，取栈顶先加右再加左入栈，直到栈取空为止。

    private void preOrderNotRecursively(Node root) {
        if (root == null) {
            return ;
        }
        
        Stack<Node> stack = new Stack<>();
        
        stack.push(root);
        
        while(!stack.isEmpty()) {
            Node node = stack.pop();
            
            System.out.println(node.e);
            
            if (node.right != null) {
                stack.push(node.right);
            }
            
            if (node.left != null) {
                stack.push(node.left);
            }
        }
    }

然后再来层序遍历，这种依赖于队列来实现。从根节点入队开始，取出队首节点访问，先入左再入右。直到队空为止。

    public void levelOrder() {
        System.out.println("leverOrder:");
        levelOrder(treeRoot);
    }
    
    private void levelOrder(Node root) {
        if (root == null) {
            return ;
        }
        
        Queue<Node> queue = new LinkedList<>();
        
        queue.offer(root);
        
        while(!queue.isEmpty()) {
            Node node = queue.poll();
            
            System.out.println(node.e);
            
            if (node.left != null) {
                queue.offer(node.left);
            }
            
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
    }

接下来的一系列方法，都是为remove服务的，我们一步步来，bst中的remove方法确实要复杂于那些add操作。

• get最大和最小递归和非递归都写了

    public E getMax() {
        if (isEmpty()) {
            throw new NullPointerException();
        }
        return getMax(treeRoot).e;
    }
    private Node getMax(Node root) {
        if (root.right == null) {
            return root;
        }
        
        return getMax(root.right);
    }
    
    private Node getMaxNotRecursively(Node root) {
        if (root == null) {
            return null;
        }
        
        while(root.right != null) {
            root = root.right;
        }
        
        return root;
    }
    
    public E getMin() {
        if (isEmpty()) {
            throw new NullPointerException();
        }
        return getMin(treeRoot).e;
    }
    
    private Node getMin(Node root) {
        if(root.left == null) {
            return root;
        }
        
        return getMin(root.left);
    }
    
    private Node getMinNotRecursively(Node root) {
        if (root == null) {
            return null;
        }
        
        while(root.left != null) {
            root = root.left;
        }
        
        return root;
    }
    

• removeMax和removeMin

    public E removeMax() {
        E ret = getMax();
        treeRoot = removeMax(treeRoot);
        return ret;
    }
    
    /*
     * 删除以root为根的子树的最大节点
     * 返回删除最大节点后的子树的根
     * 删除的过程是用该节点的左孩子直接代替它
     */
    private Node removeMax(Node root) {
        if (root.right == null) {
            Node leftNode = root.left;
            root.left = null;
            return leftNode;
        }
        
        root.right = removeMax(root.right);
        return root;
    }
    public E removeMin() {
        E ret = getMin();
        treeRoot = removeMin(treeRoot);
        return ret;
    }
    
    /*
     * 删除以root为根的子树中的最小节点
     * 返回删除最小节点后的子树的根
     * 删除的过程是一直往左走，找到最左节点，用该节点的右孩子代替它
     */
    private Node removeMin(Node root) {
        if (root.left == null) {
            Node rightNode = root.right;
            root.right = null;
            return rightNode;
        }
        
        root.left = removeMin(root.left);
        return root;
    }

• removeNode删除任意一个节点
  我们上面做的所有工作都是为了它。

    /*
     * 删除以root为根节点的子树中值为e的节点
     * 返回删除目的节点后的子树的根
     * 删除的过程就是根据e的值和当前节点的值的比较结果
     * 向左或者向右去走，直到找到目的节点
     * 这时候有三种情况。
     * 1.左子树为空，那就直接用它的右孩子去代替这个节点
     * 2.右子树为空，那就直接用它的左孩子去代替这个节点
     * 3.左右子树都不为空，我们找它的后继节点successor，
     * 也就是右子树中的最小节点，用这个节点来代替它（或者找
     * 前驱节点，左子树中的最大节点，用这个节点来代替它）,还要
     * 记的把后继（前驱）节点删除掉。
     */
    private Node removeNode(Node root, E e) {
        
        if (root == null) {
            return null;
        }
        
        if (e.compareTo(root.e)>0) {
            root.right = removeNode(root.right,e);
            return root;
        }
        
        if (e.compareTo(root.e)<0) {
            root.left = removeNode(root.left, e);
            return root;
        }
        
        if (root.left == null) {
            Node rightNode = root.right;
            root.right = null;
            size--;
            return rightNode;
        }
        
        if (root.right == null) {
            Node leftNode = root.left;
            root.left = null;
            size--;
            return leftNode;
        }
        
        //左右子树都不为空,找到后继节点——右子树中的最小值
        Node successor = getMin(root.right);
        
        successor.right = removeMin(root.right);
        successor.left = root.left;
        
        root.left = null;
        root.right = null;
        
        
        return successor;
    }