算法6.堆结构、堆排序、加强堆

奋斗吧

擅长邻域：未填写

2023-06-06 18:23:31 179浏览

堆是一颗完全二叉树。优先级队列底层是它。逻辑结构是完全二叉树，存储结构是数组堆中某个节点的值总是不大于或不小于其父节点的值;堆总是一棵完全二叉树。比较器：非基础类型；类实现接口；传对象堆创建：数组；pop–下沉heapify，push——上浮heapInsert（while条件的两个作用）堆排序：从下往上建堆；从上往下建堆；比较的元素，赋的值是坐标heapSort(建堆（heapInsert）+改成有序（heapify）)，升序建大根堆，降序建小跟堆。

算法|6.堆结构、堆排序、加强堆

1.比较器的定义

题意：定义一个学生类，分别实现对学生对象数组按年龄升序、按id降序、按名字的字典序、按id排序且id相同的年龄大的排在前边。

解题思路：

定义一个学生类
定义一个实现了Comparator接口的类A
使用Arrays.sort对它们进行排序时，传一个类A的对象

补充：字符串比较

equals():比较是否相等，相等返回true,不相等返回false str1.equals(str2);
equalsIgnoreCase()：功能与上边类似，但是忽略大小写
==：比较对象引用是否引用相同的实例，一致返回true，不一致返回false
compareTo()：按字典序比较（默认升序）str.compareTo(String otherstr);

这里的需求显然采取最后一种，并且使用默认的即可，倘若要降序，只需要将两个参数交换位置即可。

核心代码：

public static class Student{
    String name;
    int id;
    int age;

    public Student(String name, int id, int age) {
        this.name = name;
        this.id = id;
        this.age = age;
    }

    @Override
    public String toString() {
        return "Student{" +
                "name='" + name + '\'' +
                ", id=" + id +
                ", age=" + age +
                '}';
    }
}

//年龄升序
public static class AgeShengOrder implements Comparator<Student>{

    @Override
    public int compare(Student o1, Student o2) {
        return o1.age-o2.age;
    }
}

//id降序
public static class IdJiangOrder implements Comparator<Student>{

    @Override
    public int compare(Student o1, Student o2) {
        return o2.id-o1.id;
    }
}

//按名字的字典序
public static class NameOrder implements Comparator<Student>{

    @Override
    public int compare(Student o1, Student o2) {
        return o1.name.compareTo(o2.name);
    }
}

//按id排序，id相同，按年龄的降序
public static class IdShengAgeJiangOrder implements Comparator<Student>{

    @Override
    public int compare(Student o1, Student o2) {
        return o1.id==o2.id? (o2.age- o1.age):(o1.id-o2.id);
    }
}

测试代码：

// for test
public static Student[] copyArray(Student[] arr) {
    if (arr == null) {
        return null;
    }
    Student[] res = new Student[arr.length];
    for (int i = 0; i < arr.length; i++) {
        res[i] = arr[i];
    }
    return res;
}

//for test
public static void main(String[] args) {
    Student[] students=new Student[6];
    students[0]=new Student("zhangsan",1,16);
    students[1]=new Student("lisi",2,17);
    students[2]=new Student("wangwu",3,13);
    students[3]=new Student("zhaoliu",4,31);
    students[4]=new Student("liuqi",5,25);
    students[5]=new Student("yuanba",5,28);

    Student[] students1=copyArray(students);
    Student[] students2=copyArray(students);
    Student[] students3=copyArray(students);

    System.out.println("按age升序");
    Arrays.sort(students,new AgeShengOrder());
    System.out.println(Arrays.toString(students));

    System.out.println("按id降序");
    Arrays.sort(students,new IdJiangOrder());
    System.out.println(Arrays.toString(students));

    System.out.println("按名字字典序");
    Arrays.sort(students,new NameOrder());
    System.out.println(Arrays.toString(students));

    System.out.println("按ID升序age降序");
    Arrays.sort(students,new IdShengAgeJiangOrder());
    System.out.println(Arrays.toString(students));
}

测试结果：

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-kZhFurBc-1685191183079)(F:\typora插图\image-20230527095309509.png)]$

2.堆结构

题意：构建堆结构，完成堆元素的插入、弹出、判空、判满

其中插入依赖于1.堆元素的插入方法，弹出依赖于 2.堆顶元素的删除方法。

另外，实验系统的大根堆、小跟堆怎么用

解题思路：

说明：知道什么是完全二叉树、父节点和子节点位置之间的关系（i,2i+1,2i+2）

注意：顺序largest=heap[largest]>index?largest:index;``left=2*index+1;；比较的都是元素，得到的临时结果都是坐标
堆实际是一颗完全二叉树，数据存放实际是在一个数组中，因此先提供一个数组
插入，先判满
弹出，先判空
元素插入堆——是看元素是不是上浮
元素从堆顶删除——使用了替换法，堆顶和堆尾交换，之后依次从顶向下考察

核心代码：

public static class MyMaxHeap{
    private int[] heap;
    private int heapSize;
    private final int limit;

    public MyMaxHeap(int limit) {
        heap=new int[limit];
        heapSize=0;
        this.limit = limit;
    }
    //判空
    public boolean isEmpty(){
        return heapSize==0;
    }
    //判满
    public boolean isFull(){
        return heapSize==limit;
    }
    //插入元素
    public void push(int value){
        if(isFull()){
            System.out.println("已满，误cue");
            return ;
        }
        heap[heapSize]=value;
        heapInsert(heap,heapSize++);
    }
    //元素上浮
    private void heapInsert(int[] heap, int index) {
        //孩子[index] 左右孩子父亲[(index-1)/2]
        //1.上到顶了没 2.不大于父亲
        while(heap[index]>heap[(index-1)/2]){
            swap(heap,index,(index-1)/2);
            index=(index-1)/2;
        }
    }
    private void swap(int[] arr,int i,int j){
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }

    //弹出元素
    public  int pop(){
        if(isEmpty()){
            System.out.println("当前为空，别调");
            return -1;
        }
        int ans=heap[0];
        swap(heap,0,--heapSize);
        heapify(heap,0,heapSize);
        return ans;
    }
    //元素下沉
    private 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 static class BigCom implements Comparator<Integer>{

    @Override
    public int compare(Integer o1, Integer o2) {
        return o2-o1;
    }
}

测试代码：

public static void main(String[] args) {
    System.out.println("系统大根堆");
    //默认是小根堆
    PriorityQueue<Integer> pq=new PriorityQueue<>(new BigCom());
    pq.add(57);
    pq.add(51);
    pq.add(52);
    pq.add(54);
    pq.add(56);
    pq.add(59);
    while(!pq.isEmpty()){
        System.out.println(pq.poll());
    }
    System.out.println("===========================");

    System.out.println("自定义大根堆");
    MyMaxHeap myMaxHeap=new MyMaxHeap(6);
    myMaxHeap.push(57);
    myMaxHeap.push(51);
    myMaxHeap.push(52);
    myMaxHeap.push(54);
    myMaxHeap.push(56);
    myMaxHeap.push(59);

    System.out.println(myMaxHeap.pop());
    System.out.println(myMaxHeap.pop());
    System.out.println(myMaxHeap.pop());
    System.out.println(myMaxHeap.pop());
    System.out.println(myMaxHeap.pop());
    System.out.println(myMaxHeap.pop());
}

测试结果：

$[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-Vjoh1MsT-1685191183080)(F:\typora插图\image-20230527171622475.png)]$

3.堆排序

题意：使用堆排序算法对数组进行排序

解题思路：

堆排序就是在堆的基础上在进行调整（调用上浮下沉方法）的排序算法
堆排序的堆建法有两种，一种是从下往上建，这样要求数据全部给出，另一种是从上往下建，也是经典建法，能够适应数据一个一个给出的情况

这里把两种都给出，但是还是主要理解第二种
（以升序为例）构建方法主要是创建大根堆后，不断将堆顶“弹出”

复杂度、稳定性分析：

平均/最好时间复杂度：O(NlogN)

平均/最好空间复杂度：O（logN）

不稳定

核心代码：

    public static void heapSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        //从上往下O(N*logN)
        for (int i = 0; i < arr.length; i++) {
            heapInsert(arr,i);
        }
        //从下往上O(N)
//        for (int i = arr.length - 1; i >= 0; i--) {
//            heapify(arr, i, arr.length);
//        }

        int heapSize = arr.length;
        swap(arr, 0, --heapSize);
        while (heapSize > 0) {
            heapify(arr, 0, heapSize);
            swap(arr, 0, --heapSize);

        }
    }

    //元素上浮
    private static void heapInsert(int[] heap, int index) {
        //孩子[index] 左右孩子父亲[(index-1)/2]
        //1.上到顶了没 2.不大于父亲
        while (heap[index] > heap[(index - 1) / 2]) {
            swap(heap, index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    //元素下沉
    private static 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;
        }
    }

测试代码：

// for test
public static void comparator(int[] arr) {
    Arrays.sort(arr);
}

测试结果： $[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VRouNdkh-1685191183081)(F:\typora插图\image-20230527123314276.png)]$

4.加强堆

题意：给定堆结构，保证删除指定元素时间复杂度为O(logN)。

说明：

已经入堆的元素，如果参与排序的指标方法变化，针对每个元素，系统提供的堆无法做到时间复杂度为O(logN)，都是O(N)
系统提供的堆只能弹出堆顶，做不到自由删除任何一个堆中的元素/做不到在O(logN)的条件下完成弹出

解题思路：

做不到自如弹出，是因为，元素进堆之后，我们不能确定它的位置
如果知道具体位置，那么调整还是删除直接对当前位置进行heapInser或者heapify即可
怎么知道具体位置——我们手动加一张反向索引表，即通过元素值得到它在堆中的位置

核心代码：

//堆中的元素一定要是引用类型，否则就包一层
public class HeapGreater<T> {
    private ArrayList<T> heap;
    //精华所在
    private HashMap<T, Integer> indexMap;
    private int heapSize;
    private Comparator<? super T> comp;

    public HeapGreater(Comparator<? super T> comp) {
        this.comp = comp;
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
    }

    //判空
    public boolean isEmpty() {
        return heapSize == 0;
    }

    //判满——没必要，容器大小可以动态变化

    //看堆顶
    public T peek(){
        return heap.get(0);//这里使用的是ArrayList的方法
    }

    //压入元素
    public void push(T value){
        heap.add(value);
        indexMap.put(value,heapSize);//调整之后的坐标在swap中进行更改
        heapInsert(heapSize++);
    }

    //弹出元素
    public T pop() {
        T ans=heap.get(0);
        swap(0,heapSize-1);
        indexMap.remove(ans);
        heapify(0);
        return ans;
    }

    //删除值为obj的元素
    public void remove(T obj){
        T replace=heap.get(heapSize-1);

        int index=indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        //如果是堆底直接删，不影响，反之需要重新设置
        if(obj!=replace){
            heap.set(index,replace);
            indexMap.put(replace,index);
            resign(replace);
        }
    }

    public void resign(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    //返回堆上所有的元素
    public List<T> getAllElements(){
        List<T> ans = new ArrayList<>();
        for (T c : heap) {
            ans.add(c);
        }
        return ans;
    }

    //元素上浮
    private void heapInsert(int index) {
        //默认建立小跟堆
        //1.上到顶了没 2.不大于父亲
        while(comp.compare(heap.get(index),heap.get((index-1)/2))<0){
            swap(index,(index-1)/2);
            index=(index-1)/2;
        }
    }
    private void swap(int i,int j){
        T o1=heap.get(i);
        T o2 = heap.get(j);
        heap.set(i,o2);
        heap.set(j,o1);
        indexMap.put(o2,i);
        indexMap.put(o1,j);
    }

    //元素下沉
    private void heapify(int index) {
        int left=2*index+1;
        while(left<heapSize){
            int best=left+1<heapSize&&comp.compare(heap.get(left+1),heap.get(left))<0?left+1:left;
            best=comp.compare(heap.get(best),heap.get(index))<0?best:index;
            if(best==index){
                break;
            }
            swap(index,best);
            index=best;
            left=2*index+1;
        }
    }
    public static class MyCom implements Comparator<Integer>{

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1-o2;
        }
    }

}

测试代码：

public static void main(String[] args) {
    HeapGreater<Integer> heapGreater=new HeapGreater<>(new MyCom());
    heapGreater.push(1);
    heapGreater.push(11111);
    heapGreater.push(1111);
    heapGreater.push(111);
    System.out.println(heapGreater.getAllElements());
    System.out.println(heapGreater.pop());
    heapGreater.remove(111);
    System.out.println(heapGreater.getAllElements());
}

测试结果： $[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oVUzsMo2-1685191183082)(F:\typora插图\image-20230527172349440.png)]$

堆基本内容总结

堆是一颗完全二叉树。优先级队列底层是它。

逻辑结构是完全二叉树，存储结构是数组

性质：

堆中某个节点的值总是不大于或不小于其父节点的值;
堆总是一棵完全二叉树。

例题总结：

比较器：非基础类型；类实现接口；传对象
堆创建：数组；pop–下沉heapify，push——上浮heapInsert（while条件的两个作用）
堆排序：从下往上建堆；从上往下建堆；比较的元素，赋的值是坐标heapSort(建堆（heapInsert）+改成有序（heapify）)，升序建大根堆，降序建小跟堆

好博客就要一起分享哦！分享海报

此处可发布评论

评论（0）展开评论

暂无评论，快来写一下吧

展开评论

您可能感兴趣的博客