优先级队列以及堆排序

对一个数组进行排序时间复杂度为O(n)级别 效率太低了,听说堆排序可以提
高效率 时间复杂度为 级别，甩几条街啊!
首相我们先了解一下堆排序 本次主要针对大根堆排序：
1.堆是一种特殊的树形数据结构，其每个节点都有一个值，通常提到的堆都是指一颗完全二叉树，根结点的值小于（或大于）两个子节点的值，同时，根节点的两个子树也分别是一个堆。
2.根结点大于两个子节点的值为大根堆，根结点小于两个子节点的值为小根堆

image
我们先思考一个问题 如果往集合里面push值 怎么让最大值处于最上面呢？没错就是每次push值得时候让父结点和子结点进行比较 然后交换位置 把最大值放在根结点上 接着从下往上把最大值上移到 根结点上 ，不多说上一波代码 存储数组从角标为1开始的计算起来方便 从0也可以看个人

int index=0
void shiftUp(int index) {
    if (index>1 && array[index]>array[index/2]){
        swap(array[index],array[index/2]);
        shiftUp(index/2);
     }
}
void push(int e) {
    array[index+1]=e;
    index++;
    shiftUp(index);
    for (int i = 0; i <index; ++i) {
        __android_log_print(ANDROID_LOG_ERROR,"TAG","%d",array[i+1]);
    }
    __android_log_print(ANDROID_LOG_ERROR,"TAG","-----------------");
}

void shiftDown(int key) {
    while (key *2 <= index ){
       int max=key*2;
       if (max+1<=index && array[max+1]>array[max]){
           max=max+1;
       }
       if (array[key]> array[max]){
           break;
       }
       swap(array[max],array[key]);
       key=max;
   }
}

int pop() {
    int max=array[1];
    array[1]=array[index];
    index--;
    shiftDown(1);

    return max;
}

pop方法是从堆里面拿到数组最大值 然后接着把数组排序 最大值移动到根结点 即array[1]
有了以上大根堆的排序思想 我们接着思考怎么对一个数组进行排序呢？
1.我们首先从不是叶子节点的结点进行排序，让所有父节点大于子结点这样根节点就是最大值，角标即为0；
2.我们将角标为0的最大值与最后一位数进行交换位置，最后一个就是最大值了，接着我们排序 让所有父节点大于子结点这样根节点就又是最大值，然后交换位置，这样不就成了顺序排序了吗，一直把最大值放到后面
这里有点绕得好好想一想 先上一波代码参考一下

void adjustArray(int array[],int key,int n) {
    while (key *2 +1<  n ){
        int max=key*2+1;
        if (max+1< n && array[max+1]>array[max]){
            max=max+1;
        }
        if (array[key]> array[max]){
            break;
        }
        swap(array[max],array[key]);
        key=max;
    }
}
//排序
void headSort(int array[],int n){
//从最后不是叶子节点的节点进行 大根对排序
    for (int i = n/2 -1; i >=0 ; i--) {
        adjustArray(array,i,n);
    }

    //将最大值跟最后一个交换
    for (int len = n-1; len >=0 ; --len) {
        swap(array[0],array[len]);
        adjustArray(array,0,len);
    }
}

好了堆排序就说到这里 有什么问题可以提出来喔！楼主也是一个热心探究者