手撕小顶堆

🕗 发布于 2024-09-26 20:48 java 数据结构

1. 抛砖引玉

在这里插入图片描述

给定两个以升序排列的整数数组 nums1 和 nums2 , 以及一个整数 k 。
定义一对值 (u,v)，其中第一个元素来自 nums1，第二个元素来自 nums2 。
请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。

分析

大根堆（大顶堆）：大根堆即指在逻辑上的二叉树结构中，根结点>子结点，总是最大的，并且在堆的每一个局部都是这样。

小根堆（小顶堆）：与大根堆相反，即所有局部的根都小于子节点。
在这里插入图片描述
在java中优先队列是使用堆实现的。
主要有两个类

PriorityQueue 线程不安全
PriorityBlockingQueue 线程安全

我这里使用PriorityQueue，这一题我们可以通过一个大顶堆来维护一个答案序列

Jdk优先队列允许我们自定义比较器，可以比较的对象是可以使用优先队列的比较条件

PriorityQueue默认实现的是小顶堆，这里我们实现一个大顶堆

                PriorityQueue<List<Integer>> queue = new PriorityQueue<List<Integer>>(new Comparator<List<Integer>>() {
            public int compare(List<Integer> m, List<Integer> n) {
                if(m.get(0) + m.get(1) < n.get(0) + n.get(1)){
                        return 1;
                    }else{
                        return -1;
                    }
            }
        });

到这里，我们可以进行两次for循环

class Solution {
    public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
        List<List<Integer>>result = new ArrayList<>();
        //构造有些队列，自定义比较器
                PriorityQueue<List<Integer>> queue = new PriorityQueue<List<Integer>>(new Comparator<List<Integer>>() {
            public int compare(List<Integer> m, List<Integer> n) {
                if(m.get(0) + m.get(1) < n.get(0) + n.get(1)){
                        return 1;
                    }else{
                        return -1;
                    }
            }
        });
        //两次for循环，向优先队列中添加值
        for(int i = 0; i < nums1.length; i++){
            for(int j = 0; j < nums2.length; j++){
                if(queue.size() < k){
                    queue.offer(Arrays.asList(nums1[i],nums2[j]));
                }else{
                    if(nums1[i] + nums2[j] < queue.peek().get(0) + queue.peek().get(1)){
                        queue.poll();
                        queue.offer(Arrays.asList(nums1[i],nums2[j]));
                    
                    }else{
                        if(nums1[i] > queue.peek().get(0) && nums2[j] > queue.peek().get(1)){
                            break;
                        }
                    }
                }
            }
        }
        for(List<Integer>list : queue){
            result.add(list);
        }
        return result;

    }
}

可能有人要问了，两次for循环为什么我不直接暴力遍历

因为：我们维护了一个答案序列，知道最大或最小值，我们可以轻松淘汰一些无效不必要的遍历，例如：

当的数组1新的值和数组2新的值大于维护的答案队列中堆顶最大的值的时候，这次遍历就是不必要的，可以结束本次小循环。

if(nums1[i] > queue.peek().get(0) && nums2[j] > queue.peek().get(1)){
                            break;
                        }

2. 手撕堆排序

如果是当初，可能只会用 api 就够了，但是现如今，手撕堆排序也是不可或缺的技能了。

选择数据结构
堆排序的最佳选项自然是数组，但是数组用起来并不好用，并不能动态扩容，我们这里使用同样底层是数据的数据结构 ArrayList

class Heap{
    int cap = 10;

    public Heap(int cap) {
        this.cap = cap;
    }
    ArrayList<Integer>list = new ArrayList<>();
    public void insert(int num){
    }
    public int peek(){
        return list.get(0);
    }
    private void bottomSort(int i){
  
    }
    private void topSort(int i){
     
    }

}

实现的函数

对外的函数主要有插入方法和返回堆顶堆方法，对内主要是两个排序方法，是上浮和下浮方法。

为什么有上浮和下浮两个方法？
我刚开始的时候只写了下浮方法，因为前 k 大的算法题已经深深刻入我的脑海，但是随即就想到了一个问题，没加满的时候如何放置？

由于数组内的顺序很重要，不能随便移动，加入头部自然不可能，只能放到尾部，然后进行判值上浮，所以不得不同时实现两个方法，在数据不满的时候使用上浮方法，满了之后替换首个字符，使用下浮方法。

这里我实现小顶堆的方法，希望通用型更强的朋友可以试着使用关键字实现小顶堆和大顶堆两用的方法。

上浮方法

private void bottomSort(int i){
        while (i > 0){
            int iV = list.get(i);
            int lastIndex= (i - 1) / 2;
            int lastV = list.get(lastIndex);
            if(iV < lastV){
                list.set(i,lastV);
                list.set(lastIndex,iV);
            }
            i = lastIndex;


        }
    }

上浮方法比较简单，往往只用和父节点比较就可以，条件终止条件就是，i 已经交换到 0，即头节点。

下浮方法

private void topSort(int i){
        int cur = i;
        int iV = list.get(i);
        while (true){
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if(left < list.size() && list.get(cur) > list.get(left)){
                cur = left;
            }
            if(right < list.size() && list.get(cur) > list.get(right)){
                cur = right;
            }
            if(cur == i){
                break;
            }else {
                list.set(cur,iV);
            }
        }
    }

这里我们用了一个很巧妙的方法把大的数据下浮到较小的叶子上叶子上，实际上堆并没有如此严格，只保证相对有序就可以

插入方法和堆顶方法

 public void insert(int num){
        int size = list.size();
        if(cap == size){
            if(num <= peek()){
                return;
            }
            list.set(0,num);
            topSort(0);
        }else {
            list.add(num);
            bottomSort(size);
        }

    }
    public int peek(){
        return list.get(0);
    }

两个方法相对简单，就不多阐述了

3. 整体小顶堆代码

package 堆排序;

import java.util.ArrayList;

public class Solution {
    public static void main(String[] args) {
        Heap heap = new Heap(10);
        heap.insert(100);
        heap.insert(20);
        heap.insert(221);
        heap.insert(232);
        heap.insert(234);
        heap.insert(22);
        heap.insert(21);
        heap.insert(20);
        heap.insert(19);
        heap.insert(18);
        heap.insert(17);
        System.out.println(heap.peek());

    }

}
class Heap{
    int cap = 10;

    public Heap(int cap) {
        this.cap = cap;
    }

    ArrayList<Integer>list = new ArrayList<>();
    public void insert(int num){
        int size = list.size();
        if(cap == size){
            if(num <= peek()){
                return;
            }
            list.set(0,num);
            topSort(0);
        }else {
            list.add(num);
            bottomSort(size);
        }

    }
    public int peek(){
        return list.get(0);
    }
    private void bottomSort(int i){
        while (i > 0){
            int iV = list.get(i);
            int lastIndex= (i - 1) / 2;
            int lastV = list.get(lastIndex);
            if(iV < lastV){
                list.set(i,lastV);
                list.set(lastIndex,iV);
            }
            i = lastIndex;


        }
    }
    private void topSort(int i){
        int cur = i;
        int iV = list.get(i);
        while (true){
            int left = 2 * i + 1;
            int right = 2 * i + 2;
            if(left < list.size() && list.get(cur) > list.get(left)){
                cur = left;
            }
            if(right < list.size() && list.get(cur) > list.get(right)){
                cur = right;
            }
            if(cur == i){
                break;
            }else {
                list.set(cur,iV);
            }
        }
    }

}

原文地址：https://blog.csdn.net/faker1234546/article/details/142385833

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：前端面试题（四）
下一篇：HPLC智能电表是载波智能电表吗？

计算机网络：网络层 —— 路由信息协议 RIP
路由信息协议(Routing Information Protocol，RIP)，是一种基于距离矢量算法的动态路由协议，主要用于在计算机网络中选择最佳路径，并确保数据包能够正确地从源地址传输到目的地址
阅读更多2024-11-05
【P2-6】ESP8266 WIFI模块在STA模式下实现UDP与电脑/手机网络助手通信——UDP数据透传
完成ESP8266 WIFI模块在STA模式下实现UDP与电脑/手机网络助手通信——实现UDP数据透传。STA模式，通俗来说就是模块/单片机去连接路由器/热点来通信。UDP协议，是传输层协议，UDP没
阅读更多2024-11-05
Stable diffusion 3.5本地运行环境配置记录
一名古代风格的中国女学生坐在现代的计算机教室里面学习编程”安装transformer和tokenizer。Jupyter能使用Anaconda虚环境。解决：安装高于Pytorch>2.0。安装量
阅读更多2024-11-05
【基于轻量型架构的WEB开发】课程作业2 mybatis关联查询、缓存、注解
在@Results注解中，可以包含多个@Result注解，一个@Result注解完成实体类中一个属性和数据表中一个字段的映射。：MyBatis中，@Param注解的功能是指定SQL语句中的参数，通常用
阅读更多2024-11-05
在Android开发中，如何获取手机设备中的所有文件信息？
访问应用的私有存储：使用等方法获取应用的私有目录中的文件信息。访问共享存储的文件：在 Android 10 及更高版本，使用MediaStore访问公开文件（例如图片、视频、音频等）。访问特定的文件路
阅读更多2024-11-05
【Stable Diffusion】
由于embeddings模型本质是提词打包，所以这类虽然节省模型的体积通常很小(通常几kb)空间资源，但由于体积小所携带的信息少，所以现在使用这种模型的也越来越少了。简单来说就是修正出图的颜色，如果不
阅读更多2024-11-05
【k8s】-容器内排查网络问题
容器内没有tcdump、route、ifconfig等网络命令，给我们网络调试、排查问题带来了很大的困难。我们知道，容器有自已的网络命名空间，所以我们。以上就和我们进入容器运行tcpdump命令抓取报
阅读更多2024-11-05
k8s 查看cpu使用率最高的pod
在 Kubernetes 中，可以使用命令查看 Pod 的资源使用情况，从而找到 CPU 使用率最高的 Pod。
阅读更多2024-11-05
人工智能技术在网络安全领域被恶意利用
【代码】人工智能技术在网络安全领域被恶意利用。
阅读更多2024-11-05
Go 语言之搭建通用 Web 项目开发脚手架
MVC 模式代表 Model-View-Controller（模型-视图-控制器）模式。这种模式用于应用程序的分层开发。web_app2/web_app2 执行，viper 读取配置文件失败，找不到
阅读更多2024-11-05

手撕小顶堆

1. 抛砖引玉

分析

2. 手撕堆排序

3. 整体小顶堆代码

相关文章