数据结构之二叉树与二叉堆

二叉树的数据结构：
A、每个结点都有一个指向其第一个孩子的指针
B、每个结点都有一个指向其第一个右兄弟的指针

普

普通树如何转换成二叉树：
凡是兄弟就用线连起来，然后去掉父亲到儿子的连线，只留下父母到其第一个子女的连线。

二叉树的遍历方式：

先序遍历（中 左 右）： ABDFCEGH 优先级： 父>左孩子>右孩子

中序遍历（前 中 后）： DFBACGEH 优先级：左孩子>父>右孩子

后序遍历（前 后 中）： FDBGHECA 优先级 ：左孩子>右孩子>父

层次遍历：按照层次 从左到右遍历：ABCDEFGH

二叉堆
二叉堆本质上是一种完全二叉树，它有2种：
1.最小堆（父结点的值，小于左右结点）

2.最大堆（父结点的值，大于左右结点）

二叉堆的基本操作：
a.插入操作（首先在末尾添加结点 再通过上浮操作 将结点放在合适的地方）

注：比较新增结点与其父结点的关系，从而决定是否上浮。

b.删除操作（比如要删除 堆顶元素 为了保持完全二叉树的结构 用最后一个结点补到堆顶位置（删除结点处）再进行下沉操作 ）

通过比较新堆顶元素与左右结点的关系，从而决定是否进行下沉操作。

c.构建二叉堆
将一个无序的完全二叉树转换成 二叉堆（最小堆或者最大堆）

最小堆： 由底层到高层 对所有非叶子结点（不存在子节点），进行上浮操作。
由高层层到低层 对所有非叶子结点（不存在子节点），进行下沉操作。
最大堆 反过来

二叉堆的代码实现
二叉堆虽然是一颗完全二叉树，但它并不是链式存储，而是顺序存储。换句话说二叉堆的所有结点都是
存储在数组当中的。并且 父结点与左右结点的下标存在这样的关系：

左孩子=parent*2+1;
右孩子=parent*2+2;
parent=（孩子-1）/2 //左右孩子都是
通过这样的关系可以继续延伸
最后一个非叶子节点的下标为：(array.length-2)/2
判断是否有子节点：左孩子下标

public class HeapOperator {
       public static void upAdjust(int[] array) {     
             int childIndex=array.length-1;
             int parentIndex=(childIndex-1);

             //temp保持插入的叶子节点值，用于最后赋值
             int temp=array[childIndex];

             //childIndex不是堆顶 并且 子节点的值 小于父结点  
             //进行上浮操作
             while(childIndex>0&&temp<array[parentIndex])
             {
                    //无需真正交换   将被替换的节点 赋给上浮的子节点就行
                    array[childIndex]=array[parentIndex];
                    childIndex=parentIndex;
                    parentIndex=(parentIndex-1)/2; //变小


             }

             //若是上浮成功 对上浮来的子节点赋值
             array[childIndex]=temp;
       }
       /**
        * 下沉调整
        * @param array     待调整的堆
        * @param parentIndex    要下沉的父节点
        * @param parentIndex    堆的有效大小
        */
       public static void downAdjust(int[] array, int parentIndex, int length) {
             //保持父节点的值用于最后的赋值
             int temp=array[parentIndex];
             int childIndex=2*parentIndex+1;

             while(childIndex<length) //存在子节点
             {
                    //存在右孩子 并且右孩子的值小于左孩子  定位到右孩子
                    if(childIndex+1 <length&&array[childIndex-1]<array[childIndex])
                    {
                           childIndex++;
                    }
           //如果temp 小于任何一个结点的值直接跳出

                    if(temp <array[childIndex])

                    {
                           break;
                    }


                    //无需进行真正交换
                    array[parentIndex]=array[childIndex];
                    parentIndex=childIndex;
                    childIndex=2*childIndex+1;   //变大了

             }
             array[parentIndex]=temp;
       }
       /**
        * 构建堆
        * @param array     待调整的堆
        */
       public static void buildHeap(int[] array) {
           //从底层的最后一个非叶子节点进行下沉操作
             //这样效率偏低
//           for (int i=(array.length-2)/2;i>=0;i--)
//           {
//                  downAdjust(array, i, array.length);
//           }

             //这样理论更快点
             for(int i=0;i<=(array.length-2)/2;i++)
             {
                    downAdjust(array, i, array.length);
             }
       }
       public static void main(String[] args) {

             //二叉堆创建
             //非叶子结点  大值下沉
        long startTime=System.currentTimeMillis();//记录开始时间
             int[] array =new int[]{7,1,3,10,5,2,8,9,60};
             buildHeap(array);
             System.out.println(Arrays.toString(array));

             long endTime=System.currentTimeMillis();//记录结束时间
             float excTime=(float)(endTime-startTime)/1000;
             System.out.println("执行时间："+excTime+"s");

             //节点添加
              array=new int[]{1,3,2,6,5,7,8,9,10,0};
             upAdjust(array);
             System.out.println(Arrays.toString(array));
       }
}

利用二叉堆实现 堆排列和优先级队列
特性
1.在末尾添加一个结点 通过优先级 进行上浮操作
2.完成堆顶节点（队列） 删除节点（栈顶与最后一个节点交换）时，通过下沉操作 会根据优先级选举出新的堆顶
3.遍历删除 会将最小堆变成最大堆

public class HeapSort {
       public static void downAdjust(int[] array, int parentIndex, int length) {
             //保持父节点的值用于最后的赋值
             int temp=array[parentIndex];
             int childIndex=2*parentIndex+1;

             while(childIndex<length) //存在子节点
             {
                    //存在右孩子 并且右孩子的值小于左孩子  定位到右孩子
                    if(childIndex+1 <length&&array[childIndex-1]<array[childIndex])
                    {
                           childIndex++;
                    }
           //如果temp 小于任何一个结点的值直接跳出

                    if(temp <array[childIndex])

                    {
                           break;
                    }


                    //无需进行真正交换
                    array[parentIndex]=array[childIndex];
                    parentIndex=childIndex;
                    childIndex=2*childIndex+1;   //变大了

             }
             array[parentIndex]=temp;
       }

       public static void heapSort(int [] array)
       {
             //进行下沉操作
             for(int i=0;i<=(array.length-2)/2;i++)
             {
                    downAdjust(array, i, array.length);
             }
             System.out.println(Arrays.toString(array));

             //循环删除堆顶元素

             for(int i=array.length-1;i>0;i--)
             {
                    //最后一个元素与第一个元素交换
                    int temp=array[i];
                    array[i]=array[0];
                    array[0]=temp;
                    //下沉调整最大堆
                    downAdjust(array, 0, i);

             }

       }

       public static void main(String[] args) {


             int[] arr=new int[]{1,3,2,6,5,7,8,9,10,0};
             //先变成最小堆
             //再通过删除栈顶变成了 最大堆
             heapSort(arr);
             System.out.println(Arrays.toString(arr));

       }
}

堆排序 （优先级队列排序） VS 快速排序法

快速排序法
627389
初始量 i=0 (指向第一个数据) j=n-1(指向最后一个数据) k参照值

第一次循环（分2个步骤 先小后大）
a. 从右往左 寻找比k小的值m
交换k与m 的位置
j=m的下标
327689
b.从左往右 寻找比k大的值l
交换k与l 的位置
i=l的下标
326789

下个循环…..
再一次
a.从右往左 寻找比k小的值m
交换k与m 的位置
j=m的下标
当i=j 时 排序完成

建堆：O（n）
堆排序：O（nlogin）
总和：O（nlogin）

堆排序 vs 快速排序
时间 O（nlogin） O (nlogin)
空间 O（1） O（n）

几种复杂的表示方式：
O（1）： 耗时/耗空间与输入数据大小无关
O（n）: 就代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。
O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。
O( login)当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。如：二分查找
O(nlogn)同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。多次使用二分法。