排序：Java实现大顶堆和二叉树的广度优先遍历原理及代码注释详解

╰+攻爆jí腚メ 2021-12-11 03:49 106阅读 0赞

附有过程详细思路图解，最后有整体实现的代码

## 一、堆排序 ##

> 堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它是不稳定排序。

**1.堆排序简介**

> 堆是一个近似[完全二叉树][Link 1]（可以简单理解为从根到最后一层，只有最后一层可以存在二叉树的深度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层所有的结点都连续集中在最左边）的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

所以堆排序可以有两种：  
**大顶堆**：每个结点的值都大于或等于其左右孩子结点的值；  
**小顶堆**：每个结点的值都小于或等于其左右孩子结点的值。

这里有一个动态可以看一下加强理解，如果不理解也不影响，继续看下去  
![在这里插入图片描述][20190711015400480.gif]  
**2.算法思路**  
这里我是建造大顶堆，利用将数组放入树中，并借助队列记录左右子树的父亲节点，这样方便将数组中的数放入树中节点，可以满足完全二叉树的特点

下面结合图来举例解释  
例如，我们有数组\{10，8，7，6，5，4，2\}  
**（1）** 将第一个10放入树中的同时，同时也让10进入队列  
![在这里插入图片描述][20190711011545191.png]  
**（2）** 然后按照从左到右的顺序给10安排孩子，让8和7分别作为10的左右孩子放进树中，同时也进入队列，10可以出队了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70]  
**（3）** 同理给8安排孩子，分别是6和5，同时也记录到队列中，8也不需要了那就出队  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 1]  
**（4）** 利用队列的重点来了，当我们将数组中的5放入到8的右孩子后，如何将4快速定位到7的左孩子呢，这个时候我们只要去找队头的7，就解决问题了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 2]  
这样的树就是我们要构建的完全二叉树了，因为举例比较特殊，所以直接也是大顶堆了

**3.代码实现**

//整体思路，将数组中的数变为堆排序，
        // 借助队列记录左右子树的父亲节点，方便放入树中节点（画图解释）
        public static void creatTree(int a[]) { //创建完全二叉树
            LinkedList<treeNode> listNode = new LinkedList();//新建链表，链表模拟队列
            treeNode root = new treeNode(a[0]);//将数组第一位记录到根节点
            listNode.addFirst(root);//将根节点数值入队
            int temp;//声明借助temp进行两数的交换
            for(int i=1;i<a.length;i++) { //for循环遍历数组放入树中（真正的建树过程），以下注释以第一遍循环为例
                treeNode thisNode = listNode.getFirst();//将队列中第一个放入树的第一个节点对象（第一次循环为根节点）
                if (thisNode.getLeft() == null) {   //左孩子为空的情况下
                    treeNode newNode = new treeNode(a[i]);//新建节点存放数组第二个值
                    listNode.add(newNode);//队列中增加此时的第二个值
                    thisNode.setLeft(newNode);//first节点连接左孩子
                    newNode.setParent(thisNode);//左孩子连接父亲节点
                    while (newNode.value>thisNode.value){ //为了构建大顶堆，插入节点的值与父亲节点值进行比较，保证父亲节点值大
                        temp=newNode.value;
                        newNode.value=thisNode.value;
                        thisNode.value=temp;
                        if(thisNode==root){ //根节点无父亲节点
                            break;
                        }
                        newNode = thisNode;//保证所有的孩子节点和父亲节点遵循大顶堆原则（父亲节点值大于孩子节点）
                        thisNode=thisNode.getParent();
                    }
                }
                else if(thisNode.getRight()==null){ //右子树同上
                    treeNode newNode = new treeNode(a[i]);
                    listNode.add(newNode);
                    thisNode.setRight(newNode);
                    newNode.setParent(thisNode);
                    listNode.removeFirst();
                    while (newNode.value>thisNode.value){ 
                        temp=newNode.value;
                        newNode.value=thisNode.value;
                        thisNode.value=temp;
                        if(thisNode==root){ 
                            break;
                        }
                        newNode = thisNode;
                        thisNode=thisNode.getParent();
                    }
                }
            }

一个大顶堆的逻辑就这么出来了，下面看看广度优先遍历

--------------------

## 二、二叉树的广度优先遍历 ##

**1.** 二叉树的广度优先遍历介绍  
这是百度百科解释：[广度优先遍历][Link 2]  
我们可以将**二叉树的广度优先遍历理解为：对二叉树整体进行从上到下，每层从左到右的遍历。**  
**2.算法思路**  
对于二叉树的广度优先遍历的做法类似上面构建大顶堆。

利用队列记录操作的父亲，并将其左右孩子存入队列，只是这是不将父亲出队，而是利用标记来指引树的节点在队列中的索引。最后的队列输出结果就是广度优先遍历结果。  
继续用图来解释：  
**（1）** 首先把根节点10放入队列，并用红色代表我们标记的索引  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 3]  
**（2）** 如果10的左孩子不为空，我们把8放入队列，右孩子也不空，7也放入队列，10的左右孩子都遍历了，但是这是我们不将10出队，只是将标记下移到8  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 4]  
**（3）** 利用队列加标记的重点在这里：下面我们该遍历8的左右孩子了，如果8的左孩子不为空，将6入队，右孩子不为空，5入队，8的左右孩子遍历完了，同样是将标记下移到7，目的也是为了方便直接定位到7的左右孩子，进行遍历  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 5]  
**（4）** 后面依次类推  
**3.代码实现**

//通过队列按照每一层树从左到右输出
            LinkedList<treeNode> queue = new LinkedList(); //链表模拟队列
            int flag = 0;//用来标记树的节点在队列中的索引
            queue.add(root);//根节点加入队列头
            treeNode rroot ;//操作节点的父亲
            while(queue.size()!=a.length){ 
                rroot = queue.get(flag++);
                if(rroot.getLeft() != null){ //左孩子不空，放入队列
                    queue.addLast(rroot.getLeft());
                }
                if(rroot.getRight() !=null){ //右孩子不空，放入队列
                    queue.addLast(rroot.getRight());
                }
            }
            for(int i = 0;i<queue.size();i++){ //队列先进先出的性质输出
                System.out.print(queue.get(i).value+" ");
            }

--------------------

**三、Java实现大顶堆和二叉树的广度优先遍历全部代码及注释详解**  
下面就是将堆排序和广度优先遍历结合起来了直接上代码，有两个文件

**Tree.java**

import java.util.LinkedList;
    public class Tree { 
        //整体思路，将数组中的数变为堆排序，
        // 借助队列记录左右子树的父亲节点，方便放入树中节点（画图解释）
        public static void creatTree(int a[]){ //创建完全二叉树
            LinkedList<treeNode> listNode = new LinkedList();//新建链表，链表模拟队列
            treeNode root = new treeNode(a[0]);//将数组第一位记录到根节点
            listNode.addFirst(root);//将根节点数值入队
            int temp;//声明借助temp进行两数的交换
            
            for(int i=1;i<a.length;i++) { //for循环遍历数组放入树中（真正的建树过程），以下注释以第一遍循环为例
                treeNode thisNode = listNode.getFirst();//将队列中第一个放入树的第一个节点对象（第一次循环为根节点）
                if (thisNode.getLeft() == null) {   //左孩子为空的情况下
                    treeNode newNode = new treeNode(a[i]);//新建节点存放数组第二个值
                    listNode.add(newNode);//队列中增加此时的第二个值
                    thisNode.setLeft(newNode);//first节点连接左孩子
                    newNode.setParent(thisNode);//左孩子连接父亲节点
                    while (newNode.value>thisNode.value){ //为了构建大顶堆，插入节点的值与父亲节点值进行比较，保证父亲节点值大
                        temp=newNode.value;
                        newNode.value=thisNode.value;
                        thisNode.value=temp;
                        if(thisNode==root){ //根节点无父亲节点
                            break;
                        }
                        newNode = thisNode;//保证所有的孩子节点和父亲节点遵循大顶堆原则（父亲节点值大于孩子节点）
                        thisNode=thisNode.getParent();
                    }
                }
                else if(thisNode.getRight()==null){ //右子树同上
                    treeNode newNode = new treeNode(a[i]);
                    listNode.add(newNode);
                    thisNode.setRight(newNode);
                    newNode.setParent(thisNode);
                    listNode.removeFirst();
                    while (newNode.value>thisNode.value){ 
                        temp=newNode.value;
                        newNode.value=thisNode.value;
                        thisNode.value=temp;
                        if(thisNode==root){ 
                            break;
                        }
                        newNode = thisNode;
                        thisNode=thisNode.getParent();
                    }
                }
            }
            //通过队列按照每一层树从左到右输出大顶堆
            LinkedList<treeNode> queue = new LinkedList(); //链表模拟队列
            int flag = 0;//用来标记树的节点在队列中的索引
            queue.add(root);//根节点加入队列头
            treeNode rroot ;//操作节点的父亲
            while(queue.size()!=a.length){ 
                rroot = queue.get(flag++);
                if(rroot.getLeft() != null){ //左孩子不空，放入队列
                    queue.addLast(rroot.getLeft());
                }
                if(rroot.getRight() !=null){ //右孩子不空，放入队列
                    queue.addLast(rroot.getRight());
                }
            }
            for(int i = 0;i<queue.size();i++){ //队列先进先出的性质输出
                System.out.print(queue.get(i).value+" ");
            }
        }
        public static void main(String[] args) { 
            int a[] = { 11,10,4,43,34,54,6};
            creatTree(a);
        }
    }

treeNode.java

public class treeNode { 
        private treeNode left;
        private treeNode right;
        private treeNode parent;
        int value;
    
        public treeNode getLeft() { 
            return left;
        }
        public void setLeft(treeNode left) { 
            this.left = left;
        }
        public treeNode getRight() { 
            return right;
        }
        public void setRight(treeNode right) { 
            this.right = right;
        }
        public int getValue() { 
            return value;
        }
        public void setValue(int value) { 
            this.value = value;
        }
        public treeNode getParent() { 
            return parent;
        }
        public void setParent(treeNode parent) { 
            this.parent = parent;
        }
        public treeNode(int value){ 
            this.value = value;
        }
    }

--------------------

以上就是个人理解，如果看后还不清楚，可以联系我，争取做到人人看后能明白！  
写着是排序，实际就是构造完大顶堆后对其进行取最大值就好。

[Link 1]: https://baike.baidu.com/item/%E5%AE%8C%E5%85%A8%E4%BA%8C%E5%8F%89%E6%A0%91/7773232?fr=aladdin
[20190711015400480.gif]: /images/20211211/69a4bbff03e14e0ab71c33311c98d361.png
[20190711011545191.png]: /images/20211211/c7b33e51af144c9d88e4df9fae801528.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70]: /images/20211211/924f3f11a5f94af5a9481f043c76b0fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 1]: /images/20211211/6939005522fe48df8950e5990ccb9235.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 2]: /images/20211211/19a39b74de47479aafb467db00a96583.png
[Link 2]: https://baike.baidu.com/item/%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E9%81%8D%E5%8E%86/9796192?fr=aladdin
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 3]: /images/20211211/cad90d37287f4f2a92cc32de79ec838c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 4]: /images/20211211/d15b01b7250a4d03ac557b2fb9c0990c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3NDgyMTkw_size_16_color_FFFFFF_t_70 5]: /images/20211211/75fea8a0cad848c9a5e0577911c253b8.png