【数据结构与算法】堆排序算法回顾

一.堆排序介绍

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。

堆排序的应用场景主要有：topk问题，优先级队列等。

原理：
1.将存放在array[0，…，n-1]中的n个元素建成初始堆；
2.此时，堆顶元素该堆的最大值
3.将堆顶元素与堆底元素进行交换，则序列的最大值即已放到正确的位置；
4.但此时堆被破坏，将堆顶元素向下调整使其继续保持大根堆的性质，再重复第3,4步，直到堆中仅剩下一个元素为止。

堆排序

二.堆排序的代码示例

1.初始化堆

public static void initHeap(){
        heap = new int[]{1,2,3,4,5,6,7,8,9,10};
        //heap.length/2-1确定最后一个有子节点的节点
        for(int i = heap.length/2-1;i>=0;i--){
            adjustHeap(i);
        }


    }

    public static void adjustHeap(int i){
        //确定该节点的左子节点和右子节点
        int right = i*2+2;
        int left = i*2+1;
        int max = i;

        if(heap[i]<heap[left]){
            max = left;
        }
        if(right<heap.length&&heap[max]<heap[right]){
            max = right;
        }
        if(max!=i){
            swap(max,i);

            adjustHeap(i);
        }
    }

    public static void swap(int x,int y){
        int temp = heap[x];
        heap[x]=heap[y];
        heap[y]=temp;
    }

经过初始化堆的过程，现在可以发现，最大的数已经在堆顶了
2.堆排序
现在我们要做的是将整个堆变成有序的堆

public static void initHeap(){
        heap = new int[]{1,2,3,4,5,6,7,8,9,10};
        //heap.length/2-1确定最后一个有子节点的节点
        for(int i = heap.length/2-1;i>=0;i--){
            adjustHeap(i,heap.length);
        }
        //堆排序
        for (int i = heap.length-1; i >0 ; i--) {
            //每次讲最大值放到最后
            swap(i, 0);
            //注意这里传入的是i，排除了最后已排序的元素，例如：最后一个元素是我们交换过去的，是最大的，不参与排序
            adjustHeap(0,i);

        }

    }

    public static void adjustHeap(int i,int length){
        //确定该节点的左子节点和右子节点
        int right = i*2+2;
        int left = i*2+1;
        int max = i;
        System.out.println(right+":"+left+":"+length);
        //判断最大值
        if(left<length&&heap[i]<heap[left]){
            max = left;
        }
        if(right<length&&heap[max]<heap[right]){
            max = right;
        }
        if(max!=i){
            //交换
            swap(max,i);
            //递归排序
            adjustHeap(max,length);
        }
    }

    public static void swap(int x,int y){
        int temp = heap[x];
        heap[x]=heap[y];
        heap[y]=temp;
    }

三.总结

堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)...1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。

四.非递归方式实现堆排序

 public static void adjustHeap(int i,int length){
        int max = i;
        int right = i*2+2;
        int left = i*2+1;
        while(left<length){

            //判断最大值
            if(left<length&&heap[i]<heap[left]){
                max = left;
            }
            if(right<length&&heap[max]<heap[right]){
                max = right;
            }
            if(max==i){
                break;
            }
            //交换
            swap(max,i);
            i=max;
            //确定该节点的左子节点和右子节点
            right = i*2+2;
            left = i*2+1;
        }
    }