数据结构：树进阶

2021-04-20 08:53 286人阅读评论(0)

项目地址：https://gitee.com/caochenlei/data-structures

第一章并查集

1.1、并查集的介绍

并查集（Union-Find Sets）是一种树型的数据结构，并查集可以高效地进行如下操作：

查询元素p和元素q是否属于同一组
合并元素p和元素q所在组为同一组

1.2、并查集的结构

并查集也是一种树型结构，但这棵树跟我们之前讲的二叉树、红黑树等都不一样，这种树的要求比较简单：

每个元素都唯一的对应一个结点；
每一组数据中的多个元素都在同一颗树中；
一个组中的数据对应的树和另外一个组中的数据对应的树之间没有任何联系；
元素在树中并没有子父级关系的硬性要求；

1.3、并查集的实现1

实现思想：

关于初始化：

初始情况下，每个元素都在一个独立的分组中，所以，初始情况下，并查集中的数据默认分为N个组；
初始化数组eleAndGroup；
把eleAndGroup数组的索引看做是每个结点存储的元素，把eleAndGroup数组每个索引处的值看做是该结点
所在的分组，那么初始化情况下，i索引处存储的值就是i；

关于结点查找：

直接返回该元素所在组的标识 eleAndGroup[p]；

关于合并分组：

如果p和q已经在同一个分组中，则无需合并；
如果p和q不在同一个分组，则只需要将p元素所在组的所有的元素的组标识符修改为q元素所在组的标识符；
分组数量-1；

实现代码：

public class UnionFindSets {
   
    private int[] eleAndGroup;      //记录结点元素及分组的标识符
    private int count;              //记录并查集中数据的分组个数

    public UnionFindSets(int N) {
   
        this.count = N;
        this.eleAndGroup = new int[N];
        for (int i = 0; i < eleAndGroup.length; i++) {
   
            eleAndGroup[i] = i;
        }
    }

    //获取并查集中有多少分组
    public int count() {
   
        return count;
    }

    //元素p所在分组的标识符
    public int find(int p) {
   
        return eleAndGroup[p];
    }

    //查询元素p和元素q是否属于同一组
    public boolean connected(int p, int q) {
   
        return find(p) == find(q);
    }

    //合并元素p和元素q所在组为同一组
    public void union(int p, int q) {
   
        if (connected(p, q)) {
   
            return;
        }
        int pGroup = find(p);
        int qGroup = find(q);
        for (int i = 0; i < eleAndGroup.length; i++) {
   
            if (eleAndGroup[i] == pGroup) {
   
                eleAndGroup[i] = qGroup;
            }
        }
        this.count--;
    }
}

测试代码：

public class UnionFindSetsTest {
   
    public static void main(String[] args) {
   
        UnionFindSets ufs = new UnionFindSets(4);
        System.out.println("初始化并查集中有：" + ufs.count() + "个分组");
        Scanner sc = new Scanner(System.in);
        while (true) {
   
            System.out.print("请输入第一个要合并的元素：");
            int p = sc.nextInt();
            System.out.print("请输入第二个要合并的元素：");
            int q = sc.nextInt();
            if (ufs.connected(p, q)) {
   
                System.out.println(p + "元素和" + q + "元素已经在同一个组中了");
                continue;
            } else {
   
                ufs.union(p, q);
                System.out.println("当前并查集中还有：" + ufs.count() + "个分组");
            }
        }
    }
}

初始化并查集中有：4个分组
请输入第一个要合并的元素：0
请输入第二个要合并的元素：1
当前并查集中还有：3个分组
请输入第一个要合并的元素：1
请输入第二个要合并的元素：2
当前并查集中还有：2个分组
请输入第一个要合并的元素：2
请输入第二个要合并的元素：3
当前并查集中还有：1个分组
请输入第一个要合并的元素：0
请输入第二个要合并的元素：1
0元素和1元素已经在同一个组中了
请输入第一个要合并的元素：1
请输入第二个要合并的元素：2
1元素和2元素已经在同一个组中了
请输入第一个要合并的元素：2
请输入第二个要合并的元素：3
2元素和3元素已经在同一个组中了

1.4、并查集的实现2

实现思想：

关于初始化：

如果我们并查集存储的每一个整数表示的是一个大型计算机网络中的计算机，则我们就可以通过connected(int p,int q)来检测，该网络中的某两台计算机之间是否连通？如果连通，则他们之间可以通信，如果不连通，则不能通信，此时我们又可以调用union(int p,int q)使得p和q之间连通，这样两台计算机之间就可以通信了。

一般像计算机这样网络型的数据，我们要求网络中的每两个数据之间都是相连通的，也就是说，我们需要调用很多次union方法，使得网络中所有数据相连，其实我们很容易可以得出，如果要让网络中的数据都相连，则我们至少要调用N-1次union方法才可以，但由于我们的union方法中使用for循环遍历了所有的元素，所以很明显，我们之前实现的合并算法的时间复杂度是O(N²)，如果要解决大规模问题，他是不合适的，所以我们需要对算法进行优化。

为了提升union算法的性能，我们需要重新设计find方法和union方法的实现，此时我们先需要对我们的之前数据结构中的eleAndGourp数组的含义进行重新设定：

我们仍然让eleAndGroup数组的索引作为某个结点的元素；
eleAndGroup[i]的值不再是当前结点所在的分组标识，而是该结点的父结点；

关于结点查找：

判断当前元素p的父结点eleAndGroup[p]是不是自己，如果是自己则证明已经是根结点了；
如果当前元素p的父结点不是自己，则让p=eleAndGroup[p]，继续找父结点的父结点，直到找到根结点为止；

关于合并分组：

找到p元素所在树的根结点；
找到q元素所在树的根结点；
如果p和q已经在同一个树中，则无需合并；
如果p和q不在同一个分组中，则只需要将p元素所在树根结点的父结点设置为q元素的根结点即可；
分组数量-1；

实现代码：

public class UnionFindSets {
   
    private int[] eleAndGroup;      //记录结点元素及分组的标识符
    private int count;              //记录并查集中数据的分组个数

    public UnionFindSets(int N) {
   
        this.count = N;
        this.eleAndGroup = new int[N];
        for (int i = 0; i < eleAndGroup.length; i++) {
   
            eleAndGroup[i] = i;
        }
    }

    //获取并查集中有多少分组
    public int count() {
   
        return count;
    }

    //元素p所在分组的标识符
    public int find(int p) {
   
        while (true) {
   
            if (p == eleAndGroup[p]) {
   
                return p;
            }
            p = eleAndGroup[p];
        }
    }

    //查询元素p和元素q是否属于同一组
    public boolean connected(int p, int q) {
   
        return find(p) == find(q);
    }

    //合并元素p和元素q所在组为同一组
    public void union(int p, int q) {
   
        //找到p元素和q元素所在组对应的树的根结点
        int pRoot = find(p);
        int qRoot = find(q);
        //如果p和q已经在同一分组，则不需要合并了
        if (pRoot == qRoot) {
   
            return;
        }
        //p所在树根结点的父结点为q所在树的根结点
        eleAndGroup[pRoot] = qRoot;
        //组的数量-1
        this.count--;
    }
}

测试代码：

public class UnionFindSetsTest {
   
    public static void main(String[] args) {
   
        UnionFindSets ufs = new UnionFindSets(4);
        System.out.println("初始化并查集中有：" + ufs.count() + "个分组");
        Scanner sc = new Scanner(System.in);
        while (true) {
   
            System.out.print("请输入第一个要合并的元素：");
            int p = sc.nextInt();
            System.out.print("请输入第二个要合并的元素：");
            int q = sc.nextInt();
            if (ufs.connected(p, q)) {
   
                System.out.println(p + "元素和" + q + "元素已经在同一个组中了");
                continue;
            } else {
   
                ufs.union(p, q);
                System.out.println("当前并查集中还有：" + ufs.count() + "个分组");
            }
        }
    }
}

初始化并查集中有：4个分组
请输入第一个要合并的元素：0
请输入第二个要合并的元素：1
当前并查集中还有：3个分组
请输入第一个要合并的元素：1
请输入第二个要合并的元素：2
当前并查集中还有：2个分组
请输入第一个要合并的元素：2
请输入第二个要合并的元素：3
当前并查集中还有：1个分组
请输入第一个要合并的元素：0
请输入第二个要合并的元素：1
0元素和1元素已经在同一个组中了
请输入第一个要合并的元素：1
请输入第二个要合并的元素：2
1元素和2元素已经在同一个组中了
请输入第一个要合并的元素：2
请输入第二个要合并的元素：3
2元素和3元素已经在同一个组中了

1.5、并查集的实现3

实现思想：

我们优化后的算法union，如果要把并查集中所有的数据连通，仍然至少要调用N-1次union方法，但是，我们发现union方法中已经没有了for循环，所以union算法的时间复杂度由O(N²)变为了O(N)。但是这个算法仍然有问题，因为我们之前不仅修改了union算法，还修改了find算法。我们修改前的find算法的时间复杂度在任何情况下都为O(1)，但修改后的find算法在最坏情况下是O(N)：

在union方法中调用了find方法，所以在最坏情况下union算法的时间复杂度仍然为O(N²)。其最主要的问题在于最坏情况下，树的深度和数组的大小一样，如果我们能够通过一些算法让合并时，生成的树的深度尽可能的小，就可以优化find方法。之前我们在union算法中，合并树的时候将任意的一棵树连接到了另外一棵树，这种合并方法是比较暴力的，如果我们把并查集中每一棵树的大小记录下来，然后在每次合并树的时候，把较小的树连接到较大的树上，就可以减小树的深度。

只要我们保证每次合并，都能把小树合并到大树上，就能够压缩合并后新树的路径，这样就能提高find方法的效率。为了完成这个需求，我们需要另外一个数组来记录存储每个根结点对应的树中元素的个数，并且需要一些代码调整数组中的值。

实现代码：

public class UnionFindSets {
   
    private int[] eleAndGroup;
    private int count;
    private int[] eleAndCount;

    public UnionFindSets(int N) {
   
        this.count = N;
        this.eleAndGroup = new int[N];
        for (int i = 0; i < eleAndGroup.length; i++) {
   
            eleAndGroup[i] = i;
        }
        this.eleAndCount = new int[N];
        for (int i = 0; i < eleAndCount.length; i++) {
   
            eleAndCount[i] = 1;
        }
    }

    //获取并查集中有多少分组
    public int count() {
   
        return count;
    }

    //元素p所在分组的标识符
    public int find(int p) {
   
        while (true) {
   
            if (p == eleAndGroup[p]) {
   
                return p;
            }
            p = eleAndGroup[p];
        }
    }

    //查询元素p和元素q是否属于同一组
    public boolean connected(int p, int q) {
   
        return find(p) == find(q);
    }

    public void union(int p, int q) {
   
        //找到p元素和q元素所在组对应的树的根结点
        int pRoot = find(p);
        int qRoot = find(q);
        //如果p和q已经在同一分组，则不需要合并了
        if (pRoot == qRoot) {
   
            return;
        }
        //如果p和q不在一组，只需要让小树并入大树
        if (eleAndCount[pRoot] < eleAndCount[qRoot]) {
   
            eleAndGroup[pRoot] = qRoot;
            eleAndCount[qRoot] += eleAndCount[pRoot];
        } else {
   
            eleAndGroup[qRoot] = pRoot;
            eleAndCount[pRoot] += eleAndCount[qRoot];
        }
        //组的数量-1
        this.count--;
    }
}

测试代码：

public class UnionFindSetsTest {
   
    public static void main(String[] args) {
   
        UnionFindSets ufs = new UnionFindSets(4);
        System.out.println("初始化并查集中有：" + ufs.count() + "个分组");
        Scanner sc = new Scanner(System.in);
        while (true) {
   
            System.out.print("请输入第一个要合并的元素：");
            int p = sc.nextInt();
            System.out.print("请输入第二个要合并的元素：");
            int q = sc.nextInt();
            if (ufs.connected(p, q)) {
   
                System.out.println(p + "元素和" + q + "元素已经在同一个组中了");
                continue;
            } else {
   
                ufs.union(p, q);
                System.out.println("当前并查集中还有：" + ufs.count() + "个分组");
            }
        }
    }
}

初始化并查集中有：4个分组
请输入第一个要合并的元素：0
请输入第二个要合并的元素：1
当前并查集中还有：3个分组
请输入第一个要合并的元素：1
请输入第二个要合并的元素：2
当前并查集中还有：2个分组
请输入第一个要合并的元素：2
请输入第二个要合并的元素：3
当前并查集中还有：1个分组
请输入第一个要合并的元素：0
请输入第二个要合并的元素：1
0元素和1元素已经在同一个组中了
请输入第一个要合并的元素：1
请输入第二个要合并的元素：2
1元素和2元素已经在同一个组中了
请输入第一个要合并的元素：2
请输入第二个要合并的元素：3
2元素和3元素已经在同一个组中了

第二章二叉堆

2.1、二叉堆的介绍

堆（Heap）也是一种树状的数据结构，他与内存模型中的“堆空间”并不是一个概念，常见的堆实现有：

二叉堆（Binary Heap，完全二叉堆）
多叉堆（D-heap、D-ary Heap）
索引堆（Index Heap）
二项堆（Binomial Heap）
斐波那契堆（Fibonacci Heap）
左倾堆（Leftist Heap）
斜堆（Skew Heap）

二叉堆的一个重要性质就是任意结点的值总是 ≥ （ ≤ ）子结点的值，常见的二叉堆有：

如果任意结点的值总是 ≥ 子结点的值，称为：最大堆、大根堆、大顶堆

如果任意结点的值总是 ≤ 子结点的值，称为：最小堆、小根堆、小顶堆

二叉堆的逻辑结构就是一棵完全二叉树，所以也叫完全二叉堆，鉴于完全二叉树的一些特性，二叉堆的底层（物理结构）一般用数组实现即可，n 是元素数量，则索引 i 的规律如下：

如果 i > 0 ，他的父结点的索引为 floor( (i – 1) / 2 )
如果 2i + 1 ≤ n – 1，他的左子结点的索引为 2i + 1
如果 2i + 1 > n – 1，他无左子结点
如果 2i + 2 ≤ n – 1，他的右子结点的索引为 2i + 2
如果 2i + 2 > n – 1，他无右子结点

2.2、二叉堆的结构

public class BinaryHeap<E> {
   
    private E[] elements;                               //存储堆中所有元素
    private int size;                                   //存储堆中元素个数
    private Comparator<E> comparator;                   //存储一个比较对象
    private static final int DEFAULT_CAPACITY = 16;     //存储默认容量大小

    public BinaryHeap(E[] elements, Comparator<E> comparator) {
   
        if (elements == null) {
   
            this.size = 0;
            this.elements = (E[]) new Object[DEFAULT_CAPACITY];
            this.comparator = comparator;
        }
    }

    public BinaryHeap(E[] elements) {
   
        this(elements, null);
    }

    public BinaryHeap(Comparator<E> comparator) {
   
        this(null, comparator);
    }

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

    //确保堆容量可用
    private void ensureCapacity(int capacity) {
   
        int oldCapacity = elements.length;
        if (oldCapacity >= capacity) return;
        int newCapacity = oldCapacity + (oldCapacity / 2);
        E[] newElements = (E[]) new Object[newCapacity];
        for (int i = 0; i < size; i++) {
   
            newElements[i] = elements[i];
        }
        elements = newElements;
    }

    //比较两元素大小
    private int compare(E e1, E e2) {
   
        return comparator != null ? comparator.compare(e1, e2) : ((Comparable<E>) e1).compareTo(e2);
    }

    //获取堆元素个数
    public int size() {
   
        return size;
    }

    //判断堆是否为空
    public boolean isEmpty() {
   
        return size == 0;
    }

    //清空堆所有元素
    public void clear() {
   
        //需循环释放引用
        for (int i = 0; i < size; i++) {
   
            elements[i] = null;
        }
        size = 0;
    }

    //获取堆顶的元素
    public E get() {
   
        //判断堆是否为空
        if (isEmpty()) {
   
            return null;
        }
        return elements[0];
    }

    @Override
    public String toString() {
   
        String s = "";
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < size; i++) {
   
            sb.append(elements[i] + ", ");
        }
        if (!isEmpty()) {
   
            s = sb.substring(0, sb.length() - 2);
        }
        return "BinaryHeap{elements=[" + s + "]}";
    }

    //以下方法写在这
}

2.3、最大堆的实现

添加操作

循环执行以下操作（图中的 80 简称为 node），这个过程叫做上滤（Sift Up），时间复杂度：O(logn)

如果 node > 父结点，与父结点交换位置；
如果 node ≤ 父结点，或者 node 没有父结点，退出循环；

//向堆中追加元素
public void add(E e) {
   
    //确保容量
    ensureCapacity(size + 1);
    //添加元素
    elements[size++] = e;
    //上滤操作
    siftUp(size - 1);
}

private void siftUp(int index) {
   
    while (index > 0) {
   
        int parentIndex = (index - 1) / 2;
        if (compare(elements[index], elements[parentIndex]) > 0) {
   
            E temp = elements[index];
            elements[index] = elements[parentIndex];
            elements[parentIndex] = temp;
        } else {
   
            break;
        }
        index = parentIndex;
    }
}

实际上，我们并不需要每一次都交换 node 和父结点，只需要找到最终 node 存放的位置，然后再把 node 的值放到最终位置去即可。

//向堆中追加元素
public void add(E e) {
   
    //确保容量
    ensureCapacity(size + 1);
    //添加元素
    elements[size++] = e;
    //上滤操作
    siftUp2(size - 1);
}

private void siftUp2(int index) {
   
    E node = elements[index];
    while (index > 0) {
   
        int parentIndex = (index - 1) / 2;
        if (compare(node, elements[parentIndex]) > 0) {
   
            elements[index] = elements[parentIndex];
            index = parentIndex;
        } else {
   
            break;
        }
    }
    elements[index] = node;
}

添加测试：

public class BinaryHeapTest {
   
    public static void main(String[] args) {
   
        BinaryHeap<Integer> bh = new BinaryHeap<>();

        bh.add(72);
        bh.add(68);
        bh.add(50);
        bh.add(43);
        bh.add(38);
        bh.add(47);
        bh.add(21);
        bh.add(14);
        bh.add(80);

        System.out.println(bh);
    }
}

BinaryHeap{
   elements=[80, 72, 50, 68, 38, 47, 21, 14, 43]}

删除操作

删除指的是删除根结点，用最后一个结点覆盖根结点，然后删除最后一个结点，再对新的根结点进行下滤操作。

循环执行以下操作（图中的 80 简称为 node），这个过程叫做下滤（Sift Down），时间复杂度：O(logn)

如果 node < 最大的子结点，与最大的子结点交换位置；
如果 node ≥ 最大的子结点，或者 node 没有子结点，退出循环；

//删除并返回堆顶
public E remove() {
   
    //判断堆是否为空
    if (isEmpty()) {
   
        return null;
    }
    //保存根结点元素
    E root = elements[0];
    //取最后元素索引
    int lastIndex = --size;
    //替换根结点元素
    elements[0] = elements[lastIndex];
    //删除最后的元素
    elements[lastIndex] = null;
    //下滤操作
    siftDown(0);
    //返回元素
    return root;
}

private void siftDown(int index) {
   
    //index < (size / 2)：此判断代表的都是非叶子结点，叶子结点是不需要进行下滤
    while (index < (size / 2)) {
   
        int leftChildIndex = (index * 2) + 1;   //当前结点的左子结点下标
        int rightChildIndex = (index * 2) + 2;  //当前结点的右子结点下标

        //找到左右子结点中最大的那个
        int childIndex = leftChildIndex;
        if (rightChildIndex<size && compare(elements[rightChildIndex], elements[leftChildIndex]) > 0) {
   
            childIndex = rightChildIndex;
        }

        //当前结点和最大子结点哪个大
        if (compare(elements[index], elements[childIndex]) < 0) {
   
            E temp = elements[index];
            elements[index] = elements[childIndex];
            elements[childIndex] = temp;
            index = childIndex;
        } else {
   
            break;
        }
    }
}

实际上，我们并不需要每一次都交换 node 和子结点，只需要找到最终 node 存放的位置，然后再把 node 的值放到最终位置去即可。

//删除并返回堆顶
public E remove() {
   
    //判断堆是否为空
    if (isEmpty()) {
   
        return null;
    }
    //保存根结点元素
    E root = elements[0];
    //取最后元素索引
    int lastIndex = --size;
    //替换根结点元素
    elements[0] = elements[lastIndex];
    //删除最后的元素
    elements[lastIndex] = null;
    //下滤操作
    siftDown2(0);
    //返回元素
    return root;
}

private void siftDown2(int index) {
   
    E node = elements[index];
    //index < (size / 2)：此判断代表的都是非叶子结点，叶子结点是不需要进行下滤
    while (index < (size / 2)) {
   
        int leftChildIndex = (index * 2) + 1;   //当前结点的左子结点下标
        int rightChildIndex = (index * 2) + 2;  //当前结点的右子结点下标

        //找到左右子结点中最大的那个
        int childIndex = leftChildIndex;
        if (rightChildIndex<size && compare(elements[rightChildIndex], elements[leftChildIndex]) > 0) {
   
            childIndex = rightChildIndex;
        }

        //当前结点和最大子结点哪个大
        if (compare(node, elements[childIndex]) < 0) {
   
            elements[index] = elements[childIndex];
            index = childIndex;
        } else {
   
            break;
        }
    }
    elements[index] = node;
}

删除测试：

public class BinaryHeapTest {
   
    public static void main(String[] args) {
   
        BinaryHeap<Integer> bh = new BinaryHeap<>();

        bh.add(72);
        bh.add(68);
        bh.add(50);
        bh.add(43);
        bh.add(38);
        bh.add(47);
        bh.add(21);
        bh.add(14);
        bh.add(80);

        System.out.println(bh);

        bh.remove();

        System.out.println(bh);
    }
}

BinaryHeap{
   elements=[80, 72, 50, 68, 38, 47, 21, 14, 43]}
BinaryHeap{
   elements=[72, 68, 50, 43, 38, 47, 21, 14]}

替换操作

//替换并返回堆顶
public E replace(E element) {
   
    E root = null;
    if (size == 0) {
   
        root = element;         //保存根结点元素
        elements[0] = element;  //替换根结点元素
        size++;                 //元素数量应加一
    } else {
   
        root = elements[0];     //保存根结点元素
        elements[0] = element;  //替换根结点元素
        siftDown(0);            //根结点需要下滤
    }
    return root;
}

替换测试：

public class BinaryHeapTest {
   
    public static void main(String[] args) {
   
        BinaryHeap<Integer> bh = new BinaryHeap<>();

        bh.add(72);
        bh.add(68);
        bh.add(50);
        bh.add(43);
        bh.add(38);
        bh.add(47);
        bh.add(21);
        bh.add(14);
        bh.add(80);

        System.out.println(bh);

        bh.replace(11);

        System.out.println(bh);
    }
}

BinaryHeap{
   elements=[80, 72, 50, 68, 38, 47, 21, 14, 43]}
BinaryHeap{
   elements=[72, 68, 50, 43, 38, 47, 21, 14, 11]}

2.4、最小堆的实现

public class BinaryHeapTest {
   
    public static void main(String[] args) {
   
        BinaryHeap<Integer> bh = new BinaryHeap<>(new Comparator<Integer>() {
   
            @Override
            public int compare(Integer o1, Integer o2) {
   
                return o2 - o1;
            }
        });

        bh.add(72);
        bh.add(68);
        bh.add(50);
        bh.add(43);
        bh.add(38);
        bh.add(47);
        bh.add(21);
        bh.add(14);
        bh.add(80);

        System.out.println(bh);
    }
}

BinaryHeap{
   elements=[14, 21, 38, 43, 50, 68, 47, 72, 80]}

2.5、批量建堆实现

第一步：修改 public BinaryHeap(E[] elements, Comparator<E> comparator)

public BinaryHeap(E[] elements, Comparator<E> comparator) {
   
    if (elements == null) {
   
        this.size = 0;
        this.elements = (E[]) new Object[DEFAULT_CAPACITY];
        this.comparator = comparator;
    } else {
   
        this.size = elements.length;
        this.elements = (E[]) new Object[Math.max(elements.length, DEFAULT_CAPACITY)];
        this.comparator = comparator;
        for (int i = 0; i < elements.length; i++) {
   
            this.elements[i] = elements[i];
        }
        heapify();
    }
}

第二步：堆化 private void heapify()

//堆化算法
private void heapify() {
   
    //第一种堆化算法：自上而下的上滤，时间复杂度大，不用
    //for (int i = 1; i < size; i++) {
   
    //    siftUp(i);
    //}

    //第二种堆化算法：自下而上的下滤，时间复杂度小，采取
    //i < (size / 2)：此判断代表的都是非叶子结点，叶子结点是不需要进行下滤
    for (int i = (size / 2) - 1; i >= 0; i--) {
   
        siftDown(i);
    }
}

第三步：测试

public class BinaryHeapTest {
   
    public static void main(String[] args) {
   
        Integer[] data = {
   72, 68, 50, 43, 38, 47, 21, 14, 80};
        BinaryHeap<Integer> bh = new BinaryHeap<>(data);
        System.out.println(bh);
    }
}

BinaryHeap{
   elements=[80, 72, 50, 68, 38, 47, 21, 14, 43]}

第三章最优二叉树

3.1、哈夫曼树的介绍

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

1、路径和路径长度

在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度

若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度

树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。下图中第二幅图就是一棵哈夫曼树。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

3.2、哈夫曼树的结构

给定一组结点，这组结点中每个结点都有自己的权重，这里以整型数组模拟结点集合：[13, 7, 8, 3, 29, 6, 1]

1、排序后[1, 3, 6, 7, 8, 13, 29]，取出第一小的结点1，取出第二小的结点3，构造一棵新结点并加入集合，删除无效结点

2、排序后[4, 6, 7, 8, 13, 29]，取出第一小的结点4，取出第二小的结点6，构造一棵新结点并加入集合，删除无效结点

3、排序后[7, 8, 10, 13, 29]，取出第一小的结点7，取出第二小的结点8，构造一棵新结点并加入集合，删除无效结点

4、排序后[10, 13, 15, 29]，取出第一小的结点10，取出第二小的结点13，构造一棵新结点并加入集合，删除无效结点

5、排序后[15, 23, 29]，取出第一小的结点15，取出第二小的结点23，构造一棵新结点并加入集合，删除无效结点

6、排序后[29, 38]，取出第一小的结点29，取出第二小的结点38，构造一棵新结点并加入集合，删除无效结点

7、集合中[67]此时只有一个结点，那么这个结点就是哈夫曼树的根结点，我们最终就构建出一棵哈夫曼树。

ps：在这里要说明一点，同样的结点集合，可以构造出不同结构的哈夫曼树，但最终得到的结果是一样的。

3.3、哈夫曼树的实现

实现代码：

HuffmanNode

//哈夫曼树的结点类
class Node implements Comparable<Node> {
   
    public Byte data;      //存放结点数据
    public int weight;     //存放结点权重
    public Node left;      //指向左子结点
    public Node right;     //指向右子结点

    //结点类构造方法
    public Node(Byte data, int weight) {
   
        this.data = data;
        this.weight = weight;
    }

    //判断是否是叶子
    public boolean isLeaf() {
   
        return this.left == null && this.right == null;
    }

    @Override//比较方法
    public int compareTo(Node that) {
   
        return this.weight - that.weight;
    }

    @Override//打印对象
    public String toString() {
   
        String d = data == null ? "null" : new String(new byte[]{
   data});
        return "Node{data=" + d + ", weight=" + weight + "}";
    }
}

HuffmanTree

//哈夫曼树的实现类
public class HuffmanTree {
   
    //哈夫曼树的根结点
    private Node root;

    //哈夫曼树构造方法
    public HuffmanTree(List<Node> nodes) {
   
        root = buildHuffmanTree(nodes);
    }

    //哈夫曼树构造方法
    public HuffmanTree(byte[] sourceBytes) {
   
        root = buildHuffmanTree(getNodes(sourceBytes));
    }

    //获取树的叶子结点
    public List<Node> getNodes(byte[] sourceBytes) {
   
        List<Node> nodes = new ArrayList<Node>();
        Map<Byte, Integer> counts = new HashMap<>();
        for (byte sourceByte : sourceBytes) {
   
            Integer count = counts.get(sourceByte);
            if (count == null) {
   
                counts.put(sourceByte, 1);
            } else {
   
                counts.put(sourceByte, count + 1);
            }
        }
        for (Map.Entry<Byte, Integer> entry : counts.entrySet()) {
   
            nodes.add(new Node(entry.getKey(), entry.getValue()));
        }
        return nodes;
    }

    //构建一棵哈夫曼树
    private Node buildHuffmanTree(List<Node> nodes) {
   
        //如果为空则直接返回
        if (nodes.isEmpty()) {
   
            return null;
        }
        //如果nodes只有一个
        if (nodes.size() == 1) {
   
            Node node = nodes.get(0);
            Node root = new Node(null, node.weight);
            root.left = node;
            root.right = node;
            return root;
        }
        //如果nodes不止一个
        while (nodes.size() > 1) {
   
            //从小到大排序二叉树结点
            Collections.sort(nodes);
            //取出第一小的二叉树结点
            Node lNode = nodes.get(0);
            //取出第二小的二叉树结点
            Node rNode = nodes.get(1);
            //重新创建一棵新的二叉树
            Node parent = new Node(null, lNode.weight + rNode.weight);
            parent.left = lNode;
            parent.right = rNode;
            //删除已经处理二叉树结点
            nodes.remove(lNode);
            nodes.remove(rNode);
            //将新的二叉树重新入集合
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    //哈夫曼树根结点
    public Node getRoot() {
   
        return root;
    }

    //层序遍历当前树
    public void layerErgodic() {
   
        if (root != null) {
   
            layerErgodic(root);
        }
    }

    //层序遍历指定树
    private void layerErgodic(Node x) {
   
        //创建一个队列
        Queue<Node> nodes = new LinkedList<>();
        //加入指定结点
        nodes.offer(x);
        //循环弹出遍历
        while (!nodes.isEmpty()) {
   
            //从队列中弹出一个结点，输出当前结点的信息
            Node n = nodes.poll();
            System.out.println(n);
            //判断当前结点还有没有左子结点，如果有，则放入到nodes中
            if (n.left != null) {
   
                nodes.offer(n.left);
            }
            //判断当前结点还有没有右子结点，如果有，则放入到nodes中
            if (n.right != null) {
   
                nodes.offer(n.right);
            }
        }
    }
}

测试代码：

HuffmanTreeTest

public class HuffmanTreeTest {
   
    public static void main(String[] args) {
   
        List<Node> nodes = new ArrayList<>();

        nodes.add(new Node((byte) 'a', 13));
        nodes.add(new Node((byte) 'b', 7));
        nodes.add(new Node((byte) 'c', 8));
        nodes.add(new Node((byte) 'd', 3));
        nodes.add(new Node((byte) 'e', 29));
        nodes.add(new Node((byte) 'f', 6));
        nodes.add(new Node((byte) 'g', 1));

        HuffmanTree huffmanTree = new HuffmanTree(nodes);
        huffmanTree.layerErgodic();
    }
}

运行效果：

3.4、哈夫曼编码介绍

通信领域中信息的处理方式1-定长编码，如果要传输i like like like java do you like a java共40个字符(包括空格) 。

对应ASCII码：105 32 108 105 107 101 32 108 105 107 101 32 108 105 107 101 32 106 97 118 97 32 100 111 32 121 111 117 32 108 105 107 101 32 97 32 106 97 118 97

对应二进制：01101001 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101100 01101001 01101011 01100101 00100000 01101010 01100001 01110110 01100001 00100000 01100100 01101111 00100000 01111001 01101111 01110101 00100000 01101100 01101001 01101011 01100101 00100000 01100001 00100000 01101010 01100001 01110110 01100001

按照二进制来传递信息，总的长度是 359 (包括空格)。这种方式可以实现数据传输，但是需要传输的数据量却很大。

通信领域中信息的处理方式2-变长编码，如果要传输i like like like java do you like a java共40个字符(包括空格) 。

字符个数对应：d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9

按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如空格出现了9 次，编码为0，其他依次类推。

进行字符编码：0= , 1=a, 10=i, 11=e, 100=k, 101=l, 110=o, 111=v, 1000=j, 1001=u, 1010=y, 1011=d

按照上面给各个字符规定的编码，则我们在传输 “i like like like java do you like a java” 数据时，编码就是10010110100...。

但是我们在接收这一串编码10010110100...的时候却无法解析，因为部分字符编码是其他字符编码的前缀，这导致程序无法区分。

字符的编码都不能是其他字符编码的前缀，符合此要求的编码叫做前缀编码，而哈夫曼编码却是一种前缀编码。

通信领域中信息的处理方式3-哈夫曼编码，如果要传输i like like like java do you like a java共40个字符(包括空格) 。

字符个数对应：d:1 y:1 u:1 j:2 v:2 o:2 l:4 k:4 e:4 i:5 a:5 :9

按照各个字符出现的次数进行编码，原则是出现次数越多的，则编码越小，比如空格出现了9次，编码为0，其他依次类推。

按照上面字符出现的次数构建一棵哈夫曼树，字符作为数据，字符出现的次数作为权值。如下图：

根据上图哈夫曼树，给各个字符规定编码，向左的路径为0，向右的路径为1，编码如下:

空格=01
a=101
d=11000
e=000
u=11010
v=0010
i=100
y=11001
j=11011
k=1111
l=1110
o=0011

按照上面的哈夫曼编码，我们为 “i like like like java do you like a java” 字符串进行编码，编码如下：

1000111101001111000011110100111100001111010011110000111011101001010101110000011011100100111101001111010011110000110101110111010010101

当前编码后的长度为133，原来二进制的长度是 359 (包括空格)，压缩了(359-133) / 359 = 62.9%。

此编码满足前缀编码，即字符的编码都不能是其他字符编码的前缀，不会造成匹配的多义性。

3.5、哈夫曼编码实现

实现代码：

HuffmanCode

//哈夫曼编码的实现
public class HuffmanCode {
   
    //哈夫曼树的根结点
    private Node root;
    //记录最后字节位数
    private int lastByteBits;

    public HuffmanCode(HuffmanTree huffmanTree) {
   
        this.root = huffmanTree.getRoot();
    }

    //构建哈夫曼编码表
    public Map<Byte, String> buildHuffmanCode() {
   
        Map<Byte, String> huffmanCodes = new HashMap<>();
        buildHuffmanCode(huffmanCodes, root, "");
        return huffmanCodes;
    }

    //构建哈夫曼编码表
    private void buildHuffmanCode(Map<Byte, String> huffmanCodes, Node node, String s) {
   
        if (node.isLeaf()) {
   
            huffmanCodes.put(node.data, s);
            return;
        }
        buildHuffmanCode(huffmanCodes, node.left, s + "0");
        buildHuffmanCode(huffmanCodes, node.right, s + "1");
    }

    //使用哈夫曼编码表编码得到编码后的字符串
    public String buildHuffmanCodeString(byte[] bytes, Map<Byte, String> huffmanCodes) {
   
        StringBuilder huffmanCodeString = new StringBuilder();
        for (byte data : bytes) {
   
            huffmanCodeString.append(huffmanCodes.get(data));
        }
        return huffmanCodeString.toString();
    }

    //将编码后的字符串转化为相对应的字节数组
    public byte[] buildHuffmanCodeBytes(String huffmanCodeString) {
   
        lastByteBits = huffmanCodeString.length() % 8 == 0 ? 8 : huffmanCodeString.length() % 8;
        int len = (huffmanCodeString.length() + 7) / 8;
        byte[] huffmanCodeBytes = new byte[len];
        int index = 0;
        String element;
        for (int i = 0; i < huffmanCodeString.length(); i += 8) {
   
            if (i + 8 > huffmanCodeString.length()) {
   
                element = huffmanCodeString.substring(i);
            } else {
   
                element = huffmanCodeString.substring(i, i + 8);
            }
            huffmanCodeBytes[index++] = (byte) Integer.parseInt(element, 2);
        }
        return huffmanCodeBytes;
    }

    //压缩
    public byte[] encode(byte[] sourceBytes, Map<Byte, String> huffmanCodes) {
   
     return buildHuffmanCodeBytes(buildHuffmanCodeString(sourceBytes, huffmanCodes));
    }

    //解压
    public byte[] decode(byte[] targetBytes) {
   
     return rebuildHuffmanCodeStringToSourceBytes(rebuildHuffmanCodeTargetBytesToString(targetBytes));
    }

    //反向将编码后的字节数组转化为编码字符串
    public String rebuildHuffmanCodeTargetBytesToString(byte[] huffmanCodeBytes) {
   
        String binaryString;
        StringBuilder huffmanCodeString = new StringBuilder();
        for (int i = 0; i < huffmanCodeBytes.length; i++) {
   
            int element = huffmanCodeBytes[i];
            if (i == huffmanCodeBytes.length - 1) {
   
                if (element > 0) {
   //如果byte是正数，需要补充满8位，负数则不需要
                    element |= 256;
                    binaryString = Integer.toBinaryString(element);
                    binaryString = binaryString.substring(binaryString.length() - lastByteBits);
                } else {
   
                    binaryString = Integer.toBinaryString(element);
                }
            } else {
   
                if (element > 0) {
   //如果byte是正数，需要补充满8位，负数则不需要
                    element |= 256;
                    binaryString = Integer.toBinaryString(element);
                    binaryString = binaryString.substring(binaryString.length() - 8);
                } else {
   
                    binaryString = Integer.toBinaryString(element);
                    binaryString = binaryString.substring(binaryString.length() - 8);
                }
            }
            huffmanCodeString.append(binaryString);
        }
        return huffmanCodeString.toString();
    }

    //反向将编码字符串转化为源字符串字节数组
    public byte[] rebuildHuffmanCodeStringToSourceBytes(String huffmanCodeString) {
   
        List<Byte> datas = new ArrayList<>();
        Node node = this.root;
        for (int i = 0; i < huffmanCodeString.length(); i++) {
   
            char flag = huffmanCodeString.charAt(i);
            if (flag == 48) {
          //如果是0，则代表data在左子树中
                node = node.left;
            }
            if (flag == 49) {
          //如果是1，则代表data在右子树中
                node = node.right;
            }
            if (node.isLeaf()) {
       //如果是叶子，则找到data，重置node
                datas.add(node.data);
                node = this.root;
            }
        }
        byte[] huffmanCodeBytes = new byte[datas.size()];
        for (int i = 0; i < datas.size(); i++) {
   
            huffmanCodeBytes[i] = datas.get(i);
        }
        return huffmanCodeBytes;
    }
}

测试代码：

HuffmanCodeTest

public class HuffmanCodeTest {
   
    public static void main(String[] args) {
   
        String src = "i like java";
        byte[] sourceBytes = src.getBytes();

        System.out.println("解压前显示数据：" + src);
        System.out.println("解压前字节数组：" + Arrays.toString(sourceBytes));

        HuffmanTree huffmanTree = new HuffmanTree(sourceBytes);
        HuffmanCode huffmanCode = new HuffmanCode(huffmanTree);
        Map<Byte, String> huffmanCodes = huffmanCode.buildHuffmanCode();

        byte[] targetBytes = huffmanCode.encode(sourceBytes, huffmanCodes);
        System.out.println("压缩后字节数组：" + Arrays.toString(targetBytes));
        sourceBytes = huffmanCode.decode(targetBytes);
        System.out.println("解压后字节数组：" + Arrays.toString(sourceBytes));

        System.out.print("解压后显示数据：");
        for (byte sourceByte : sourceBytes) {
   
            System.out.print(new String(new byte[]{
   sourceByte}));
        }
    }
}

解压前显示数据：i like java
解压前字节数组：[105, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97]
压缩后字节数组：[-10, 118, 42, -57, 0]
解压后字节数组：[105, 32, 108, 105, 107, 101, 32, 106, 97, 118, 97]
解压后显示数据：i like java

ps：src的长度必须大于0，如果解压后显示数据有中文，则需要使用new String(sourceBytes,"UTF-8")。

第四章单词查找树

4.1、单词查找树的介绍

Trie树又称单词查找树，是一种树形结构，用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。他的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较。

4.2、单词查找树的结构

假设使用 Trie 存储 cat、dog、doggy、does、cast、add 六个单词，则构建树如下图：

现在针对以上单词查找树的结构图，我们定义结点类，并给出最常见的一些方法。

Trie

//单词查找树的实现类
public class Trie<E> {
   
    //单词查找树的结点类
    private class Node {
   
        public Node parent;                     //存储该结点的父结点
        public Map<Character, Node> children;   //存储该结点的子结点
        public Character character;             //存储该结点的字符值
        public E value;                         //存储该结点的对象值
        public boolean isWord;                  //记录是不是单词结尾
    }

    private Node root;                          //记录单词查找树根结点
    private int size;                           //记录单词查找树单词数

    public Trie() {
   
        this.root = new Node();
        this.root.children = new HashMap<>();
    }

    //获取当前树的根结点
    public Node getRoot() {
   
        return root;
    }

    //获取当前树的单词数
    public int size() {
   
        return size;
    }

    //判断当前树是否为空
    public boolean isEmpty() {
   
        return size == 0;
    }

    //清空当前单词查找树
    public void clear() {
   
        size = 0;
        root = null;
    }

    //以下方法请写在这里
}

4.3、单词查找树的实现

添加操作

//添加、替换操作
public E add(String key, E value) {
   
    Node parent = root;
    //循环创建字符路径
    for (int i = 0; i < key.length(); i++) {
   
        Character character = key.charAt(i);
        Node child = parent.children.get(character);
        if (child == null) {
   
            child = new Node();
            child.parent = parent;
            child.children = new HashMap<>();
            child.character = character;
            child.value = value;
            child.isWord = false;

            parent.children.put(character, child);
        }
        parent = child;
    }
    //判断单词是否结尾
    if (parent.isWord) {
   
        E oldValue = parent.value;
        parent.value = value;
        return oldValue;
    }
    //没有结尾则是新增
    parent.isWord = true;
    parent.value = value;
    size++;
    return value;
}

public class TrieTest {
   
    public static void main(String[] args) {
   
        Trie<String> trie = new Trie<>();

        trie.add("tom", "tom@qq.com");
        trie.add("lucy", "lucy@qq.com");
        trie.add("mark", "mark@qq.com");
        trie.add("bill", "bill@qq.com");
        trie.add("james", "james@qq.com");
        trie.add("alan", "alan@qq.com");
        trie.add("jack", "jack@qq.com");

        System.out.println(trie.size());
        System.out.println(trie.add("tom", "123@qq.com"));
        System.out.println(trie.add("tom", "abc@qq.com"));
    }
}

7
tom@qq.com
123@qq.com

获取操作

//获取指定的结点
private Node getNode(String key) {
   
    Node parent = root;
    for (int i = 0; i < key.length(); i++) {
   
        if (parent == null)             return null;
        if (parent.children == null)    return null;
        if (parent.children.isEmpty())  return null;
        Character character = key.charAt(i);
        Node child = parent.children.get(character);
        parent = child;
    }
    return parent;
}

//根据key获取值
public E get(String key) {
   
    Node node = getNode(key);
    return (node != null && node.isWord) ? node.value : null;
}

//判断key的存在
public boolean contains(String key) {
   
    Node node = getNode(key);
    return (node != null && node.isWord);
}

//是否含有前缀串
public boolean startsWith(String prefix) {
   
    return getNode(prefix) != null;
}

public class TrieTest {
   
    public static void main(String[] args) {
   
        Trie<String> trie = new Trie<>();

        trie.add("tom", "tom@qq.com");
        trie.add("lucy", "lucy@qq.com");
        trie.add("mark", "mark@qq.com");
        trie.add("bill", "bill@qq.com");
        trie.add("james", "james@qq.com");
        trie.add("alan", "alan@qq.com");
        trie.add("jack", "jack@qq.com");

        System.out.println(trie.get("james"));
        System.out.println(trie.contains("james"));
        System.out.println(trie.startsWith("ja"));

        System.out.println("====================");

        System.out.println(trie.get("123"));
        System.out.println(trie.contains("123"));
        System.out.println(trie.startsWith("123"));
    }
}

james@qq.com
true
true
====================
null
false
false

删除操作

//删除key的操作
public E remove(String key) {
   
    //找到最后一个结点
    Node node = getNode(key);
    //如果不是单词结尾
    if (node == null || !node.isWord) {
   
        return null;
    }
    //开始进行其他操作
    size--;
    E oldValue = node.value;
    //如果还存有子结点
    if (!node.children.isEmpty()) {
   
        node.isWord = false;
        node.value = null;
        return oldValue;
    }
    //如果不存在子结点
    Node parent;
    while ((parent = node.parent) != null) {
   
        parent.children.remove(node.character);
        if (parent.isWord || !parent.children.isEmpty()) break;
        node = parent;
    }
    return oldValue;
}

public class TrieTest {
   
    public static void main(String[] args) {
   
        Trie<String> trie = new Trie<>();

        trie.add("tom", "tom@qq.com");
        trie.add("lucy", "lucy@qq.com");
        trie.add("mark", "mark@qq.com");
        trie.add("bill", "bill@qq.com");
        trie.add("james", "james@qq.com");
        trie.add("alan", "alan@qq.com");
        trie.add("jack", "jack@qq.com");

        System.out.println(trie.remove("123"));
        System.out.println(trie.remove("tom"));
        System.out.println(trie.remove("james"));
        System.out.println(trie.startsWith("jame"));
        System.out.println(trie.remove("jack"));
        System.out.println(trie.size());
    }
}

null
tom@qq.com
james@qq.com
false
jack@qq.com
4

转载：https://blog.csdn.net/qq_38490457/article/details/115841424

查看评论

飞道的博客

飞道的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章

数据结构：树进阶

目录

第一章并查集

1.1、并查集的介绍

1.2、并查集的结构

1.3、并查集的实现1

1.4、并查集的实现2

1.5、并查集的实现3

第二章二叉堆

2.1、二叉堆的介绍

2.2、二叉堆的结构

2.3、最大堆的实现

2.4、最小堆的实现

2.5、批量建堆实现

第三章最优二叉树

3.1、哈夫曼树的介绍

3.2、哈夫曼树的结构

3.3、哈夫曼树的实现

3.4、哈夫曼编码介绍

3.5、哈夫曼编码实现

第四章单词查找树

4.1、单词查找树的介绍

4.2、单词查找树的结构

4.3、单词查找树的实现

* 以上用户言论只代表其个人观点，不代表本网站的观点或立场

飞道的博客

飞道的博客

个人资料

文章分类

文章存档

阅读排行

评论排行

推荐文章

数据结构：树进阶

目录

第一章 并查集

1.1、并查集的介绍

1.2、并查集的结构

1.3、并查集的实现1

1.4、并查集的实现2

1.5、并查集的实现3

第二章 二叉堆

2.1、二叉堆的介绍

2.2、二叉堆的结构

2.3、最大堆的实现

2.4、最小堆的实现

2.5、批量建堆实现

第三章 最优二叉树

3.1、哈夫曼树的介绍

3.2、哈夫曼树的结构

3.3、哈夫曼树的实现

3.4、哈夫曼编码介绍

3.5、哈夫曼编码实现

第四章 单词查找树

4.1、单词查找树的介绍

4.2、单词查找树的结构

4.3、单词查找树的实现

* 以上用户言论只代表其个人观点，不代表本网站的观点或立场

第一章并查集

第二章二叉堆

第三章最优二叉树

第四章单词查找树