算法-堆

发表于2025-08-01|更新于2025-08-11|Computer FundamentalsAlgorithmHeap

|总字数:212|阅读时长:1分钟|浏览量:

堆

核心概念

这里并不讨论堆的实现和基本的原理, 只是讨论这个数据结构的使用场景, 解决的问题

使用堆我们能获得O(logn)的时间复杂度的插入和删除元素, O(1)的时间复杂度的获取某个集合的最大(小)值

如果一个场景需要持续获取某个变化集合的最大(小)值, 我们就能考虑使用堆, 并且一定会有出堆操作!!! 不然我们简单维护一个min或max变量就行了

一般解法

// 创建小堆
Queue<Integer> minHeap = new PriorityQueue<>();
// 创建大堆
Queue<Integer> maxHeap = new PriorityQueue<>((a,b) -> b-a);

典型例题

295. 数据流的中位数

347. 前 K 个高频元素

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

Computer Fundamentals Algorithm Heap

相关推荐

算法-Binary Sort-二分查找

二分查找典型特征原数组是有序的, 或者改变原数组顺序不影响答案我们要找出来一个数字在数组中的位置(标准二分查找题目) 一般化特征我们能一次性排除解空间中的一半解我们要找出来解空间中的某一个解的位置解题通法-红蓝染色法我们能将数组依照单调性分成两部分, 以我们要找出target为例 num >= target的部分染成蓝色, num < target为红色, 我们需要染色的区间是[left, right]或者(left-1, right+1)… [left, right]要染色的区间的含义就是我们现在没有染色也就是不知道其中的元素和target之间的关系循环不变量(以两端闭区间举例) left - 1始终是红色 right + 1始终是蓝色思考顺序首先确定我们怎么确定答案, 这种方式一定是要利用原数组在找到答案方面的单调性, 我们一定能一次性排除一半的解空间确定下来红蓝染色情况确定下来没有染色区间的开闭选择(一般是双开区间) 典型例题及实现找到第一个大于等于target的值闭区间12345678910111213141516...

算法-栈 (单调栈)

栈栈核心特征 (什么时候使用栈)本质上是一种用空间换时间的优化方案, 如果我们缓存数据的方向是从左往右(从右往左), 而我们求解答案的时候是从右往左的, 计算完成以后就不需要了, 符合后进先出的特征, 使用栈结构比如括号匹配问题, 我们从左向右遍历和缓存数据, 然后在我们匹配到右括号的时候, 从右往左将数据弹出一般解法1234567891011for (int i = 0; i < nums.length; i++) { // 特殊的情况下, 也就是匹配到了需要解递归的数据的时候 // 元素出栈 while (!stack.isEmpty() && condition) { int j = stack.pop(); ... } // 一般情况下直接将元素入栈 stack.push(i);} 典型题目20. 有效的括号 394. 字符串解码非典型题目155. 最小栈单调栈核心特征单调栈是栈的一种特殊的用法, 我们维护的栈是一个大小单调变化的...

计网-深入理解三次握手的实现原理

三次握手的内部实现原理不同于八股中简单的对三次握手的流程的介绍, 本文会从在Linux中使用socket建立TCP连接完成的工作的角度深度剖析三次握手参考: 深入理解Linux网络：修炼底层内功，掌握高性能原理 (张彦飞) 使用Socket通信的过程 123456// 客户端的核心代码int main(){ int fd = socket(AF_INET, SOCK_STREAM, 0); connect(fd, ....); ....} 12345678// 服务端的核心代码int main() { int fd = socket(AF_INET, SOCK_STREAM, 0); bind(fd, ...); listen(fd, 128); accept(fd, ...); ...} socket函数的作用从开发者的角度我们调用socket函数, 创建一个socket, 然后返回一个句柄用于访问和操作我们这个创建的socket. 从内核的角度来看, 调用这个函数会在内核内部创建...

操作系统I/O - 零拷贝

I/O的演进DMA技术在最开始的时候, 读一个文件的过程是用户进程调用read(), 切换到内核态, CPU向磁盘发起IO请求磁盘将数据放入到磁盘控制器缓冲区里面, 发送IO中断信号给CPU CPU将数据从磁盘数据控制器缓冲区中拷贝到 PageCache CPU将数据从PageCache中拷贝到用户缓冲区 read()调用返回, 切换到用户态一共发生了两次用户态和内核态的上下文切换, 发生了两次拷贝, 并且数据的搬运也是交给CPU来操作的, 占用了大量的CPU的时间, 导致了CPU吞吐量下降解决方式就是引入了DMA(Direct Memory Access)直接内存访问技术, 我们将把数据从磁盘控制器缓冲区搬运到PageCache的工作交给了DMA控制器来进行现在的读一个文件的流程变成了用户进程调用read(), 切换到内核态, 向操作系统发起IO请求, 将数据读取到自己的内存缓冲区中, 进程进入到了阻塞状态 CPU收到操作系统发送的指令以后, 将请求发送给DMA, DMA再进一步发送给磁盘磁盘将数据放入到磁盘控制器缓冲区里面, 发送IO中断信...

操作系统I/O - 多路复用

I/O-多路复用多路复用是解决的什么问题解决的最根本的问题是: 我们怎么让我们的服务器能并发处理更多的数量的请求最经典的问题就是C10K问题: 服务器怎么并发处理1w个请求解决这个问题我们就需要考虑到, 连接占用的资源有哪些文件描述符: Socket实际上是一个虚拟的文件, 也就对应着有相应的文件描述符, 在Linux中一个进程能打开的文件描述符的数量是有限的, 一般来说是1024(默认值) 系统内存: 每个TCP连接在内核中都有对应的数据结构, 也就是每个连接都占用了一定的内存在这些基础上, 我们该怎么实现并发处理1w个请求呢? 多进程模型? 我们每成功建立一个连接就创建一个进程, 这个时候因为fork()创建的子进程中的文件描述符也是被继承过去, 让子进程来通过已连接Socket来提供服务但是这种方式很明显是不能解决C10K问题的, 没有哪个系统扛得住创建1W个进程, 并且进程间切换的成本很高, 性能很差多线程模型为了解决多进程模型中, 进程的体量很大并且切换成本高的问题, 我们换成多线程模型当服务器与客户端 TCP 完成连接后，通过 p...

操作系统内存管理 - Linux物理内存篇

Linux物理内存物理内存检测在物理内存这个硬件和操作系统之间, 还存在着一个固件层(firmware)也叫BIOS. 它负责硬件自检, 初始化所有硬件设备, 加载操作系统引导程序, 将控制权移交给操作系统并提供结构供操作系统读取硬件信息. 操作系统所需的内存等硬件信息都是通过固件来获取的在固件ACPI接口规范中定义了探测内存的物理分布规范. 内核请求中断15H , 并设置操作码为E820H, 因为操作码是E820, 所以这个机制也被称为E820 会在detect_memory_e820函数发出15号中断并处理所有结果, 把内存地址范围保存到boot_params.e820_table对象中. boot_params只是一个中间数据, 专门还有一个e820_table全局数据结构来保存内存地址范围, 在e820__memory_setup中会将boot_params.e820_table保存到e820_table中, 并打印出来. 服务器能通过mseg命令来查看到实际的物理内存地址. memblock内存分配器的创建在完成了E820机制检测到可用的内存地址范围以后, 调用e8...

评论

数据加载中