程序员社区

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

一.堆排序介绍

堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复杂度均为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;
        }
    }
赞(0) 打赏
未经允许不得转载:IDEA激活码 » 【数据结构与算法】堆排序算法回顾

相关推荐

  • 暂无文章

一个分享Java & Python知识的社区