首页 > 其他分享 >堆排序 与 比较器

堆排序 与 比较器

时间:2022-08-19 15:57:19浏览次数:113  
标签:index arr int 堆排序 public heapSize heap 比较

堆排序

假如给你一无序的数组,经过堆排序获得一组降序的数组

1、首先我们将数组遍历,进行heapInsert,变为一个大根堆,建立堆的过程

方法一:正序遍历+heapInsert O(N*logN)

当需要建堆的数量少的时候,代价低,数量高的时候,代价高

for(int i = 0; i < arr.length;i++){
    heapInsert(arr,i);//O(log(2,N))
}
方法二:倒序遍历+heapify O(N)

需要建堆的数量少的时候,代价高,数量多的时候,代价低

给你一个数列你可以把它想象成一个大根堆,然后我们从最后一位开始进行heapify,当然没有子节点的是跳过的,就是从后向前找带有子节点的,然后进行heapify,最终得到的数组就是大根堆

for(int i = arr.length - 1 ; i >=0 ;i--){
    heapify(arr,i,arr.length)
}

2、把堆的最大值和堆末尾的值进行交换,然后减少堆的大小后,再去调整堆,一直周而复始,时间复杂度为O(N*logN)

3、堆的大小减为0之后,排序完成

//O(N*log(2,N))
public static void heapSort(int[] arr){
    if(arr == null || arr.length < 2){
        return;
    }
    //把数组整个改为一个大根堆 O(N)
    for(int i = 0; i< arr.length;i++){
        heapInsert(arr,i);//O(log(2,N))
    }
    //这样做速度会更快,和上面那个一样
    //在数组中从右往左,每一个位置开始做heapify,周而复始得到大根堆
    /*for(int i = arr.length - 1 ; i >=0 ;i--){
        heapify(arr,i,arr,length)
    }*/
    //给heapSize赋值
    int heapSize = arr.length;
    //第一位的数(最大值)和最后一位数字交换,然后heapSize-1
    swap(arr, 0, --heapSize);
    //一直进行大根堆化、头节点和最后一个交换,直到heapSize变为0
    while(heapSize > 0){
        heapify(arr, 0, heapSize);//O(log(2,N))
        swap(arr, 0, --heapSize);//O(1)
    }
}

扩展:使用JAVA自带的堆 O(N*logK)

几乎有序:如果把数组排好顺序的话,每个元素移动的距离可以不超过K,并且K对于数组来说比较小

那么,已知一个几乎有序的数组,请选择一个合适的排序算法来对这个数据进行排序

解法:O(N*log(2,K)),如果K很小,可以看作O(N)

设K=5

1、准备一个小根堆,遍历前6个数,下标为0-5的前6个数全部加入到小根堆中。下标为6的不可能进入遍历,因为它如果是最小值,来到0下标需要移动6个距离,

2、排完序后,由于每个元素移动的距离不可用超过5,所以小根堆的最小值一定在下标为0的位置,然后我们从数组中去除这个最小值

public static void soredArrDistanceK(int[] arr, int k){
    //java中自带的的容器,小根堆,属性就跟大根堆相反呗
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    //第一次把0-K个数放进小根堆,如果这个里最后一个元素下标根本不到K,就取这俩之间最小的
    for(int index = 0; index <= Math.min(arr.length-1, k); index++){
        heap.add(arr[index]);
    }
     //小根堆中动态的保存K+1个数,这个操作就是新进来数,把原来的数弹出,0-K个数放进小根堆,如果这个里最后一个元素下标根本不到K,就取这俩之间最小
     for(int i = 0; index <= Math.min(arr.length-1, k); i++, index++){
        heap.add(arr[index]);
        arr[i] = heap.poll();
    }
    //小根堆中动态的保持有k+1个数,加入最后一次小根堆弹完不满k+1个数,下发代码就是把所有剩下的数弹出
    while(!heap.isEmpty()){
        arr[i++] = heap.poll());//弹出最小值,插入数组
    }
}
注意什么时候使用自带的堆结构,什么时候手写堆结构:

1、java中自带的堆容器,只允许我们输入和输出,别的操作,比如我们手写的heapify无法实现,就是说自带的容器就是一个黑盒

2、通常我们需要改变内部结构都需要手写堆

比较器

  1. 实质就是重载比较运算符,比如说数字比大小要用大于小于等于三个关系,但是如果进行其他类型 的比较,怎么定义大于小于等于

  2. 比较器可以很好的应用在特殊标准的排序上

  3. 比较器可以很好的应用在根据特殊标准排序的结构上

  4. 写代码变得容易,用于范性编程

约定俗成的返回值

int compare(T o1, T o2);
  • 参数列表代表,两个同一类型的对象,它俩要进行对比

  • 返回值int

    • 如果返回 -1(或者是负数),就代表o1在前的情况

    • 如果返回 1(或者是正数),就代表o2在前的情况

    • 如果返回 0 ,代表o1,o2 不分先后

例子:自定义student类,让student根据ID大小排序

public class test{
    psvm{
        Student s1 = new Student(1,"asd",12);
        Student s2 = new Student(11,"qwe",11);
        Student[] students = new Student[] {s1, s2};
        //在调用排序的时候传入你要进行排序的数组,和比较器
        Arrays.sort(students, new IdAscendingComparator());
    }
}
public class Student{
    private Integer id;
    private String name;
    private Integer age;
    //get set 构造器
}
//根据id升序排列的比较器,继承了比较器接口Comparator
public static class IdAscendingComparator implements Comparator<Student>{
    @Override
    public int compare(Student o1, Student o2){
        return o1.id - o2.id;
    }
}

自定义堆与比较器

JAVA自带的堆结构,是不能处理堆内部发生变化的,假如堆内部发生了变化,还需要重新再对堆进行根排序化,但是要排序必须要清楚,堆内的对象是如何比较排序的,这里就需要用比较器

例子:resign(),用户对堆里的数据进行了更改,并且要求重建堆结构

例子:resign(),用户对堆里的数据进行了更改,并且要求重建堆结构

public static class MyHeap<T>{
    //之前的堆我们都用的数组,但是这里要保存一类的元素进入堆,数组不能指定泛型索性使用arrayList,这个属性就是指的存放堆中数据的
    //*******这个属性和indexMap密不可分,二者同步更新******
    private ArrayList<T> heap;
    //反向表,用于存放 堆中元素(T) 和 它(T)所在arrayList中的下标(Integer) 
    //*******这个属性和heap密不可分,二者同步更新******
    private HashMap<T, Integer> indexMap;
    //heap的大小
    private int heapSize;
    //比较器属性,用于比较堆内元素是如何进行排序的
    private Comparator<? super T> comparator;
    //构造器,必须传入一个构造器
    public MyHeap(Comparator<? super T> com){
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comparator = com;
    }
    //判断是否为空
    public boolean isEmpty(){
        return heapSize == 0;
    }
    //获取长度
    public int size(){
        return heapSize();
    }
    //堆中是否收过某个元素,直接从反向表中查看是否有就行了
    public boolean contains(T key){
        return indexMap.containsKey(key);
    }
    //向堆中添加元素
    public void push(T key){
        //向堆中添加元素,这个元素在堆list的末尾index=heapSize
        heap.add(value);
        //同时堆和反向表绑定行动,向反向表中插入:添加的元素,与此时元素所在的位置,肯定在heap的末尾
        indexMap.put(value, heapSize);
        //执行heapInsert,在末尾插入元素value,执行根堆化,并且让heap大小+1
        heapInsert(heapSize++);
    }
    //返回堆中最大的元素,并且清除掉最大的元素
    public T pop(){
        //获取到根上最大的值
        T ans = heap.get(0);
        //获取最后一位的下标
        int end = heapSize - 1;
        //把最后一位和根节点互换,删掉根节点的值
        swap(0, end);
        //反向表中,同步删除最大的值
        indexMap.remove(ans);
        //执行heapify,重新大根堆化
        heapify(0, --heapSize);
        return ans;
    }
    //************将堆内的一元素的值进行更新,并不知道更新后的值是多少,只是让你重新排一下堆
    public void resign(T value){
        //可以根据反向表,获取到更新后的值的下标
        int valueIndex = indexMap.get(value);
        //根据这个下标,对堆进行insert或者heapify,因为这两个都有条件,并且只能执行一个
        heapInsert(valueIndex);
        heapify(valueIndex, heapSize);
    }
    //带有比较器的heapInsert,判断条件就查看比较器返回值是否小于0
    public void heapInsert(int index){
        while(comparator.compar(heap.get(index), heap.get(index - 1)/2) < 0){
            swap(index, (index - 1) / 2);
            index = (index - 1)/2;
        }
    }
    //带有比较器的heapify,判断条件就看比较器返回值
    public void heapify(int index, int heapSize){
        int left = 2 * index + 1;
        while(left < heapSize){
            int largest = left + 1 < heapSize
                          && comparator.compare(heap[left], heap[left+1]) ? 
                          left : left+1;
            largest = comparator.compare(heap[largest], heap[index]) ? 
                      largest : index;
            if(lagest == index){
                break;
            }
            swap(index, largest);
            index = largest;
            int left = 2 * index + 1;
        }
    }
    //新的交换代码
    private void swap(int i, int j){
        //通过下标获取到heap中对于保存的值
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        //直接调用list中的set方法,通过给i下标赋值j的值,j下标处赋值i的值完成交换
        heap.set(i, o2);
        heap.set(j, o1);
        //同样,我们的反向表也必须进行更改
        indexMap.put(o1, j);
        indexMap.put(o2, i);
    }
}

leetcode 215 数组的第K个最大元素

215、数组中的第K个最大元素

class Solution {
    public int findKthLargest(int[] nums, int k) {
        int heapSize = nums.length;
        for (int j = heapSize -1 ; j >= 0; j--) {
             heapify(nums, j, heapSize);
        } 
        for (int i = nums.length - 1; i >= nums.length - k + 1; --i) {
            swap(nums, 0, i);
            --heapSize;
            heapify(nums, 0, heapSize);
        }
        return nums[0];
    }
​
​
​
    public void heapify(int[] heap, int index, int heapSize) {
      int left = 2 * index + 1;
        while(left < heapSize){
            int largest = left + 1 < heapSize && heap[left + 1] > heap[left] ? left + 1 : left;
            largest = heap[largest] > heap[index] ? largest : index;
            if(largest == index){
                break;
            }
            swap(heap, index, largest);
            index = largest;
            left = 2 * index + 1;
        }
    }
​
    public void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
}
​

 

标签:index,arr,int,堆排序,public,heapSize,heap,比较
From: https://www.cnblogs.com/phonk/p/16602240.html

相关文章

  • 【排序】各类排序算法的时间性能比较
    用https://www.luogu.com.cn/paste/nzx555us中代码在此题运行时限\(\tt1s\),空间限制\(\tt256MB\)。插入排序冒泡排序选择排序希尔排序快速排序归并排......
  • 比较器Comparable、Comparator
    Comparable接口的使用(自然排序)1.String、包装类等实现了Comparable接口,重写了compareTo(obj)方法,给出了比较两个对象大小的方式.String、包装类重写了compareTo()方法以......
  • KingbaseES时间函数的比较
    KingbaseES提供了多种的时间函数,这些函数在使用过程中存在哪些不同?**同一事务**test=#begintest-#foriin1..10looptest-#raisenotice'time1:%,time2:%,tim......
  • 经典排序之堆排序
    堆排序思路堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分......
  • Park变换比较(自建与simulink中自带)
    模型建立   参数选择及输出波形    ——————————————————————————————————————————————————————......
  • 由浅入深!一文带你彻底明白堆排序
    本文中所有的代码全都是大根堆!实现语言是Java图片来源都是这位大神的,大神的文章也给了我很多启发数据结构之堆堆排序这个视频通俗易懂从什么是堆,什么是堆化,再到实现......
  • 十大排序算法之【堆排序】
    堆排序代码://头文件省略voidheapify(vector<int>&in,intbottom,inttop){intlargest=top;intlson=top*2+1;intrson=top*2+1;if(lson......
  • 1. 对常用I/O模型进行比较说明
      一、服务端I/O流程I/O在计算机中指Input/Output,IOPS(Input/OutputPerSecond)即每秒的输入输出量(或读写次数),是衡量磁盘性能的主要指标之一。IOPS是指单位时......
  • rust f64 比较
      (val1-val2).abs()<f64::EPSILON  val1.to_ne_bytes()==val2.to_ne_bytes()或者 val1.to_bits()==val2.to_bits()......
  • AcWing周赛62-64 中比较有意思的小题题解
    AcWing周赛62-64(选讲)感觉比较思维4502.集合操作https://www.acwing.com/problem/content/4505/根据题意,肯定要使得所取的最大值最大,平均值最小。又因为每次放进来的的......