优先队列

优先队列基本介绍

​ 优先队列又叫做堆，他是一种比较特殊的完全二叉树。所谓完全二叉树就是一层层的堆叠，本层不满就不能堆放下一层。并且优先队列还有一个特点就是如果他是大根堆那么父节点不小于子节点，如果是小根堆父节点不大于子节点。这也是一个递归定义。

为什么要是用优先队列？

1. 首先如果我们需要查找一个第 k 大的数字，毫无疑问这个是最方便的
2. 他的插入操作和删除操作都是 logn 的复杂度，所以说他是最经济的方式

优先队列的常用操作

插入

插入的时候我们一般采用的方式就是上滤，也就是把要插入的元素放在最后面，然后比较让这个元素向上冒，知道正确的位置。

//插入
    public void insert(int x) {
        if (size > ele.length - 1) {
            return;
        }
        //不使用0号元素
        ele[++size] = x;
        swim(size);
    }

    //上滤操作
    private void swim(int index) {
        while (index / 2 > 0) {
            if (ele[index] > ele[index / 2]) {
                int tep = ele[index];
                ele[index] = ele[index / 2];
                ele[index / 2] = tep;
            }
            index = index / 2;
        }
    }

删除操作

​ 在删除的时候我们再删除了最上面的元素之后我们还需要调整堆的平衡，这个时候我们采取的策略就是下滤，首先用最后一个元素代替要删除的那个元素，然后对该元素进行下滤，直到平衡。

//删除元素
    public int deleteMax(){
        int max = ele[1];
        ele[1] = ele[size--];
        sink(1);
        return max;
    }

    //下滤
    private void sink(int i) {
        int index = i;
        int tmp = ele[i];
        while (i * 2 < size) {
            int next = i * 2;
            if (ele[next + 1] > ele[next]) {
                ++next;
            }
            if (ele[next] > tmp) {
                // int temp = ele[index];
                ele[index] = ele[next];
                // ele[next] = temp;
                index = next;
            }
            i = next;
        }
        ele[index] = tmp;
    }

堆排序

​ 优先队列的很好的一个使用就是堆排序，他有比较好的性能，和优点。

堆排序分为两个步骤：

1. 首先我们需要把一个无序的数组构建成一个优先队列，这个过程我们是从下往上进行的，也就是从它有两个孩子的节点开始依次向上上滤操作。

   

   这样我们就建立了一个完整的优先队列了，接下来就是类似于删除最大元素最小元素的问题了。

2. 然后我们只需要把最大或者最小的元素同最后一个元素交换，然后再次下滤就可以了。这一步就类似于删除顶点元素，的步骤。

   

   这样我们就完成了整个的堆排序

   public class HeapSort {
   
     	//下滤操作	
       public void sink(int[] arr,int i,int end) {
           int index = i;
           int tmp = arr[i];
           while (i * 2 <= end) {
               int n = i * 2;
               if (n+1<=end&&arr[n] > arr[n + 1]) {
                   ++n;
               }
               if (arr[n] < tmp) {
                   arr[index] = arr[n];
                   index = n;
               }
               i = n;
           }
           arr[index] = tmp;
       }
   
       public void sort(int[] arr) {
           //构建堆
           for (int i = arr.length / 2; i > 0; i--) {
               sink(arr, i, arr.length - 1);
           }
           //从堆序生成顺序
           int size = arr.length - 1;
           while (size > 0) {
               int tmp = arr[1];
               arr[1] = arr[size];
               arr[size] = tmp;
               --size;
               sink(arr, 1, size);
           }
       }
   
       @Test
       public void fun(){
           int[] arr = new int[]{0, 7, 2, 5, 8, 3, 9};
           sort(arr);
           System.out.println(arr);
       }
   
   }

   ​

三大排序的分析

三大排序就是快排，堆排序，归并排序。

1. 堆排序的优势在于它能够在最坏的情况下使用 NLogN 的复杂度，并且在不借助辅助空间的情况下完成排序
2. 归并当然也是最坏的情况为 NLogN 时间复杂度，但是他需要借助线性的辅助空间
3. 快排虽然不需要借助空间，但是时间复杂度没有让人满意，最坏情况快排的复杂度到了平方级别。

看起来貌似堆排序是最完美的排序算法，但是其实不是的，下面就是一些缺点：

1. 他的内部循环的次数要高于快排
2. 在现代计算机上我们主存其实也不是很大的问题，这个时候归并其实也没什么不好
3. 他是不稳定的排序算法

常见排序算法的复杂度