2025年libco源码分析（libuv源码分析）

大家好，我是讯享网，很高兴认识大家。

小根堆(Min-Heap)是一种完全二叉树结构，它满足以下性质：

在树中任意节点的值都不大于其子节点的值。这样的结构使得小根堆能够高效地取出最小元素，非常适合用于实现优先队列、事件调度等场景。

那么，何为完全二叉树？看下图：

完全二叉树图

如上图，完全二叉树首先是一颗二叉树，然后从上到下、从左到右节点是连续的，称之为完全二叉树。

对完全二叉树有了基本了解之后，便可很容易的理解小根堆了，小根堆就是在完全二叉树基础之上，满足当前节点值不大于子节点值，如下图：

小根堆图

完全二叉树结构：小根堆通常用数组表示，而不是指针链接的节点。由于它是完全二叉树，父节点和子节点的索引可以通过简单的数学计算得到。
• 若当前节点索引为 i，则其左子节点为 2i + 1，右子节点为 2i + 2，父节点为 (i - 1) / 2（取整）。

最小堆性质：每个节点的值都小于或等于其子节点的值，即堆顶元素（数组索引为0的元素）总是整个堆的最小值。

• 插入元素（Push）：

        • 新元素插入到堆的末尾，然后自底向上“上浮”到合适的位置。每次与其父节点比较并交换，直到满足最小堆的性质。

        • 时间复杂度： O(log n)。

• 删除最小值（Pop）：

        • 将堆顶元素（最小值）删除，并用堆的最后一个元素替换堆顶，然后自顶向下“下沉”到合适位置。每次与其子节点中的较小值交换，直到满足最小堆的性质。

        • 时间复杂度： O(log n)。

• 构建小根堆：

        • 可以通过“上浮”法一个一个插入元素构建小根堆，时间复杂度为 O(n log n)。

        • 或者用“下沉”法，从非叶子节点开始自底向上调整，每个节点都进行一次下沉操作，时间复杂度为 O(n)。

优点

高效的最小值提取：小根堆能在 O(1) 时间内获得最小值，在 O(log n) 时间内删除最小值。

适合动态数据：插入和删除的复杂度为 O(log n)，适合动态数据集合的场景，如任务调度和优先队列。

缺点

讯享网

访问非顶点元素不高效：除了堆顶以外的元素无法直接访问，且遍历堆时顺序不定。

平衡维护成本：每次插入和删除操作需要重新调整堆，虽然成本是 O(log n)，但相较于顺序队列有额外开销。

2.3.1 插入

描述：

新增元素放到数组有连续值的末尾，然后按下图与父节点值比较，如果小于则往“上浮”，直到父节点没有大于当前节点值。

此操作时间复杂度为O(log(n))。

插入操作图

2.3.2 弹出

弹出小根堆的根节点，实际上是将最后一个元素值挪到根节点处，然后与左右子节点值中的最小值进行比较，如果大于此2子节点的最小值则交换。

以此类推，直到当前节点值不大于其2子节点值为值。

时间复杂度为O(log(n))。

弹出是指弹出小根堆的根节点，如下图：

小根堆原图

将100挪到根节点13处，替换了根节点13值，如下图：

小根堆弹出操作调整图1

然后，据此往“下沉”，用当前节点值与其2子节点最小值进行比较，如果大于最小值，则与对应节点交换，直到小于子节点值。

小根堆弹出操作调整图2

2.3.3 peek操作

peek操作即是取出小根堆堆顶元素，时间复杂度O(1)，如下图：

弹出操作图

2.3.4 堆调整

对小根堆进行插入和删除操作时，要满足小根堆的性质，因此要对小根堆进行调整，如下图：

小根堆调整图

libevent之小根堆结构定义如下：

讯享网

小根堆的元素是event结构指针:

讯享网

插入元素操作：

讯享网

必要时，对小根堆按原来大小2倍扩容：

小根堆的上浮操作，以满足小根堆的性质：

讯享网

弹出小根堆堆顶元素操作：

小根堆的下沉操作，以满足小根堆性质：

讯享网

删除小根堆中的某个元素，原理是借用小根堆最后一个元素来实现的，用最后一个元素替换要删除的节点值，然后视情况上浮或下沉操作，以满足小根堆的性质：

删除某个小根堆元素时上浮调整，以满足小根堆性质：

讯享网

与min_heap_erase删除小根堆某个元素操作不同，此操作为调整小根堆某个节点struct event *e以满足小根堆性质：

• 性质

完全二叉树结构：适合用数组实现，便于通过索引计算快速定位父节点和子节点。

最小堆性质：任意节点的值不大于其子节点，使得堆顶（即数组首位）始终为最小元素。

• 核心操作

插入元素：将新元素放在堆尾，然后通过“上浮”操作找到合适位置，保持最小堆结构。时间复杂度为 O(log n)。

删除最小值：删除堆顶元素后，用堆尾元素替代堆顶，通过“下沉”操作调整堆结构。时间复杂度为 O(log n)。

• 构建堆

可以通过单个插入操作逐步构建，也可以通过“下沉”法从无序数组直接生成堆，后者时间复杂度更低，为 O(n)。

• 优缺点

优点：支持快速的最小值访问、插入、删除，操作复杂度低，特别适合动态优先级管理。

缺点：访问非堆顶元素效率不高，不适合随机访问和顺序遍历。此外，维护堆结构的调整操作带来一定开销。

2025年libco源码分析（libuv源码分析）

2.3.1 插入

2.3.2 弹出

2.3.3 peek操作

2.3.4 堆调整

相关推荐