在js中实现大顶堆和小顶堆的操作(javascript)
堆是什么呢,在我们理解堆的过程中,可以把堆想象成一个完全二叉树,堆其实是实现优先队列的一种方式,通常在工程实践中我们会用一组一维的数据,例如数组来实现堆,但是为了方便我们理解,在我们的脑海中最好把堆想象成一个完全二叉树。
那么堆这种树结构适合处理什么问题呢,我们来看一下堆在二叉树中长什么样子
可以看到,在这棵树中,每一个节点都要比他的左右节点大,堆在树中就是长这个样子的,在工程实践中,堆比较适合用来处理需要极值的有一定顺序规律的的场景,什么是极值,就是在一组数据中需要最大/最小的值时,这时我们就可以利用堆来实现。
排序大家都不陌生,堆排序就是其中一种实现排序的方式,它利用了堆的以下特性:极值、弹出当前堆的每一个元素后,会生成一个有序的一维数据。
这其中,也分为大顶堆和小顶堆,大顶堆就是这组数据的极值是这组数据的最大值,当他弹出所有元素后,会剩下一个升序数组;小顶堆则反之,小顶堆的极值是这组数据的最小值,对这个堆进行全部弹出后,会剩下一个降序数组,数组的堆排序就是利用的大顶堆的特性,如图两个二叉树,分别是以0和1开始的一个小顶堆。
在用堆实现一个优先队列的操作时,我们会利用到一些小技巧,例如,我们对一颗完全二叉树进行层序遍历后会发现,坐标以0开头,有以下规律:- 当前节点的左子节点的下标 = 2 * ( 当前节点下表 ) + 1
- 当前节点的右子节点的下标 = 2 * ( 当前节点下表 ) + 2
- 当前节点的父节点的下标 = Math.floor(当前节点下标 / 2)
同时,坐标以0开头,有以下规律:
- 当前节点的左子节点的下标 = 2 * ( 当前节点下表 )
- 当前节点的右子节点的下标 = 2 * ( 当前节点下表 ) + 1
- 当前节点的父节点的下标 = Math.floor(( 当前节点下标 - 1 ) / 2)
当我们进行push操作时,只需要把最新的元素放在树的最后一位,也是具体实现中的数组的最后一位,然后再和父节点比较。
比较时,在大顶堆中,如果当前节点比父节点大,则交换两个元素的位置;在小顶堆中则反之,如果当前节点比父节点小,则交换位置。 这样的比较要一直进行到当前的这棵树符合大顶堆和小顶堆的性质,也就是在大顶堆中,每个节点、左子节点、右子节点三个节点中必须是当前节点的值最大;在小顶堆中,每个节点、左子节点、右子节点三个节点中必须是当前节点的值最小;
接下来我们用js来实现一下大顶堆和小顶堆的操作:
大顶堆:
class HEAP {
constructor(maxSize) {
this.heap = new Array((typeof maxsize === 'number' && !isNaN(maxsize) ? maxsize : 1000)
this.count = 0
}
push(val) {
this.heap[this.count++] = val
let index = this.count - 1
while (index && this.heap[index] > this.heap[Math.floor((index - 1) / 2)]) {
this.swap(this.heap, index, Math.floor((index - 1) / 2))
index = Math.floor((index - 1) / 2)
}
}
pop() {
if (!this.size()) return
this.swap(this.heap, 0, --this.count)
let index = 0, last = this.count - 1
while (index * 2 + 1 <= last) {
let temp = index
if (this.heap[temp] < this.heap[index * 2 + 1]) temp = index * 2 + 1
if (index * 2 + 2 <= last && this.heap[temp] < this.heap[index * 2 + 2]) temp = index * 2 + 2
if (temp === index) break
this.swap(this.heap, temp, index)
index = temp
}
}
top() {
return this.count ? this.heap[0] : undefined
}
size() {
return this.count
}
swap(arr, i1, i2) {
[arr[i1], arr[i2]] = [arr[i2], arr[i1]]
}
}
小顶堆:
class HEAP {
constructor(maxsize) {
this.heap = new Array(typeof maxsize === 'number' && !isNaN(maxsize) ? maxsize : 1000)
this.count = 0
}
size() {
return this.count
}
swap(i, j) {
[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
}
push(val) {
this.heap[this.count++] = val
let index = this.count - 1
while (index > 0 && this.heap[index] < this.heap[Math.floor((index - 1) / 2)]) {
this.swap(index, Math.floor((index - 1) / 2))
index = Math.floor((index - 1) / 2)
}
}
pop() {
if (this.size() === 0) return
this.swap(0, --this.count)
let index = 0, last = this.count - 1
while (index * 2 + 1 <= last) {
let temp = index
if (this.heap[index * 2 + 1] < this.heap[temp]) temp = index * 2 + 1
if (index * 2 + 2 <= last && this.heap[index * 2 + 2] < this.heap[temp]) temp = index * 2 + 2
if (temp === index) break
this.swap(index, temp)
index = temp
}
}
top() {
return this.count ? this.heap[0] : undefined
}
}
以大顶堆为例,接下来我们来试验一下:
const h = new HEAP(4)
h.push(4)
h.push(5)
h.push(8)
h.push(2)
console.log(h.heap, h.top(), h.size());
h.pop()
h.pop()
h.pop()
h.pop()
console.log(h.heap, h.top(), h.size());
输出如下:
没有问题,小顶堆也是一样的使用方法。接下来是闲聊时间!~
毕业也一年多了,最近在好好刷刷算法,也复习复习数据结构,毕竟这些是过多少年都不会变的程序员基本功嘛,多练练总是好的,也有想过边刷题边更新心得体会,不知道能不能坚持下来哈哈哈~,欢迎大家一起交流呀!
推荐阅读
-
Python中的大顶堆和小顶堆:实现从小到大排序的大顶堆
-
Java中的大顶堆和小顶堆
-
C++实现的大顶堆和小顶堆的堆排序算法
-
堆排序中 Go 语言中使用大顶堆和小顶堆的方法
-
《排序算法》——Java中的堆排序(大顶堆和小顶堆)
-
在js中实现大顶堆和小顶堆的操作(javascript)
-
【Netty】「萌新入门」(七)ByteBuf 的性能优化-堆内存的分配和释放都是由 Java 虚拟机自动管理的,这意味着它们可以快速地被分配和释放,但是也会产生一些开销。 直接内存需要手动分配和释放,因为它由操作系统管理,这使得分配和释放的速度更快,但是也需要更多的系统资源。 另外,直接内存可以映射到本地文件中,这对于需要频繁读写文件的应用程序非常有用。 此外,直接内存还可以避免在使用 NIO 进行网络传输时发生数据拷贝的情况。在使用传统的 I/O 时,数据必须先从文件或网络中读取到堆内存中,然后再从堆内存中复制到直接缓冲区中,最后再通过 SocketChannel 发送到网络中。而使用直接缓冲区时,数据可以直接从文件或网络中读取到直接缓冲区中,并且可以直接从直接缓冲区中发送到网络中,避免了不必要的数据拷贝和内存分配。 通过 ByteBufAllocator.DEFAULT.directBuffer 方法来创建基于直接内存的 ByteBuf: ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); 通过 ByteBufAllocator.DEFAULT.heapBuffer 方法来创建基于堆内存的 ByteBuf: ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); 注意: 直接内存是一种特殊的内存分配方式,可以通过在堆外申请内存来避免 JVM 堆内存的限制,从而提高读写性能和降低 GC 压力。但是,直接内存的创建和销毁代价昂贵,因此需要慎重使用。 此外,由于直接内存不受 JVM 垃圾回收的管理,我们需要主动释放这部分内存,否则会造成内存泄漏。通常情况下,可以使用 ByteBuffer.clear 方法来释放直接内存中的数据,或者使用 ByteBuffer.cleaner 方法来手动释放直接内存空间。 测试代码: public static void testCreateByteBuf { ByteBuf buf = ByteBufAllocator.DEFAULT.buffer(16); System.out.println(buf.getClass); ByteBuf heapBuf = ByteBufAllocator.DEFAULT.heapBuffer(16); System.out.println(heapBuf.getClass); ByteBuf directBuf = ByteBufAllocator.DEFAULT.directBuffer(16); System.out.println(directBuf.getClass); } 运行结果: class io.netty.buffer.PooledUnsafeDirectByteBuf class io.netty.buffer.PooledUnsafeHeapByteBuf class io.netty.buffer.PooledUnsafeDirectByteBuf 池化技术 在 Netty 中,池化技术指的是通过对象池来重用已经创建的对象,从而避免了频繁地创建和销毁对象,这种技术可以提高系统的性能和可伸缩性。 通过设置 VM options,来决定池化功能是否开启: -Dio.netty.allocator.type={unpooled|pooled} 在 Netty 4.1 版本以后,非 Android 平台默认启用池化实现,Android 平台启用非池化实现; 这里我们使用非池化功能进行测试,依旧使用的是上面的测试代码 testCreateByteBuf,运行结果如下所示: class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeHeapByteBuf class io.netty.buffer.UnpooledByteBufAllocator$InstrumentedUnpooledUnsafeDirectByteBuf 可以看到,ByteBuf 类由 PooledUnsafeDirectByteBuf 变成了 UnpooledUnsafeDirectByteBuf; 在没有池化的情况下,每次使用都需要创建新的 ByteBuf 实例,这个操作会涉及到内存的分配和初始化,如果是直接内存则代价更为昂贵,而且频繁的内存分配也可能导致内存碎片问题,增加 GC 压力。 使用池化技术可以避免频繁内存分配带来的开销,并且重用池中的 ByteBuf 实例,减少了内存占用和内存碎片问题。另外,池化技术还可以采用类似 jemalloc 的内存分配算法,进一步提升分配效率。 在高并发环境下,池化技术的优点更加明显,因为内存的分配和释放都是比较耗时的操作,频繁的内存分配和释放会导致系统性能下降,甚至可能出现内存溢出的风险。使用池化技术可以将内存分配和释放的操作集中到预先分配的池中,从而有效地降低系统的内存开销和风险。 内存释放 当在 Netty 中使用 ByteBuf 来处理数据时,需要特别注意内存回收问题。 Netty 提供了不同类型的 ByteBuf 实现,包括堆内存(JVM 内存)实现 UnpooledHeapByteBuf 和堆外内存(直接内存)实现 UnpooledDirectByteBuf,以及池化技术实现的 PooledByteBuf 及其子类。 UnpooledHeapByteBuf:通过 Java 的垃圾回收机制来自动回收内存; UnpooledDirectByteBuf:由于 JVM 的垃圾回收机制无法管理这些内存,因此需要手动调用 release 方法来释放内存; PooledByteBuf:使用了池化机制,需要更复杂的规则来回收内存; 由于池化技术的特殊性质,释放 PooledByteBuf 对象所使用的内存并不是立即被回收的,而是被放入一个内存池中,待下次分配内存时再次使用。因此,释放 PooledByteBuf 对象的内存可能会延迟到后续的某个时间点。为了避免内存泄漏和占用过多内存,我们需要根据实际情况来设置池化技术的相关参数,以便及时回收内存; Netty 采用了引用计数法来控制 ByteBuf 对象的内存回收,在博文 「源码解析」ByteBuf 的引用计数机制 中将会通过解读源码的形式对 ByteBuf 的引用计数法进行深入理解; 每个 ByteBuf 对象被创建时,都会初始化为1,表示该对象的初始计数为1。 在使用 ByteBuf 对象过程中,如果当前 handler 已经使用完该对象,需要通过调用 release 方法将计数减1,当计数为0时,底层内存会被回收,该对象也就被销毁了。此时即使 ByteBuf 对象还在,其各个方法均无法正常使用。 但是,如果当前 handler 还需要继续使用该对象,可以通过调用 retain 方法将计数加1,这样即使其他 handler 已经调用了 release 方法,该对象的内存仍然不会被回收。这种机制可以有效地避免了内存泄漏和意外访问已经释放的内存的情况。 一般来说,应该尽可能地保证 retain 和 release 方法成对出现,以确保计数正确。
-
使用Java实现和应用小顶堆和大顶堆:力扣347题目前K个高频元素的解答
-
堆排序中的大顶堆和小顶堆