数据结构与算法

面试时遇到的一道题：给出给出 n 个数，求出前 k 小的数字。 输入是 n + 1 行： 第一行是 n 和 k 之后 n 行是这个数列 输出是 k 个数。 当时没想出来怎么做，直接嗯排序，然后输出，OJ 的时限比较宽容，竟然过了😄。 ...

最近看到了一些关于侵入式和非侵入式链表的讨论，决定研究一下它们两个。 侵入式和非侵入式链表的区别 这里的侵入是相对于链表的指针域来说，所以最主要的区别就是非侵入式的链表容器中保存了一份用户传入的值。 ...

之前学习 Lua 的时候就对它的 Table 很感兴趣，最近在看 Lua 解释器的源码，因此就想研究一下具体是怎么实现这个 Lua 之中最为重要的数据结构的。 Lua Table 简介 在 Lua 语言之中，数组是 table ，字典是 table ，就连对象、模块、包也是通过 table 实现的： ...

联创 Lab 组新人任务第一弹。 关于斐波那契堆 结构与特点 斐波那契堆是由一组最小堆有序树构成的。每个节点的度数为其子节点的数目。树的度数为其根节点的度数。 斐波那契堆中的树都是有根的但是无序。每个节点x包含指向父节点的指针p[x]和指向任意一个子结点的child[x]。x的所有子节点都用双向循环链表链接起来，叫做x的子链表。子链表中的每一个节点y都有指向它的左兄弟的left[y]和右兄弟的right[y]。如果节点y是x仅有的子节点，则left[y]=right[y]=y。 斐波那契堆中所有树的根节点也用一个双向循环链表链接起来。 使用一个指针指向斐波那契堆中最小元素。 斐波那契堆将操作尽可能地延后，它的插入是懒惰的，只有在不得不进行合并操作时才进行合并。在极端情况下，它甚至是一个长度很大的链表。 插入操作 将一个节点直接插入到根链表中，并比较键值的大小，如果新节点的键值小于原有节点的键值，就将斐波那契堆的指向最小节点的指针指向它。 ...

联创 Lab 组新人任务第一弹。 关于LLRB 定义 根节点是黑色的。 红色节点的儿子一定是黑色的。 任意节点到任意叶子的最短路径上都有相同数量的黑色节点。 黑色节点的儿子要么全是黑色，要么只有左儿子是黑色。 前三点与红黑树的性质相同，第四点为左偏红黑树的特殊性质，这导致了它的操作相对红黑树更加简单。 左偏红黑树也可以认为其相邻节点的边是有颜色的。 空节点的颜色认为是黑色。 插入操作 可以先就像向二叉查找树中插入节点一样操作，插入时将其颜色赋为红色。如果插入时是黑色，这会导致破坏了LLRB的平衡性质。 保持住了黑色平衡性质之后再来调整其他结构性质，要对连续两个红色节点、只有右儿子是红色节点进行旋转，对左右儿子都是红色的节点进行颜色翻转（拆分2-3-4树中的4-node）。 其操作可以是递归的，编写代码也将更加容易实现。 优先保持平衡性质的原因有：在一开始插入时保持平衡性质最容易实现（只需要给新节点赋红色），此时若优先考虑其他性质，会导致需要考虑的情况过多，而且在后续进行修补（旋转、颜色翻转）的时候不会破坏其平衡性质。 删除操作 依然优先考虑其平衡性质，删除的节点需要是红色的，因此思路就是先将需要删除的节点变成红色的。 此时需要考虑的是，如何将红色节点向下移动（向左下或右下）。当左右儿子都不是红色时也不用担心，可以通过颜色翻转实现，翻转后需要考虑移动的另一个方向是否会出现不满足左倾红黑树的情况，并对其进行修补。 由于LLRB的左偏特性，因此会出现想要向右下移动时，左儿子是红色而右儿子是黑色，因此需要对该节点进行右旋，让向右下的路径上出现红色。 当找到删除的目标节点后，如果是一个叶子节点，直接删去，如果是一个内部节点，便从它的右儿子的分支中找到最小节点与之替换，再删掉。 在向上返回的途中修补节点。 4 中判断是否为叶子节点不应该用它是否有左儿子来判断，而是用它是否有右儿子来判断，因为在前一步中有右旋操作。 ...