首页 > 其他分享 >堆排序

堆排序

时间:2023-02-07 08:22:14浏览次数:39  
标签:nums int 堆排序 static heapsize largest public

leetcode-FindKthLargest
public class KthLargest {
    public static void main(String[] args){
        System.out.println(findKthLargest(new int[] {3,2,1,5,6,4} , 2)) ;
    }
    //heapsort-->find kth
    public static int findKthLargest(int[] nums,int k){
        int heapsize=nums.length;
        buildHeap(nums,heapsize);
        for(int i=nums.length-1;i>=nums.length-k+1;--i) {//交换堆顶与堆底元素,找到最大元素的最终正确位置
            swap(nums,0,i);
            --heapsize;
            maxiHeapify(nums, 0, heapsize);
        }
        return nums[0];
    }
    public static void swap(int[] a, int i, int largest){
        int temp=a[i];
        a[i]=a[largest];
        a[largest]=temp;
    }
    public static void buildHeap(int a[], int heapsize){
        for(int i=heapsize/2-1;i>=0;i--){
            maxiHeapify(a,i,heapsize);
        }
    }
    public static void maxiHeapify(int[] a, int i, int heapsize) {
        int left=i*2+1;
        int right=2*i+2;
        int largest=i;
        if(left<heapsize&&a[left]>a[largest]){
            largest=left;
        }
        if(right<heapsize&a[right]>a[largest]){
            largest=right;
        }
        if(largest!=i){
            swap(a,i,largest);
            maxiHeapify(a, largest, heapsize);
        }
    }
}

Heapsort

建堆
从堆的中间开始,依次向下调整,传参调整第i个结点

    public static void buildHeap(int a[], int heapsize){
        for(int i=heapsize/2-1;i>=0;i--){
            AdjustHeap(a,i,heapsize);
        }
    }

调整
判断结点 i 的左孩子和右孩子是否比i的值大,如果大就交换并继续调整交换后的堆;反之不变

    public static void AdjustHeap(int[] a, int i, int heapsize) {
        int left=i*2+1;
        int right=2*i+2;
        int largest=i;
        if(left<heapsize&&a[left]>a[largest]){
            largest=left;
        }
        if(right<heapsize&a[right]>a[largest]){
            largest=right;
        }
        if(largest!=i){
            swap(a,i,largest);
            AdjustHeap(a, largest, heapsize);
        }
    }
    public static void swap(int[] a, int i, int largest){
        int temp=a[i];
        a[i]=a[largest];
        a[largest]=temp;
    }

堆排序

  1. 建堆
  2. 利用for loop 从最后一个结点开始,将堆顶元素与堆底元素交换
  3. 调整,找到最大值的正确位置
    public static void findKthLargest(int[] nums,int k){
        int heapsize=nums.length;
        buildHeap(nums,heapsize);
        for(int i=nums.length-1;i>=0;--i) {
            swap(nums,0,i);//交换堆顶与堆底元素,找到最大元素的最终正确位置
            --heapsize;//最大值已经找到正确位置,不再参与排序
            AdjustHeap(nums, 0, heapsize);
        }
    }

标签:nums,int,堆排序,static,heapsize,largest,public
From: https://www.cnblogs.com/mubai-xx/p/17097191.html

相关文章

  • 算法导论:堆排序
    维护堆主要思想比较\(A[i],A[Left(i)]\)和\(A[Right(i)]\)的大小如果\(A[i]\)不是最大的,则将其与比较大的孩子节点进行交换在堆中继续向下比较和交换,直到\(i......
  • 选择排序+堆排序(实现)
    王道督学营17.1/*Description读取10个整型数据1263589541356503844,然后通过选择排序,堆排序,分别对该组数据进行排序,输出2次有序结果,每个数的输出占3个空格完......
  • 堆排序(Heap Sort)
    一、算法概述1.1算法分类十种常见排序算法可以分为两大类:比较类排序:通过比较来决定元素间的相对次序,由于其时间复杂度不能突破O(nlogn),因此也称为非线性时间比较类排......
  • 17种编程语言实现排序算法-堆排序
    开源地址​​https://gitee.com/lblbc/simple-works/tree/master/sort/​​覆盖语言:C、C++、C#、Java、Kotlin、Dart、Go、JavaScript(JS)、TypeScript(TS)、ArkTS、swift、......
  • 【算法-堆排序】Go语言实现
    堆排序通过数组构造堆,根节点是最大的元素是大根堆,相反为小根堆主要有俩个方法,插入InsertHeap,调整堆:heapify对于排序来说:先把数组构造成一个大根堆,然后[0]依次......
  • p24-p25参数返回值局部变量以及堆排序代码实现
    函数的返回值8位(一个字节)则放到al16位放ax32位放eax64位放raxoffset偏移(可看作一个具体的地址参数传递的办法:1.寄存器2.堆栈整数类型的参数,一律使用int类型:无论......
  • C++ 不知树系列之二叉堆排序(递归和非递归实现上沉、下沉算法)
    1.前言什么是二叉堆?二叉堆是有序的完全二叉树,在完全二叉树的基础上,二叉堆提供了有序性特征:二叉堆的根结点上的值是整个堆中的最小值或最大值。当根结点上的值......
  • 数据结构-堆排序
    文章目录​​1、向下调整​​​​2、向上调整​​​​3、建立堆​​​​4、堆排序​​​​5、删除堆首​​​​6、增加元素​​​​7、完成代码​​堆是由一维数组存储的完......
  • 堆排序 O(N*logN)
    packageclass06;importjava.util.Arrays;/***堆排序*O(N*logN)*/publicclassCode03_HeapSort{publicstaticvoidheapSort(int[]arr){......
  • 堆排序
    本题要求实现堆排序中的筛选函数,待排序列的长度1<=n<=1000。函数接口定义:voidHeapAdjust(HeapTypeH,ints,intm);其中L是待排序表,使排序后的数据从小到大......