本文共 2050 字，大约阅读时间需要 6 分钟。

          优先队列是一个常见的堆的应用，他是一种维护一组元素构成的集合S的数据结构。优先队列分为最大优先队列与最小优先队列，在优先队列中，每一个元素都有一个关键字(key)，这个关键字可以用来判别优先队列中元素在所有元素中的优先级。这里我以最大优先队列来举例优先队列里面常见的操作:

1.INSERT(S,x):把元素x插入到集合S里面。2.MAXIMUM(S):返回S里面关键字key最大的元素3.EXTRACT-MAX(S):去掉并返回S中的具有最大关键字key的元素4.INCREASE-KEY(S,x,k):将元素x的关键字值增加到k,这里的k一	般是大于等于x的原关键字值

最小优先队列相应的操作就是:INSERT,MINIMUM,EXTRACT-MIN,DECREASE-KEY.

一.堆排序

如果你已经学过了堆排序可以直接跳过这一节往下看，如果不熟悉请看下面关于利用大根堆实现排序的算法。

1.堆调整

/**     * 我们这里假设i的左子树与右子树     * 已经成功构建为大根堆，然后对索引i处的值作调整,n是数组a的大小     * @param a     * @param i     * @param n     */    void heapify(int[] a,int i,int n){
           int largest = i;        if(2*i+1<=n-1&&a[2*i+1]>a[largest]){
               largest = 2*i+1;        }        if(2*i+2<=n-1&&a[2*i+2]>a[largest]){
               largest = 2*i+2;        }        if(largest!=i){
               swap(a,largest,i);            heapify(a,largest,n);        }    }

这个方法最坏时间复杂度是O(h)，这里的h是从索引i位置开始到最下面又多高。

2.构建堆

void buildMaxHeap(int []a){
           int end = (a.length-2)/2;        for(int i = end;i>=0;i--){
               heapify(a,i,a.length);        }    }

这个构建大根堆的过程就是多次调用heapify,下面我们来分析复杂度:

3.堆排序算法实现

void heapSort(int []a){
           buildMaxHeap(a);        for(int i=a.length-1;i>=1;i--){
               swap(a,0,i);            heapify(a,0,i);        }    }

第一步是先构造大根堆，接下来一直做如下操作:

1.把索引0的值与最后一个元素交换，数组长度n减1 2.重新调整堆结构，调用heapify(a,0,n) 上述最后在n==1时结束，代码中i就是变化的n的值

这个算法是时间复杂度为:

O(n)+(n-1)*O(logn)=O(nlogn)

二.实现优先队列

//复杂度O(1)    int MAXMUM(int []a){
           return a[0];    }    //复杂度O(logn)    int EXTRACT_MAX(int []a){
           int max  = a[0];        swap(a,0,length-1);        heapify(a,0,length-1);        length--;        return max;    }    	//复杂度O(logn)    void INCERASE_KEY(int []a,int i,int key){
           if(i<=length-1&&key>a[i]){
               int current =  i;            while(a[current]>a[(current-1)/2]){
                   swap(a,current,(current-1)/2);                current = (current-1)/2;            }        }    }

关于INSERT，这里的集合结构不应该是数组，我们采用list,具体的做法便是:

将负无穷放在list最后，最后这个元素索引记为index,然后调用INCERASE_KEY(list,index,key)即可。

转载地址：http://jolzi.baihongyu.com/