算法分析与设计之堆排序和优先队列

堆排序的时间复杂度为O（nlgn），使用一种我们成为“堆”的的数据结构来进行信息管理。

最大堆：除了根以外的所有结点都要满足：A[PARENT(i)]>=A[i]

最小堆：除了根以外的所有结点都要满足：A[PARENT(i)]<=A[i]

堆排序：利用大顶堆或者小顶堆来对数据进行排序。

import java.util.ArrayList;

//采用Arraylist实现堆排序
public class HS {


    public static void main(String[] args) {
        HeapSort();
    }

    private static void HeapSort() {
        ArrayList arrayList=new ArrayList<>();
        arrayList.add(-1);//使输入的数从1开始
        arrayList.add(101);
        arrayList.add(23);
        arrayList.add(52);
        arrayList.add(91);
        arrayList.add(19);
        arrayList.add(15);

        System.out.println("排序后：");
        print(HeapSort_DES(arrayList));
    }

    private static ArrayList HeapSort_DES(ArrayList arrayList) {
        Build_Max_Heap(arrayList);
        ArrayList temp=new ArrayList<>();
        temp.add(-1);//方便打印
        while(arrayList.size()>1){
            temp.add(arrayList.get(1));
            arrayList.remove(1);
            Max_Heapfy(arrayList,1);
        }
        return temp;

    }
    private static void Build_Max_Heap(ArrayList arrayList) {
        int length=arrayList.size()-1;
        for(int i=length/2;i>0;i--){
            Max_Heapfy(arrayList, i);
        }
    }
    private static void Max_Heapfy(ArrayList arrayList, int i) {
        if(arrayList.size()<=1)
            return;
        int l=left(i);
        int r=right(i);
        int largest=0;
        if(larrayList.get(i)){
            largest=l;
        }else{
            largest=i;
        }
        if(r arrayList.get(largest)){
            largest=r;
        }
        if(largest!=i){
            int temp =  arrayList.get(i);
            arrayList.set(i, arrayList.get(largest));
            arrayList.set(largest, temp);
            Max_Heapfy(arrayList,largest);
        }
    }

    private static int right(int i) {

        return 2*i+1;
    }
    private static int left(int i) {

        return 2*i;
    }

    private static void print(ArrayList arrayList) {
        for(int i=1;i

有了arraylist实现的堆排序，优先队列的四个实现方法也就很好解决了 

①insert（arr、key）方法需要arraylist.add()来实现
②Maximu（arr）返回数组的第一个值就可以，本程序中返回arraylist.get(1)；
③Extract_max(array)将arr[1]的值与arr[arr.length-1]的值交换后，数组最后一个数remove操作
④Increase_key(arr,x,key)使用arraylist的set方法即可