数据结构相关的一些复习笔记，本文很长善用目录跳转。

数组

Array 的属性：size 表示已存在的元素个数，capacity 是 Array 的容积。

contains

判断 Array 中是否含有某个元素的办法是进行遍历：

public boolean contains(E value) {
    for (E m : data) {
        if (value.equals(m)) {
            return true;
        }
    }
    return false;
}

查找元素

从前往后遍历，找到则返回元素索引，没找到则返回 -1：

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

resize

有时在进行添加/删除时需要对 Array 进行扩容/缩容操作，此时可以准备一个 resize 方法，在 Array 需要被扩容或者缩容时调用该方法，这个方法的思路是进行遍历将旧 Array 的元素一个个赋值给新 Array 中的元素：

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

向 Array 中插入元素

向 Array 中添加元素时要考虑 Array 已满的情况，如果已经满了则进行扩容，具体为扩大一倍。

插入元素的思路是将被插入位置及其之后的元素向后移一位，最后把要插入的元素赋值给 data[index]，同时注意维护 size 的值。

public void add(int index, E value) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("add() failed. Requirement: 0 <=index <= size.");
    }
    if (size == data.length) {
        resize(2 * data.length);
    }
    for (int i = size - 1; i >= index; i--) {
        data[i + 1] = data[i];
    }
    data[index] = value;
    size++;
}

给出索引移除 Array 中的元素

移除元素则很简单，把要移除的元素赋值给 temp，被移除元素之后的元素各向前移动一位，最后将 temp 返回即可。注意调整 size 的值。

移除元素后需要判断是否要缩容，通常判断缩容的条件是已存在元素个数等于容积的一半，但我们无法预测下次对 Array 的操作是 add 还是 remove，如果是 add 那么又需要进行一次扩容，这样会造成时间浪费。

所以更改判断条件：当元素个数是容积的 1 / 4 时才进行缩容操作，并且此时只缩容一半（而不是缩容到原来的 1/ 4）以应对下次可能的 add 操作。

与此同时还存在一个边界特殊情况：capacity 为 1 时不能再进行缩容，这也是需要判断的条件之一。

public E remove(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("remove() failed, index is illegal.");
    }
    E removedValue = data[index];
    for (int i = index + 1; i < size; i++) {
        data[i - 1] = data[i];
    }
    size--;
    // loitering objects != memory leak
    data[size] = null;
    if (size == data.length / 4 && data.length / 2 != 0) {
        resize(data.length / 2);
    }
    return removedValue;
}

给出元素值并将其在 Array 中移除

如果要删除某个特定值的元素，只要进行查找然后调用 remove 方法即可：

public void removeElement(E value) {
    int index = find(value);
    if (-1 != index) {
        remove(index);
    }
}

附完整代码

package array;

/**
 * 自定义的 Array 类
 *
 * @author 陶波利
 */
public class Array<E> {
    private E[] data;
    private int size;

    public Array() {
        this(10);
    }

    public Array(int capacity) {
        data = (E[]) new Object[capacity];
        size = 0;
    }

    public Array(E[] arr) {
        data = (E[]) new Object[arr.length];
        for (int i = 0; i < arr.length; i++) {
            data[i] = arr[i];
        }
        size = arr.length;
    }

    public int getSize() {
        return size;
    }

    public int getCapacity() {
        return data.length;
    }

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

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("get() failed, index is illegal.");
        }
        return data[index];
    }

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

    public boolean isContaianed(E value) {
        for (E m : data) {
            if (value.equals(m)) {
                return true;
            }
        }
        return false;
    }

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

    public void add(int index, E value) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add() failed. Requirement: 0 <=index <= size.");
        }
        if (size == data.length) {
            resize(2 * data.length);
        }
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        data[index] = value;
        size++;
    }

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

    public void addFirst(E value) {
        add(0, value);
    }

    public void addLast(E value) {
        add(size, value);
    }

    public E remove(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("remove() failed, index is illegal.");
        }
        E removedValue = data[index];
        for (int i = index + 1; i < size; i++) {
            data[i - 1] = data[i];
        }
        size--;
        // loitering objects != memory leak
        data[size] = null;
        if (size == data.length / 4 && data.length / 2 != 0) {
            resize(data.length / 2);
        }
        return removedValue;
    }

    public E removeFirst() {
        return remove(0);
    }

    public E removeLast() {
        return remove(size - 1);
    }

    public void removeElement(E value) {
        int index = find(value);
        if (-1 != index) {
            remove(index);
        }
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Array: size = %d, capacity = %d\n", size, data.length));
        builder.append("[");
        for (int i = 0; i < size; i++) {
            builder.append(data[i]);
            if (i != size - 1) {
                builder.append(", ");
            }
        }
        builder.append("]");
        return builder.toString();
    }

    public E getLast() {
        return get(size - 1);
    }

    public E getFirst() {
        return get(0);
    }

    /**
     * 交换索引为 i j 的元素
     *
     * @param i index i
     * @param j index j
     */
    public void swap(int i, int j) {
        if (i < 0 || i >= size || j < 0 || j >= size) {
            throw new IllegalArgumentException("Index is illegal");
        }
        E temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }
}

栈

栈接口

首先对栈进行一下抽象，栈的特性是先入后出，栈的主要三个方法是 push（入栈），pop（出栈），peek（查看栈顶元素）：

package stack;

public interface Stack<E> {
    int getSize();

    boolean isEmpty();

    void push(E e);

    E pop();

    E peek();
}

使用数组实现栈

实现很简单，直接用以前写的 Array 就好。

package stack;

import array.Array;

/**
 * @author Boli Tao
 */
public class ArrayStack<E> implements Stack<E> {
    Array<E> array;

    public ArrayStack(int capacity) {
        array = new Array<>(capacity);
    }

    public ArrayStack() {
        array = new Array<>();
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

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

    @Override
    public void push(E e) {
        array.addLast(e);
    }

    @Override
    public E pop() {
        return array.removeLast();
    }

    @Override
    public E peek() {
        return array.getLast();
    }


    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("Stack: ");
        stringBuilder.append("[");
        for (int i = 0; i < array.getSize(); i++) {
            stringBuilder.append(array.get(i));
            if (i != array.getSize() - 1) {
                stringBuilder.append(", ");
            }
        }
        stringBuilder.append("] top");
        return stringBuilder.toString();
    }
}

使用链表实现栈

由于对于链表头节点的增删查操作时间复杂度为 O(1)，所以使用链表实现的栈性能较数组栈性能更好。

package stack;

import LinkedList.LinkedList;

/**
 * @author Boli Tao
 */
public class LinkedListStack<E> implements Stack<E> {
    private LinkedList<E> list;

    public LinkedListStack() {
        list = new LinkedList<E>();
    }

    @Override
    public int getSize() {
        return list.getSize();
    }

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

    @Override
    public void push(E e) {
        list.addFirst(e);
    }

    @Override
    public E pop() {
        return list.removeFirst();
    }

    @Override
    public E peek() {
        return list.getFirst();
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Stack: top ");
        builder.append(list);
        return builder.toString();
    }

    public static void main(String[] args) {
        LinkedListStack<Integer> linkedListStack = new LinkedListStack<>();
        for (int i = 0; i < 10; i++) {
            linkedListStack.push(i);
            System.out.println(linkedListStack);
        }
        linkedListStack.pop();
        System.out.println(linkedListStack);
        System.out.println(linkedListStack.peek());
    }
}

队列

队列接口

队列的特性是先入先出（参考排队），重要的三个方法是enqueue（入队），dequeue（出队），getFront（查看队首元素）。

package queue;

public interface Queue<E> {
    int getSize();

    boolean isEmpty();

    void enqueue(E e);

    E dequeue();

    E getFront();
}

数组实现的队列

package queue;

import array.Array;

public class ArrayQueue<E> implements Queue<E> {
    Array<E> array = new Array<>();

    public ArrayQueue() {
        array = new Array<>();
    }

    public ArrayQueue(int capacity) {
        array = new Array<>(capacity);
    }

    @Override
    public int getSize() {
        return array.getSize();
    }

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

    @Override
    public void enqueue(E e) {
        array.addLast(e);
    }

    @Override
    public E dequeue() {
        return array.removeFirst();
    }

    @Override
    public E getFront() {
        return array.getFirst();
    }

    public int getCapacity() {
        return array.getCapacity();
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append("Queue: front [");
        for (int i = 0; i < array.getSize(); i++) {
            builder.append(array.get(i));
            if (i != array.getSize() - 1) {
                builder.append(", ");
            }
        }
        builder.append("] tail");
        return builder.toString();
    }

    public static void main(String[] args) {
        ArrayQueue<Integer> arrayQueue = new ArrayQueue<>();
        for (int i = 0; i < 10; i++) {
            arrayQueue.enqueue(i);
        }
        System.out.println(arrayQueue);
        arrayQueue.dequeue();
        System.out.println(arrayQueue);
        arrayQueue.enqueue(20);
        System.out.println(arrayQueue);
    }
}

循环队列

判空：front == tail

规定满的条件：(tail + 1) % capacity == front。

由于总是浪费一个空间，所以 getCapacity() 方法返回的是 data.length - 1

resize()

重新分配容积时和数组的 resize() 方法类似，但是由于队列是循环的所以需要额外应对 tail 在 front 前的情况，比如下图：

此时遍历赋值时不能单纯使用 temp[i] = data[(front + i)]，而要使用 temp[i] = data[(front + i) % data.length]。调整容积后的 LoopQueue 可以看作一个标准的数组队列，需要将 front 调整为 0，tail 值调整为 size（size - 1 + 1）。

private void resize(int newCapacity) {
    E[] temp = (E[]) new Object[newCapacity];
    // 第一种遍历的方式
    for (int i = 0; i < size; i++) {
        temp[i] = data[(front + i) % data.length];
    }
    data = temp;
    front = 0;
    tail = size;
}

入队

和数组类似，入队时需要判断队列是否满，如果满需要进行扩容。入队后注意维护 tail 和 size 的值，size 直接 ++ 就好，而为了应对 tail 在 front 前的情况不能直接 ++，需要对 capacity 取余：

@Override
public void enqueue(E e) {
    if ((tail + 1) % data.length == front) {
        resize(getCapacity() * 2);
    }
    data[tail] = e;
    tail = (tail + 1) % data.length;
    size++;
}

出队

某元素出队后 front 只需要 ++ 即可，同样为了应对 front 从队尾跑到队首的情况要对 capacity 取余，注意调整 size 大小。

出队后和 Array 类似，可以判断是否进行缩容，原理和 Array 一样，当元素个数为容积的 1/4 时才进行缩容，并且只缩容到原容积的 1/2（而不是 1/4）以应对未知的下次操作。

@Override
public E dequeue() {
    if (isEmpty()) {
        throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
    }
    E ret = data[front];
    data[front] = null;
    front = (front + 1) % data.length;
    size--;
    if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
        resize(getCapacity() / 2);
    }
    return ret;
}

循环队列的两种遍历方式

请查看循环队列实现源码的注释部分，其实本质一样，我个人更能理解第一种。

循环队列所有代码

package queue;

/**
 * @author Boli Tao
 */
public class LoopQueue<E> implements Queue<E> {
    private E[] data;
    private int tail, front, size;

    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }

    public LoopQueue() {
        this(10);
    }

    public int getCapacity() {
        return this.data.length - 1;
    }

    public boolean isFull() {
        return (tail + 1) % data.length == front;
    }

    private void resize(int newCapacity) {
        E[] temp = (E[]) new Object[newCapacity];
        // 第一种遍历的方式
        for (int i = 0; i < size; i++) {
            temp[i] = data[(front + i) % data.length];
        }
        data = temp;
        front = 0;
        tail = size;
    }

    @Override
    public int getSize() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return front == tail;
    }

    @Override
    public void enqueue(E e) {
        if ((tail + 1) % data.length == front) {
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        tail = (tail + 1) % data.length;
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }
        E ret = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size--;
        if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
            resize(getCapacity() / 2);
        }
        return ret;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty.");
        }
        return data[front];
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        builder.append(String.format("Queue: size = %d, capacity = %d.\n", size, getCapacity()));
        builder.append("front [");
        // 第二种遍历的方式
        for (int i = front; i != tail; i = (i + 1) % data.length) {
            builder.append(data[i]);
            if ((i + 1) % data.length != tail) {
                builder.append(", ");
            }
        }
        builder.append("] tail");
        return builder.toString();
    }

    public static void main(String[] args) {
        LoopQueue<Integer> loopQueue = new LoopQueue<>(5);
        for (int i = 0; i < 10; i++) {
            loopQueue.enqueue(i);
            System.out.println(loopQueue);
        }
        System.out.println();
        for (int i = 0; i < 10; i++) {
            loopQueue.dequeue();
            System.out.println(loopQueue);
        }
    }
}

链表实现的队列

package queue;

/**
 * @author Boli Tao
 */
public class LinkedListQueue<E> implements Queue<E> {
    private class Node {
        public E e;
        public Node next;

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        public Node() {
            this(null, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node head, tail;
    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

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

    @Override
    public void enqueue(E e) {
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        } else {
            tail.next = new Node(e);
            tail = tail.next;
        }
        size++;
    }

    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Queue is empty, cannot dequeue.");
        }
        Node dequeueNode = head;
        E returnValue = dequeueNode.e;
        dequeueNode = null;
        head = head.next;
        if (head == null) {
            tail = null;
        }
        size--;
        return returnValue;
    }

    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException();
        }
        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        stringBuilder.append("Queue: front ");
        Node current = head;
        while (current != null) {
            stringBuilder.append(current + "->");
            current = current.next;
        }
        stringBuilder.append("NULL tail");
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<>();
        for (int i = 0; i < 10; i++) {
            linkedListQueue.enqueue(i);
            System.out.println(linkedListQueue);
        }
        for (int i = 0; i < 10; i++) {
            linkedListQueue.dequeue();
            System.out.println(linkedListQueue);
        }
    }
}

优先队列

最大堆具有优先队列特性，在入队时通过下沉对优先级进行排序，并且可以保证每次出队都是优先级最高的元素。以下是最大堆实现的优先队列，关于最大堆可以看本人堆相关的文章。

package queue;

import heap.MaxHeap;

/**
 * @author 陶波利
 */
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.getMax();
    }
}

链表

链表中的节点

节点中的 next 引用就是链表的精华了。

private class Node {
    public E e;
    public Node next;

    public Node() {
        this(null, null);
    }

    public Node(E e, Node next) {
        this.e = e;
        this.next = next;
    }

    public Node(E e) {
        this(e, null);
    }

    @Override
    public String toString() {
        return e.toString();
    }
}

虚拟头节点

为了便于之后的理解和使用在链表中添加一个虚拟头节点，无参构造函数会实例化 Node(null, null) 赋值给 dummyNode：

public LinkedList() {
    dummyNode = new Node();
    size = 0;
}

向链表中添加元素

想要在索引处添加一个元素只需要以 dummyNode 为 prev，一路 next 到索引位置即可，随后的插入只要执行 prev.next = new Node(666, prev.next) 即可。

public void add(int index, E e) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("add() filed, illegal index.");
    }
    Node prev = dummyNode;
    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }
    prev.next = new Node(e, prev.next);
    size++;
}

获取链表中某索引位置的值 get()

public E get(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Illegal argument");
    }
    Node current = dummyNode.next;
    for (int i = 0; i < index; i++) {
        current = current.next;
    }
    return current.e;
}

修改索引位置节点的值

和 get() 类似，当 current 节点经过循环到达索引处时，直接修改 current.e 即可。

public void update(int index, E e) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Illegal argument");
    }
    Node node = dummyNode.next;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    node.e = e;
}

判断链表中是否某值

直接遍历链表，找到符合的返回 true，否则返回 false：

public boolean contains(E e) {
    Node current = dummyNode.next;
    while (current != null) {
        if (current.e.equals(e)) {
            return true;
        }
        current = current.next;
    }
    return false;
}

删除给定索引位置的元素

与添加操作类似，在删除操作中被删除节点的前序节点对于链表的连接有重要作用，图示删除索引为 2 的元素：

只需要执行 prev.next = delNode.next 即可。

此后需要让 delNode 脱离链表，以便 Java 进行垃圾回收，否则 delNode 会成为游离对象，具体操作即 delNode.next = null，这是一个个人比较难理解的地方，如果不明白可以看看 Java 的引用那一部分。

还是那句老话，不要忘记维护 size（

public E delete(int index) {
    if (index < 0 || index >= size) {
        throw new IllegalArgumentException("Illegal argument");
    }
    Node prev = dummyNode;
    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }
    Node deletedNode = prev.next;
    E deletedData = deletedNode.e;
    prev.next = deletedNode.next;
    size--;
    // deletedNode = null;
    deletedNode.next = null;
    return deletedData;
}

删除链表中的某个特定值

遍历、找到前序节点、进行删除。

public void removeElement(E e) {
    Node prev = dummyNode;
    while (prev.next != null) {
        if (prev.next.e.equals(e)) {
            break;
        }
        prev = prev.next;
    }
    if (prev.next != null) {
        Node delNode = prev.next;
        prev.next = delNode.next;
        delNode.next = null;
        size--;
    }
}

时间复杂度分析

添加操作

addLast(e)：O(n)

addFirst(e): O(1)

add(index, e): O(n /2) = O(n)

删除操作

removeLast(e): O(n)

removeFirst(e): O(1)

remove(index, e): O(n/2) = O(n)

修改

set(index, e): O(n)

查找

get(index): O(n)

contains(e): O(n)

总结

增 O(n)
删 O(n)
改 O(n)
查 O(n)

用途

由于对链表头节点来说其增删时间复杂度为 O(1)，并且如果只对头节点进行查找其复杂度也为 O(1)，因此其非常适合作为栈的实现，详见栈那篇文章的链表相关内容。

附完整代码

package LinkedList;

/**
 * @author Boli Tao
 */
public class LinkedList<E> {
    private class Node {
        public E e;
        public Node next;

        public Node() {
            this(null, null);
        }

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        public Node(E e) {
            this(e, null);
        }

        @Override
        public String toString() {
            return e.toString();
        }
    }

    private Node dummyNode;
    private int size;

    public LinkedList() {
        dummyNode = new Node();
        size = 0;
    }

    public int getSize() {
        return size;
    }

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

    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IllegalArgumentException("add() filed, illegal index.");
        }
        Node prev = dummyNode;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        prev.next = new Node(e, prev.next);
        size++;
    }

    public void addFirst(E e) {
        add(0, e);
    }

    public void addLast(E e) {
        add(size, e);
    }

    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Illegal argument");
        }
        Node current = dummyNode.next;
        for (int i = 0; i < index; i++) {
            current = current.next;
        }
        return current.e;
    }

    public E getFirst() {
        return get(0);
    }

    public E getLast() {
        return get(size - 1);
    }

    public void update(int index, E e) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Illegal argument");
        }
        Node node = dummyNode.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        node.e = e;
    }

    public boolean contains(E e) {
        Node current = dummyNode.next;
        while (current != null) {
            if (current.e.equals(e)) {
                return true;
            }
            current = current.next;
        }
        return false;
    }

    public E delete(int index) {
        if (index < 0 || index >= size) {
            throw new IllegalArgumentException("Illegal argument");
        }
        Node prev = dummyNode;
        for (int i = 0; i < index; i++) {
            prev = prev.next;
        }
        Node deletedNode = prev.next;
        E deletedData = deletedNode.e;
        prev.next = deletedNode.next;
        size--;
        // deletedNode = null;
        deletedNode.next = null;
        return deletedData;
    }

    public E removeFirst() {
        return delete(0);
    }

    public E removeLast() {
        return delete(size - 1);
    }

    public void removeElement(E e) {
        Node prev = dummyNode;
        while (prev.next != null) {
            if (prev.next.e.equals(e)) {
                break;
            }
            prev = prev.next;
        }
        if (prev.next != null) {
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
        }
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder();
        // current != null 而不是 current.next != null
        for (Node current = dummyNode.next; current != null; current = current.next) {
            stringBuilder.append(current + "->");
        }
        stringBuilder.append("NULL");
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<Integer>();
        for (int i = 0; i < 5; i++) {
            linkedList.addFirst(i);
            System.out.println(linkedList);
        }
        linkedList.add(2, 666);
        System.out.println(linkedList);
        linkedList.add(0, 0);
        System.out.println(linkedList);
        linkedList.addFirst(0);
        System.out.println(linkedList);
        linkedList.addLast(0);
        System.out.println(linkedList);
        linkedList.removeFirst();
        System.out.println(linkedList);
        linkedList.removeLast();
        System.out.println(linkedList);
        linkedList.delete(3);
        System.out.println(linkedList);
    }
}

二分搜索树

重要性质

用不那么严谨且好理解的话来说，就是左孩子小于父节点右孩子大于父节点。

向二分搜索树中添加元素

如果比父节点小则向左深入，如果大则向右深入，对相等节点不做操作（即二分搜索树中不包含重复元素），直到深入的下一个节点为空为止，此时将空节点替换为待插入节点。

比如，向 BST 中插入元素 52：

递归代码：

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

判断树中是否含有某个值（可用于查找算法）

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

遍历

广度优先遍历（层序遍历）

层序遍历通常使用队列帮助实现：

public void levelOrder() {
    Queue<Node> queue = new LinkedList<>();
    queue.add(root);
    while (!queue.isEmpty()) {
        Node current = queue.remove();
        System.out.println(current.e);
        if (current.left != null) {
            queue.add(current.left);
        }
        if (current.right != null) {
            queue.add(current.right);
        }
    }
}

深度优先遍历

前序遍历

先访问节点，再访问其左右孩子。

非递归的前序遍历通常借助栈来实现，注意左右孩子的入栈顺序：先入右孩子再入左孩子，这样出栈时才能保证顺序为“父-左-右”。

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

递归：

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

中序遍历

遍历顺序为左-中-右。

中序遍历的一个特性是其输出按大小排列。

示意图：

递归代码实现：

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

后序遍历

递归代码：

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

取得 BST 中的最小值

由二分搜索树的定义一直往左取就能得到最小值：

private Node minimum(Node node) {
    if (node.left == null) {
        return node;
    }
    return minimum(node.left);
}

取得 BST 中的最大值

private Node maximum(Node node) {
    if (node.right == null) {
        return node;
    }
    return maximum(node.right);
}

删除 BST 中的最小元素

private Node removeMin(Node node) {
    if (node.left == null) {
        Node rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
    }
    node.left = removeMin(node.left);
    return node;
}

删除 BST 中的最大元素

private Node removeMax(Node node) {
    if (node.right == null) {
        Node leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
    }
    node.right = removeMax(node.right);
    return node;
}

删除 BST 中某个给定值的元素

递归找到待删除节点
判断三种情形：
1. 如果待删除节点左子树为空：图中 58 为待删除元素，此时将 58 的右孩子直接返回。
2. 如果待删除结点右子树为空：直接返回左孩子即可。
3. 如果待删除结点左右子树都不为空：待删除节点为 D，此时需要找到 D 右子树的最小节点 S，将 S 替代 D。此外，寻找比 D 小的最大值来顶替 D 也是可行的（即 D 的左子树中的最大节点 53）。

/**
 * 删除以 node 为根的值为 e 的节点
 *
 * @param node 根节点
 * @param e    待删除节点的值
 * @return 删除之后的根节点
 */
private Node remove(Node node, E e) {
    if (node == null) {
        return null;
    }
    if (e.compareTo(node.e) < 0) {
        node.left = remove(node.left, e);
        return node;
    }
    if (e.compareTo(node.e) > 0) {
        node.right = remove(node.right, e);
        return node;
    } else { // e equals node.e
        // 待删除结点左子树为空的情况
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        // 待删除结点右子树为空的情况
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        /*
        待删除节点左右节点都不为空的情况：
        找到比待删除结点大的最小节点 a（即右子树的最小节点），用这个节点 a 顶替待删除结点
        注意 size 的变化情况
        另外：找待删除结点左子树的最大值作为顶替节点 a 也是可以的
        */
        Node successor = minimum(node.right);
        successor.right = removeMin(node.right);
        size++;
        successor.left = node.left;
        node.left = node.right = null;
        size--;
        return successor;
    }
}

BST 的性能

在二分搜索树性能取决于树的形状，在平衡状态下，性能为 O(logn)。在最坏情况下 BST 退化为链表，性能为 O(n)。

附 BST 完整代码

package BST;

import java.util.*;

/**
 * 二分搜索树，不包含重复元素
 *
 * @author Boli Tao
 */
public class BST<E extends Comparable<E>> {
    private class Node {
        E e;
        Node left, right;

        public E getE() {
            return e;
        }

        Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }


        public void setE(E e) {
            this.e = e;
        }

        public Node getLeft() {
            return left;
        }

        public void setLeft(Node left) {
            this.left = left;
        }

        public Node getRight() {
            return right;
        }

        public void setRight(Node right) {
            this.right = right;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size = 0;
    }

    public int getSize() {
        return size;
    }

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

    public void add(E e) {
        root = add(root, e);
    }

    /**
     * 向二叉树中插入节点，忽略重复元素
     *
     * @param root 根节点（也包含子树的根节点）
     * @param e    需要插入的元素
     * @return 插入新节点后二叉树的根
     */
    private Node add(Node root, E e) {
        if (root == null) {
            size++;
            return new Node(e);
        }
        if (e.compareTo(root.e) < 0) {
            root.left = add(root.left, e);
        } else if (e.compareTo(root.e) > 0) {
            root.right = add(root.right, e);
        }
        return root;
    }

    public boolean contains(E e) {
        return contains(root, e);
    }

    /**
     * 判断以 root 为根的树是否含有值 e
     *
     * @param root 树的根
     * @param e    需要查询的值
     * @return 是否找到
     */
    private boolean contains(Node root, E e) {
        if (root == null) {
            return false;
        }
        if (e.compareTo(root.e) == 0) {
            return true;
        } else if (e.compareTo(root.e) < 0) {
            return contains(root.left, e);
        } else {
            return contains(root.right, e);
        }
    }

    /**
     * 非递归的前序遍历
     */
    public void preOrderNR() {
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node current = stack.pop();
            System.out.println(current.e);
            if (current.right != null) {
                stack.push(current.right);
            }
            if (current.left != null) {
                stack.push(current.left);
            }
        }
    }

    /**
     * 二分搜索树的前序遍历
     */
    public void preOrder() {
        preOrder(root);
    }

    /**
     * 前序遍历以 root 为根的二分搜索树
     *
     * @param root 树根
     */
    private void preOrder(Node root) {
        if (root == null) {
            return;
        }
        System.out.println(root.e);
        preOrder(root.left);
        preOrder(root.right);
    }

    public void inOrder() {
        inOrder(root);
    }

    /**
     * 中序遍历以 root 为根的二叉搜索树
     * 重要特性：二分搜索树的中序遍历输出是按大小顺序排列的
     *
     * @param root 根节点
     */
    private void inOrder(Node root) {
        if (root == null) {
            return;
        }
        inOrder(root.left);
        System.out.println(root.e);
        inOrder(root.right);
    }

    public void postOrder() {
        postOrder(root);
    }

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

    @Override
    public String toString() {
        StringBuilder result = new StringBuilder();
        generateBSTString(root, 0, result);
        return result.toString();
    }

    private void generateBSTString(Node root, int depth, StringBuilder stringBuilder) {
        if (root == null) {
            stringBuilder.append(generateDepthString(depth)).append("null\n");
            return;
        }
        stringBuilder.append(generateDepthString(depth)).append(root.e).append("\n");
        generateBSTString(root.left, depth + 1, stringBuilder);
        generateBSTString(root.right, depth + 1, stringBuilder);
    }

    private String generateDepthString(int depth) {
        StringBuilder builder = new StringBuilder();
//        for (int i = 0; i < depth; i++) {
//            builder.append("Depth: ").append(depth).append(", ");
//        }
        builder.append("Depth: ").append(depth).append(", ");
        return builder.toString();
    }

    /**
     * 层序遍历/ 广度优先遍历
     */
    public void levelOrder() {
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node current = queue.remove();
            System.out.println(current.e);
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
    }

    public E getMin() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty.");
        }
        return minimum(root).e;
    }

    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }
        return minimum(node.left);
    }

    public E getMax() {
        if (size == 0) {
            throw new IllegalArgumentException("BST is empty.");
        }
        return maximum(root).e;
    }

    private Node maximum(Node node) {
        if (node.right == null) {
            return node;
        }
        return maximum(node.right);
    }

    public E removeMin() {
        E ret = getMin();
        root = removeMin(root);
        return ret;
    }

    /**
     * 删除以 node 为根的最小节点
     *
     * @param node 根节点
     * @return 删除元素后新的二分搜索树的根
     */
    private Node removeMin(Node node) {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    public E removeMax() {
        E ret = getMax();
        root = removeMax(root);
        return ret;
    }

    private Node removeMax(Node node) {
        if (node.right == null) {
            Node leftNode = node.left;
            node.left = null;
            size--;
            return leftNode;
        }
        node.right = removeMax(node.right);
        return node;
    }

    public void remove(E e) {
        root = remove(root, e);
    }

    /**
     * 删除以 node 为根的值为 e 的节点
     *
     * @param node 根节点
     * @param e    待删除节点的值
     * @return 删除之后的根节点
     */
    private Node remove(Node node, E e) {
        if (node == null) {
            return null;
        }
        if (e.compareTo(node.e) < 0) {
            node.left = remove(node.left, e);
            return node;
        }
        if (e.compareTo(node.e) > 0) {
            node.right = remove(node.right, e);
            return node;
        } else { // e equals node.e
            // 待删除结点左子树为空的情况
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            // 待删除结点右子树为空的情况
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            /*
            待删除节点左右节点都不为空的情况：
            找到比待删除结点大的最小节点 a（即右子树的最小节点），用这个节点 a 顶替待删除结点
            注意 size 的变化情况
            另外：找待删除结点左子树的最大值作为顶替节点 a 也是可以的
            */
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            size++;
            successor.left = node.left;
            node.left = node.right = null;
            size--;
            return successor;
        }
    }
}

集合和映射

集合

接口

package set;

/**
 * @author 陶波利
 */
public interface Set<E> {
    void add(E e);

    void remove(E e);

    boolean contains(E e);

    int getSize();

    boolean isEmpty();
}

基于二分搜索树实现的集合

package set;

import BST.BST;
import tool.FileOperation;

import java.util.ArrayList;

/**
 * 二分搜索树实现的集合
 *
 * @author 陶波利
 */
public class BinarySearchTreeSet<E extends Comparable<E>> implements Set<E> {
    private BST bst;

    public BinarySearchTreeSet() {
        bst = new BST();
    }

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

    @Override
    public void remove(E e) {
        bst.remove(e);
    }

    @Override
    public boolean contains(E e) {
        return bst.contains(e);
    }

    @Override
    public int getSize() {
        return bst.getSize();
    }

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

基于链表实现的集合

package set;

import LinkedList.LinkedList;

/**
 * 链表实现的集合
 *
 * @author 陶波利
 */
public class LinkedListSet<E> implements Set<E> {
    private LinkedList linkedList;

    public LinkedListSet() {
        linkedList = new LinkedList();
    }

    @Override
    public void add(E e) {
        if (!linkedList.contains(e)) {
            // 在链表头插入元素时间复杂度更小
            linkedList.addFirst(e);
        }
    }

    @Override
    public void remove(E e) {
        linkedList.removeElement(e);
    }

    @Override
    public boolean contains(E e) {
        return linkedList.contains(e);
    }

    @Override
    public int getSize() {
        return linkedList.getSize();
    }

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

集合的复杂度分析

映射

链表实现的映射

package map;

/**
 * 链表实现的映射
 *
 * @author 陶波利
 */
public class LinkedListMap<K, V> implements Map<K, V> {
    private class Node {
        public K key;
        public V value;
        public Node next;

        public Node(K key, V value, Node next) {
            this.key = key;
            this.value = value;
            this.next = next;
        }

        public Node(K key) {
            this(key, null, null);
        }

        public Node() {
            this(null, null, null);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "key=" + key +
                    ", value=" + value +
                    ", next=" + next +
                    '}';
        }
    }

    private Node dummyHead;
    private int size;

    public LinkedListMap() {
        dummyHead = new Node();
        size = 0;
    }

    private Node getNode(K key) {
        Node cur = dummyHead.next;
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur;
            }
            cur = cur.next;
        }
        return null;
    }

    /**
     * 添加元素
     * 如果 key 重复，则进行更新
     *
     * @param key   key
     * @param value value
     */
    @Override
    public void add(K key, V value) {
        Node node = getNode(key);
        if (node == null) {
            dummyHead.next = new Node(key, value, dummyHead.next);
            size++;
        } else {
            node.value = value;
        }
    }

    @Override
    public V remove(K key) {
        Node prev = dummyHead;
        while (prev.next != null) {
            if (prev.next.key.equals(key)) {
                break;
            }
            prev = prev.next;
        }
        if (prev.next != null) {
            Node delNode = prev.next;
            prev.next = delNode.next;
            delNode.next = null;
            size--;
            return delNode.value;
        }
        return null;
    }

    @Override
    public boolean contains(K key) {
        return !(getNode(key) == null);
    }

    @Override
    public V get(K key) {
        Node node = getNode(key);
        return node == null ? null : node.value;
    }

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(key);
        if (node == null) {
            new IllegalArgumentException(key + " doesn't exist.");
        } else {
            node.value = newValue;
        }
    }

    @Override
    public int getSize() {
        return size;
    }

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

BST 实现的映射

package map;

/**
 * 二分搜索树实现的映射
 *
 * @author 陶波利
 */
public class BinarySearchTreeMap<K extends Comparable<K>, V> implements Map<K, V> {
    private class Node {
        public K key;
        public V value;
        public Node left, right;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            left = null;
            right = null;
        }
    }

    private Node root;
    private int size;

    public BinarySearchTreeMap() {
        root = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

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

    @Override
    public void add(K key, V value) {
        root = add(root, key, value);
    }

    private Node add(Node node, K key, V value) {
        if (node == null) {
            size++;
            return new Node(key, value);
        }
        if (key.compareTo(node.key) < 0) {
            node.left = add(node.left, key, value);
        } else if (key.compareTo(node.key) > 0) {
            node.right = add(node.right, key, value);
        } else {
            // map 中已存在需插入的 key 情况：更新 value 的值
            node.value = value;
        }
        return node;
    }

    /**
     * 返回以 node 为根的二分搜索树中 key 所在的节点
     *
     * @param node 根节点
     * @param key  key
     * @return 根节点
     */
    private Node getNode(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.key) == 0) {
            return node;
        } else if (key.compareTo(node.key) < 0) {
            return getNode(node.left, key);
        } else {
            return getNode(node.right, key);
        }
    }

    @Override
    public boolean contains(K key) {
        return !(getNode(root, key) == null);
    }

    @Override
    public V get(K key) {
        Node node = getNode(root, key);
        return node == null ? null : node.value;
    }

    @Override
    public void set(K key, V newValue) {
        Node node = getNode(root, key);
        if (node == null) {
            throw new IllegalArgumentException(key + " doesn't exist.");
        } else {
            node.value = newValue;
        }
    }

    @Override
    public V remove(K key) {
        Node node = getNode(root, key);
        if (node != null) {
            root = remove(root, key);
            return node.value;
        }
        return null;
    }

    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }
        return minimum(node.left);
    }

    private Node removeMin(Node node) {
        if (node.left == null) {
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;
        }
        node.left = removeMin(node.left);
        return node;
    }

    private Node remove(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.key) < 0) {
            node.left = remove(node.left, key);
            return node;
        } else if (key.compareTo(node.key) > 0) {
            node.right = remove(node.right, key);
            return node;
        } else {
            if (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;
        }
    }
}

堆

堆的表示方式

二叉堆实质是一个完全二叉树，定义最大堆为父节点总是大于其子节点。

二叉堆可以使用数组存储，如图：

其父节点与子节点的关系：

parent(i) = (i -1) / 2
lChild(i) = i * 2  + 1
rChild(i) = i * 2 + 2

堆的父子节点关系

上一节有做说明和伪代码，这里直接贴 Java 代码：

private int parent(int index) {
    if (index == 0) {
        throw new IllegalArgumentException("index 0 doesn't have parent.");
    }
    return (index - 1) / 2;
}

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

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

上浮堆中元素

在向堆中添入元素后，为了满足堆的性质可能要将元素上浮。比如：

向堆中添加 52，为了满足堆的性质需要将 52 上浮到索引为 1 的位置。上浮操作是：拿 52 与其父节点进行比较，如果大于其父节点则进行交换，直到元素达到合适位置。

相应代码：

/**
 * 为满足最大堆性质而设计的元素上浮方法
 *
 * @param k 需要被上浮的元素索引
 */
private void siftUp(int k) {
    while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
        data.swap(k, parent(k));
        k = parent(k);
    }
}

向堆中添加元素

上一节已经实现过元素的上浮，所以添加操作顺理成章变得很简单，只需要把元素添加到数组末尾，然后调用上浮函数。

public void add(E e) {
    data.addLast(e);
    siftUp(data.getSize() - 1);
}

得到堆中最大值

直接 get(0) 即可。

下沉堆中元素

有时堆中可能出现某元素破坏堆性质，可能需要对该元素进行下沉操作，比如：

此时需要下沉 16 以维持堆的性质。下沉思路如下：

将元素与子节点比较，与子结点中比自己大且是最大的元素交换位置，比如上图中索引 0 和索引 1 要交换位置
交换位置后继续进行比较，直到自己比所有子节点大或者成为叶子

/**
 * 为满足最大堆性质而设计的元素下沉方法
 *
 * @param k 需要被下沉的元素索引
 */
private void siftDown(int k) {
    while (leftChild(k) < data.getSize()) {
        int j = leftChild(k);
        if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
            j = rightChild(k);
        }
        // ↑此时 j 表示孩子节点中更大元素的索引
        if (data.get(k).compareTo(data.get(j)) > 0) {
            break;
        }
        data.swap(k, j);
        k = j;
    }
}

取出堆中最大元素(extractMax)

public E extractMax() {
    E ret = getMax();
    data.swap(0, data.getSize() - 1);
    data.removeLast();
    siftDown(0);
    return ret;
}

heapify、replace

heapify 使用构造函数实现：传入一个数组时，通过下沉将数组变成一个最大堆。

public MaxHeap(E[] arr) {
    data = new Array<>(arr);
    for (int i = parent(arr.length - 1); i >= 0; i--) {
        siftDown(i);
    }
}

在某些情况下需要将某元素替换掉堆顶元素，可以写一个 replace() 方法：

public E replace(E e) {
    E ret = getMax();
    data.set(0, e);
    siftDown(0);
    return ret;
}

堆的应用

优先队列，可以看本人队列相关的博客文章。

代码

package heap;

import array.Array;

import java.util.Random;

/**
 * @author 陶波利
 */
public class MaxHeap<E extends Comparable<E>> {
    private Array<E> data;

    public MaxHeap(int capacity) {
        data = new Array<>(capacity);
    }

    public MaxHeap() {
        data = new Array<>();
    }

    /**
     * 构造函数：将传入数组组成为最大堆
     *
     * @param arr 待化为最大堆的数组
     */
    public MaxHeap(E[] arr) {
        data = new Array<>(arr);
        for (int i = parent(arr.length - 1); i >= 0; i--) {
            siftDown(i);
        }
    }

    public int size() {
        return data.getSize();
    }

    public boolean isEmpty() {
        return data.isEmpty();
    }

    /**
     * @param index index
     * @return index 的父节点的索引
     */
    private int parent(int index) {
        if (index == 0) {
            throw new IllegalArgumentException("index 0 doesn't have parent.");
        }
        return (index - 1) / 2;
    }

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

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

    /**
     * 向堆中添加元素
     *
     * @param e 待添加的元素值
     */
    public void add(E e) {
        data.addLast(e);
        siftUp(data.getSize() - 1);
    }

    /**
     * 为满足最大堆性质而设计的元素上浮方法
     *
     * @param k 需要被上浮的元素索引
     */
    private void siftUp(int k) {
        while (k > 0 && data.get(parent(k)).compareTo(data.get(k)) < 0) {
            data.swap(k, parent(k));
            k = parent(k);
        }
    }

    /**
     * 取出堆中最大元素
     *
     * @return max value
     */
    public E extractMax() {
        E ret = getMax();
        data.swap(0, data.getSize() - 1);
        data.removeLast();
        siftDown(0);
        return ret;
    }

    public E getMax() {
        if (data.getSize() == 0) {
            throw new IllegalArgumentException("Size is 0, no element in heap.");
        }
        return data.get(0);
    }

    /**
     * 为满足最大堆性质而设计的元素下沉方法
     *
     * @param k 需要被下沉的元素索引
     */
    private void siftDown(int k) {
        while (leftChild(k) < data.getSize()) {
            int j = leftChild(k);
            if (j + 1 < data.getSize() && data.get(j + 1).compareTo(data.get(j)) > 0) {
                j = rightChild(k);
            }
            // ↑此时 j 表示孩子节点中更大元素的索引
            if (data.get(k).compareTo(data.get(j)) > 0) {
                break;
            }
            data.swap(k, j);
            k = j;
        }
    }

    public E replace(E e) {
        E ret = getMax();
        data.set(0, e);
        siftDown(0);
        return ret;
    }

    /**
     * 测试类
     *
     * @param args args
     */
    public static void main(String[] args) {
        int n = 1000000;
        MaxHeap<Integer> maxHeap = new MaxHeap<>();
        Random random = new Random();
        for (int i = 0; i < n; i++) {
            maxHeap.add(random.nextInt(Integer.MAX_VALUE));
        }
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = maxHeap.extractMax();
        }
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] < arr[i]) {
                throw new IllegalArgumentException("Error: 最大堆实现出现问题！");
            }
        }
        System.out.println("Completed!");
    }
}

红黑树

Wikipedia 对 Red–black tree 的性质描述如下：

In addition to the requirements imposed on a binary search tree the following must be satisfied by a red–black tree:

Each node is either red or black.

The root is black. This rule is sometimes omitted. Since the root can always be changed from red to black, but not necessarily vice versa, this rule has little effect on analysis.

All leaves (NIL) are black.

If a node is red, then both its children are black.

Every path from a given node to any of its descendant NIL nodes contains the same number of black nodes.

嗯...很复杂，光是听描述就要自闭，为了更方便理解红黑树可以先了解 2-3 树。

2-3 树

2-3 树的除了满足二分搜索树的基本性质外还有一个性质：节点可以存放一个或两个元素。

比如以下节点：

满足 leftChild < b < midChild < c < rightChild。

此外 2-3 树还是一颗绝对平衡树：从根节点到任意叶子节点所经过的节点数量一定相同。

这一性质由其 add 方式决定：2-3 树添加节点时永远不会添加到空的位置（有别于二分搜索树），而是和最后找到的叶子节点融合，如果节点数大于三，则进行分裂。

2-3 树转化为红黑树

对一个 2-3 树中的三节点，将其转化为二叉树，并且定义左侧/较小的值为子节点，规定所有红色节点为左倾，转化为红黑树中的节点则为：

e.g.

以上 2-3 树的红黑树形式为：

红黑树的定义

根是黑色

2-3 树等价的两种红黑树如下：

2 节点：

3 节点：

可见根节点总会是黑色。

所有叶子都是黑色（叶子是NIL节点）

可以看做一条定义，最后的空节点是黑色。比如空树这种特殊情况。

每个红色节点必须有两个黑色的子节点

红色节点的子节点在 2-3 树中为一个三节点的 lChild 或 mChild，lChild 和 mChild 只可能为二节点或三节点。

如果是二节点则直接对应红黑树中的黑色节点。

如果是三节点，其转化成红黑树的样式之后子树根节点仍为黑色（红黑树的性质）。

此外还有一相似性质：黑色节点的右孩子一定是黑色。

哈希表

哈希函数

整型

小范围整数直接使用
小范围负整数进行偏移 -100 ~ 100 → 0 ~ 200

大整数：模一个素数

e.g.

以下情况哈希冲突很严重：

模素数的结果分布更均匀：

对不同整型规模取模时素数的参考：good hash table primes

浮点型

字符串

转为整形处理

由整形组成：

$$123 = 1 * 10^2 + 2 * 10^1 + 3 * 10^0$$

可以推出：

$$code = c * 26^3 + o * 26^2 + d * 26^1 + e * 26^0$$

对于更复杂的字符串（区分大小写、包含符号等）可以使用更大的进制。

所以哈希函数可以设置如下：

$$hash(code) = (c * B^3 + o * B^2 + d * B^1 + e * B^0) \bmod P$$

即：

$$hash(code) = ((((c * B) + o) * B + d) * B + e) \bmod P$$

为防止计算机运行时整形溢出，可以变形为：

$$hash(code) = ((((c \bmod P) * B + o) \bmod P * B + d) \bmod P * B + e) \bmod P$$

其中 B 为进制数，P 为对整数取模用的素数，Java 代码：

int hash = 0;
for (int i = 0; i < str.length(); i++) {
    hash = (hash * B + str.charAt(i)) % P;
}

复合类型

与字符串类似。

e.g.

对于数据类型 Date，有 year, month, day 三个属性，可以设置其哈希函数为：

$$ hash(date) = (((date.year \bmod P) * B + date.month) \bmod P * B + date.day) \bmod P $$

数据结构复习

相关文章：