算法练习——堆排序应用(优先队列)

优先队列作为堆排序的高级应用具有十分广泛的应用场景，其中一个就是在共享计算机系统的作业调度。最大优先队列记录将要执行的各个作业以及它们之间的相对优先级．

当一个作业完成或者被中断后，调度器调用  EXTRACT-MAX  从所有的等待作业中，选出具有最高优先级的作业来执行。

在任何时候，调度器可以调用 INSERT() 把一个新作业加入到队列中来。

下面就讨论一下关于优先队列的基本操作：

优先队列(priority queue)是一种用来维护由一组元素构成的集合S的数据结构，其中的每一个元素都有一个相关的值，称为关键字( key)．一个最大优先队列支持以下操作：

　　INSERT(S , x)： 把元素x插入集合S中。

　　MAXIMUM(S)：返回S中具有最大键字的元素．

　　EXTRACT-MAX(S)：去掉并返回S中的具有最大键字的元素。

　　INCREASE-KEY(S , x，k)：将元素x的关键字值增加到k，这里假设k的值不小于x的原关键字值。
　　HeapDelete(A,i)    ：删除第 i 个位置的元素

　　

下面分别给出各自的伪代码描述：

1     INSERT(S,x) 

　　　　把元素x插入到集合S中

MaxHeapInsert(A,key)
    A.heapsize = A.heapsize+1
    A[A.heapsize] =-无穷大
    HeapIncreaseKey(A,A[A.heapsize],key)

 　　　　此时时间复杂度主要消耗在    HeapIncreaseKey()   上，而后者的时间复杂度为   O(logn)

2   INCREASE_KEY(S,x,k)

　　　　将元素x的关键字值增加为k(前提：k>=x)     整体的算法：从开始增大的那个值开始往根节点循环调用。（自低向顶） 

　　  　 该方法的时间复杂度为    O(logn)     因为第三行做关键字更新的结点到根节点的路径长度为  O(logn)

HeapIncreaseKey(A,x,key)
    if key <= A[i]
        error "请输入更大的key值"
    A[i] = key
    while i >=0 && A[Parent(i)] <= A[i]
        Exchange A[i] with A[Parent(i)]
        i = Parent(i)

　　　　HEAP-INCREASE-KEY的操作过程．(a)图6-4(a)中的最大堆，其中下标为i的结点以深色阴影显示．
　　　　(b)该结点的关键字增加到15．
　　　　(c)经过第 4--6 行的 while 循环的一次迭代，该结点与其父结点交换关键字，
　　　　同时下标i的指示上移到其父结点．(d)经过再一次迭代后得到的最大堆．此时，
　　　　A[PARENT(i)]≥A[f]．现在，最大堆的性质成立，程序终止

3    EXTRACT_MAX(S)

　　　　去掉并且返回S中的最大关键字元素

HeapMaxImum(A)
    max = A[0]
    A[0] = A[A.heapsize] 
    A.heapsize = A.heapsize-1
    MaxHeap(A,0)
    return max

     　　EXTRACT_MAX(S)   的时间复杂度为   O( log(n) )，因此除了MaxHeap(A,i)的时间复杂度为O(logn)之外，其余的时间复杂度均为常数。

4   MaxIMUM(S)

　　　　取得S集合中的最大值

HeapMaxImum(A)
    return A[0]

5   HeapDelete(A,i)    

　　　　删除第 i 个位置的元素

HeapDelete(A,i)
    temp = A[i]
    A[i] = A[A.heapsize]
    A.heapsize = A.heapsize-1
    MaxHeap(A,i)
    return temp

具体的代码实现：

/*
 * 优先队列主要通过四个函数来实现
 */
public class Priorityqueue {
    
    static int[] a={15,13,9,5,21,8,7,4,0,6,2,1};
    public static int [] heap =a ;
    public static int heapsize = heap.length;
    
    //给优先队列插入某一个值   数组大小不容易控制     可以考虑使用链表
    public void MaxHeapInsert(int[] A,int key){
        heapsize = heapsize+1;
        a[heapsize-1] = -1000;
        HeapIncreaseKey(a,heapsize,key);
    }
    
    //增加第i个元素的数值
    public void HeapIncreaseKey(int[] a2, int i, int key) {
        if (key <= a[i]) 
            System.out.println("请输入更大的值------");
        a[i] = key;
        //这里也可以用递归
        while(i > 0 && a[HeapSort.findParent(i)]<a[i] ){
            swap(a,HeapSort.findParent(i) , i);
            i = HeapSort.findParent(i);
        }
        
    }

    //交换数组中的两个元素
    private void swap(int[] a2, int parent, int i) {
        int temp = a[i];
        a[i] = a[parent];
        a[parent] = temp;
    }
    
    //取得优先队列的最大值
    public int HeapMaximum(){
        return a[0];
    }
    
    //去掉并且返回最大值最大值
    public int HeapExtractMax(int[] b){
        int max = b[0];
        b[0] = b[heapsize-1];
        heapsize--;
        HeapSort.maxHeap(b , 0);
        return 0;
    }

    //删除优先队列中第i个位置的元素     这里面调用的HeapSort.maxHeap(a,i)  主要来自于上一篇文章中的maxHeap() 在于维持最大堆的性质
    public void MaxHeapDelete(int[] b,int i){
        int temp = b[i];
        b[i] = b[heapsize-1];
        heapsize--;
        HeapSort.maxHeap(b, i);
    }
    
    public void printMy(int[] a){
        for (int i = 0; i < heapsize; i++) 
            System.out.print(a[i]+" ");
        System.out.println();
    }

    
    public static void main(String[] args){
        Priorityqueue pqueue = new Priorityqueue();
        System.out.print("原数组：  ");
        pqueue.printMy(a);
        
        HeapSort.createHeap(a);
        System.out.print("最大堆：  ");
        pqueue.printMy(a);
        
        pqueue.HeapIncreaseKey(a, 7, 11);
        System.out.print("增加数值  ");
        pqueue.printMy(a);
        
        int max = pqueue.HeapMaximum();
        System.out.print("返回最大值  ");
        System.out.println(max);
        
        int extracte = pqueue.HeapExtractMax(a);
        System.out.print("去掉最大值：  ");
        pqueue.printMy(a);
    }
    
}

总之，对于优先队列中所有的操作都可以在   O(logn)  的时间复杂度内完成。