Java Collection(4)——二叉搜索树(BinarySearchTree)PriorityQueue(优先级队列)

用户11873138

发布于 2026-01-13 21:23:54

1310

前言

本文的二叉搜索树和优先级队列都是基于完全二叉树实现的，所以务必要二叉树的基本结构和操作

1.二叉搜索树

1.1概念和用途

在完全二叉树的基础上，满足左子树所有节点的值小于根节点，右子树所有节点的值大于根节点。主要用于高效的查找，插入和删除操作(时间复杂度是log₂(N))

1.2模拟实现

1.2.1创建内部类

这个步骤和普通二叉树没什么区别

public static class Node{
        public int val;
        public Node left;
        public Node right;

        public Node(int val) {
            this.val = val;
        }
    }
    //根节点是整颗树的根节点，所以定义在内部类之外
    private Node root = null;

1.2.2插入

上节之所以没有讲到二叉树的插入和删除操作，一是因为对二叉树还不够了解，二是因为非完全二叉树不方便进行插入和删除操作

如上图，假设插入value=10的节点，因为普通二叉树不存在左子树的节点小于根节点，右子树的节点大于根节点这样的规则，那么该value=10的节点是插入到4的右边还是5的左边，这样的不确定性就很大。现在基于二叉搜索树，左右子树有明确的大小之分，再来进行插入操作就可以找到唯一确定的位置，下面是插入操作的代码

//插入
    public void insert(int key){
        if (root == null) {
            root = new Node(key);
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null){
            if (cur.val > key){
                parent = cur;
                cur = cur.left;
            }else if (cur.val < key){
                parent = cur;
                cur = cur.right;
            }else {
                System.out.println("存在相同元素,无法插入");
                return;
            }
        }
        //此时的parent节点，要么是叶子节点，要么左右子树至少有一边为空
        Node node = new Node(key);
        if (parent.val < key){
            parent.right = node;
        }
        if (parent.val > key){
            parent.left = node;
        }
    }

1.2.3删除

删除操作分两步走 第一步：找到要删除的元素

//删除
    public void del(int key){
        if (root == null){
            System.out.println("为空,无法删除");
            return;
        }
        Node cur = root;
        Node parent = null;
        while (cur != null){
            if (cur.val > key){
                parent = cur;
                cur = cur.left;
            }else if (cur.val < key){
                parent = cur;
                cur = cur.right;
            }else {
                //删除节点的具体逻辑
                scapegoat(parent,cur);
                return;
            }
        }
        System.out.println("没找到你要删除的元素");
    }

第二部：删除元素

假设删除value=70的节点，那么该节点的左右子树要如何安排？所以，二叉搜索树的删除操作并不是真正删除节点，而是找到一个替罪羊节点来覆盖掉要删除的节点

//寻找替罪羊节点
    private void scapegoat(Node parent,Node cur){
        if (cur.left == null){
            //左树为空且cur是根节点
            if (cur == root){
                root = root.right;
            //左树为空且cur是parent的左子节点
            }else if (cur == parent.left){
                parent.left = cur.right;
            //左树为空且cur是parent的右子节点
            }else {
                parent.right = cur.right;
            }
        }else if (cur.right == null){
            //右树为空且cur是根节点
            if (cur == root){
                root = root.left;
            //右树为空且cur是parent的右子节点
            }else if (cur == parent.right){
                parent.right = cur.left;
            //右树为空且cur是parent的左子节点
            }else {
                parent.left = cur.left;
            }
        //左右子树都不为空
        }else {
            //找到右子树的最左边的子节点
            Node tempParent = cur;
            Node temp = cur.right;
            while (temp.left != null){
                tempParent = temp;
                temp = temp.left;
            }
            //把右子树 的 左子树 的 最左边的节点覆盖掉cur节点
            cur.val = temp.val;
            if (temp == tempParent.left){
                tempParent.left = temp.right;
            }else {
                tempParent.right = temp.right;
            }
        }
    }

1.2.3查找

//查找
    public int find(int key){
        if (root == null){
            System.out.println("为空,无法查找");
            return -1;
        }
        Node cur = root;
        while (cur != null){
            if (cur.val > key){
                cur = cur.left;
            }else if (cur.val < key){
                cur = cur.right;
            }else {
                return cur.val;
            }
        }
        System.out.println("没有这个元素");
        return -1;
    }

二.优先级队列

2.1概念和用途

优先级队列支持插入元素和删除具有最高（或最低）优先级的元素。优先级队列通常用于需要根据优先级处理任务的场景，如任务调度、事件处理等（我之前写的Timer那篇博客就使用了优先级队列）。通常使用堆(Heap)实现（特殊的完全二叉树），因为堆能够高效的进行插入和删除操作时间复杂度分析：比较的次数是完全二叉树的高度，即时间复杂度为log₂(N)

2.2大根堆的模拟实现

2.2.1向下调整

思路：从最后一颗子树开始调整，当把所有子树都调整为大根堆时，整棵树就调整完毕了

最后一颗子树的根节点parent=(数组长度-2)/2 该根节点的左孩子child=(parent*2)+1,右孩子=左孩子+1，找到两个孩子的最大值和根节点比较 由上图可知，底下的两颗子树只需要将child和parent比较交换一次即可但要将整棵树调整为大根堆没那么简单

具体代码如下

//大根堆
    public void createHeap1(){
        //将每一棵子树都进行调整
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0 ; parent--) {
            //调整的具体代码
            shiftDown1(parent,usedSize);
        }
    }
    //
    public void shiftDown1(int parent,int usedSize){
        int child = parent * 2 + 1;
        while (child < usedSize){
            if(child + 1 < usedSize && array[child] < array[child + 1]){
                child++;
            }
            if (array[child] > array[parent]){
                swap(child,parent);
                parent = child;
                child = child * 2 + 1;
            }else {
                break;
            }
        }
    }
    public void swap(int i,int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

2.2.2插入元素

//添加
    public void offer(int data){
        if(usedSize == 0) array[0] = data;
        if (isFull()){
            this.array = Arrays.copyOf(array,array.length*2);
        }
        //违法法
        array[usedSize] = data;
        //向上调整
        
        shiftUp(usedSize);
        usedSize++;
    }
    //向上调整
    public void shiftUp(int child){
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (array[child] > array[parent]) {
                swap(parent, child);
                child = parent;
                parent = (parent - 1) / 2;
            }else {
                break;
            }
        }
    }

2.2.3删除根节点

//删除根
    public int pollRoot(){
        if (usedSize == 0){
            System.out.println("堆为空");
            return -1;
        }
        int ret = array[0];
        //将根节点和最后一个节点交换
        swap(0,usedSize-1);
        //useSize--,就相当于把最后一个节点删除
        usedSize--;
        //向下调整
        shiftDown1(0,usedSize);
        return ret;
    }
    public void shiftDown1(int parent,int usedSize){
        int child = parent * 2 + 1;
        while (child < usedSize){
            if(child + 1 < usedSize && array[child] < array[child + 1]){
                child++;
            }
            if (array[child] > array[parent]){
                swap(child,parent);
                parent = child;
                child = child * 2 + 1;
            }else {
                break;
            }
        }
    }

2.3大/小根堆全部代码

public class MyPriorityQueue {
    public int[] array = new int[10];
    public int usedSize;


    //初始化
    public void initHeap(int[] str) {
        for (int i = 0; i < str.length; i++) {
            array[i] = str[i];
            usedSize++;
        }
    }
    //大根堆
    public void createHeap1(){
        //将每一棵子树都进行调整
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0 ; parent--) {
            //调整的具体代码
            shiftDown1(parent,usedSize);
        }
    }
    //
    public void shiftDown1(int parent,int usedSize){
        int child = parent * 2 + 1;
        while (child < usedSize){
            if(child + 1 < usedSize && array[child] < array[child + 1]){
                child++;
            }
            if (array[child] > array[parent]){
                swap(child,parent);
                parent = child;
                child = child * 2 + 1;
            }else {
                break;
            }
        }
    }
    //小根堆
    public void createHeap2(){
        for (int parent = (array.length - 1 - 1) / 2; parent >= 0 ; parent--) {
            shiftDown2(parent,usedSize);
        }
    }
    //
    public void shiftDown2(int parent,int usedSize){
        int child = parent * 2 + 1;
        while (child < usedSize){
            if(child + 1 < usedSize && array[child] > array[child + 1]){
                child++;
            }
            if (array[child] < array[parent]){
                swap(child,parent);
                parent = child;
                child = child * 2 + 1;
            }else {
                break;
            }
        }
    }
    //
    public void swap(int i,int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    //
    public void disPlay(){
        if (usedSize == 0) System.out.println("堆为空");
        for (int i = 0; i < usedSize; i++) {
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }
    //添加
    public void offer(int data){
        if(usedSize == 0) array[0] = data;
        if (isFull()){
            this.array = Arrays.copyOf(array,array.length*2);
        }
        //违法法
        array[usedSize] = data;
        //向上调整

        shiftUp(usedSize);
        usedSize++;
    }
    //向上调整
    public void shiftUp(int child){
        int parent = (child - 1) / 2;
        while (child > 0) {
            if (array[child] > array[parent]) {
                swap(parent, child);
                child = parent;
                parent = (parent - 1) / 2;
            }else {
                break;
            }
        }
    }
    //
    public Boolean isFull(){
        return usedSize == array.length;
    }
    //删除根
    public int pollRoot(){
        if (usedSize == 0){
            System.out.println("堆为空");
            return -1;
        }
        int ret = array[0];
        //将根节点和最后一个节点交换
        swap(0,usedSize-1);
        //useSize--,就相当于把最后一个节点删除
        usedSize--;
        //向下调整
        shiftDown1(0,usedSize);
        return ret;
    }
}