堆排序前序之队列优先级

应用场景：

　　对于现在的计算机来说，同时可以运行多个程序，加上操作系统里面一大堆的进程，操作系统经常会处理各个进程的排序，从而有条不紊运行各种程序。

　　在这种情况下，需要一种数据结构且需要以下的功能：删除最大元素和插入元素，这种类型叫做优先队列。

提供的方法：

　　常用的排序算法之中的exch（）交换方法，less（）比较方法，此外还提供了插入方法insert（）和删除最大的方法delMax（），以及由此生成的上浮方法swim（）和下沉的方法sink（）。

原理：

　　概念成形图：
　　　　

　　　　从图中可以明显的看出：若将一个数组的所有数据按照图示的顺序排放在一个堆种，且int型数据之中，可以发现每个节点（除开根节点）的的父节点均是当前节点的1/2，即4/2 = 2，5/2=2，得到的总是它的父节点；

　　　　这样就为我门提供了思路：想要一个这样的堆是有序的话，将其中的节点和它的上下节点做对比，如果它比子节点小就和子节点交换位置，如果比父节点大就和父节点交换位置，这两种交换就像泡泡上浮，下沉的样子；所以将其取名为swin和sink；最终也会得到最上面的（数组的第一个）数是最大的；删除的时候，将根节点保存，并和数组的最后一个节点交换，然后返回最大值，将数组的长度减一，最后释放最后一个节点。

　　实现代码：

public class YouxiangDuilie{
    /*
     *通过数组实现队列的优先级
     *
     *
     *
     */
     //初始化数组和定义N表示数组的长度
     private int [] keys;
     private int N;



     /*
      *交换函数
      *
      */
     public void exch(int [] a,int i,int j){
         int temp = a[i];
         a[i] = a[j];
         a[j] = temp;
     }
    /*
     *判断大小函数
     *
     */
     public boolean less(int a,int b){
        return a[a].compareTo(a[b]) < 0;
     }

     /*
      *上浮函数：
      *如果这个数比它的上一级的数大的话，就将它两交换。
      *
      */

      public void swim(int k){
          while(k > 1&& less(k / 2,k)){
              exch(k / 2,k);
              k = k / 2;
          }
      }
      /*
       *将元素下沉
       *
       */
      public void sink(int k){
          while(K * 2 <= N){
              int j = k * 2;
              //此时下标为2*n，需要判断和它同级的数字谁小，取一个小的进行对比
              if(j < N && !less(j,j+1)) j++;//如果是奇数大就将索引放到奇数为
              if(!less(k , j)) break;
              exch(k,j);
              k = j;
          }
      }
     /*
      *实现数组的添加
      *
      */
     public void insert(int n ){
         key[++N] = n ;
         //处于最底层所以要将其上浮
         swim(N);
     }
     /*
      *删除元素的操作并返回
      *
      */
      public int delMax(){
          int maxax = a[1];
          //将最后一个和第一个交换位置；并将数组的长度减一
          exch(1,N--);
          a[N] = null;
          return max;
      }

}