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

桃扇骨 2024-03-16 09:44 119阅读 0赞

## 算法|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)\]][img-kZhFurBc-1685191183079_F_typora_image-20230527095309509.png]

### 2.堆结构 ###

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

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

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

**解题思路：**

说明：知道什么是完全二叉树、父节点和子节点位置之间的关系（i,2*i+1,2*i+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)\]][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)\]][img-VRouNdkh-1685191183081_F_typora_image-20230527123314276.png]

### 4.加强堆 ###

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

说明：

1.  已经入堆的元素，如果参与排序的指标方法变化，针对每个元素，系统提供的堆无法做到时间复杂度为O(logN)，都是O(N)
2.  系统提供的堆只能弹出堆顶，做不到自由删除任何一个堆中的元素/做不到在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)\]][img-oVUzsMo2-1685191183082_F_typora_image-20230527172349440.png]

### 堆基本内容总结 ###

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

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

性质：

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

**例题总结：**

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

[img-kZhFurBc-1685191183079_F_typora_image-20230527095309509.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/9a3cbff922f840e9b944fb95181d96eb.png
[img-Vjoh1MsT-1685191183080_F_typora_image-20230527171622475.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/cecedfef959d44a5952614e902aa1afa.png
[img-VRouNdkh-1685191183081_F_typora_image-20230527123314276.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/2ec4d15a76e3462e836036805a98a537.png
[img-oVUzsMo2-1685191183082_F_typora_image-20230527172349440.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/16/3810ce1ef82f4f4bb0cd160128c9e18c.png