时间戳

首页 > 解决方案 > 在跳过列表中查找第 k 个元素 - 需要解释

algorithm - 在跳过列表中查找第 k 个元素 - 需要解释

问题描述

我们正在我的大学学习跳过列表，我们必须在跳过列表中找到第 k 个元素。我在互联网上没有找到任何关于此的信息，因为 skiplist 并不是一个真正流行的数据结构。W. Pugh 在他的原始文章中写道：
每个元素 x 都有一个索引 pos(x)。我们在不变量中使用这个值，但不存储它。标头的索引为零，第一个元素的索引为一，依此类推。与每个前向指针相关联的是该指针经过的距离的测量值 fDistance：
x→fDistance[i] = pos(x→forward[i]) – pos(x)。
请注意，级别 1 指针所经过的距离始终为 1，因此此处可能会节省一些存储空间，但代价是算法复杂度略有增加。 

SearchByPosition(list, k)
if k < 1 or k > size(list) then return bad-index
    x := list→header
    pos := 0
    -- loop invariant: pos = pos(x)
    for i := list→level downto 1 do
        while pos + x→fDistance[i] ≤ k do
            pos := pos + x→fDistance[i]
            x := x→forward[i]
return x→value

问题是，我仍然不明白这里发生了什么。我们如何知道元素的位置而不存储它们？如果我们不存储它，我们如何从 pos(x) 计算 fDistance？如果我们从跳过列表的最高层开始，我们如何知道第 0 层（或 1，无论如何是最低的）有多少节点以这种方式跳过？

标签： algorithmskip-lists

解决方案

我将假设您指的是如何k在跳过列表中找到 -th 最小（或最大）元素。我认为这是一个相当标准的假设，否则你必须澄清你的意思。

我将在此答案中参考维基百科上的 GIF：https ://en.wikipedia.org/wiki/Skip_list

在此处输入图像描述

假设您想找到k = 5最小的元素。

您从最高级别（图中的 4）开始。你会从多少个元素30跳到NIL？6（我们也算30）。这太多了。

下一层。从 跳到 有30多少50​​？2:30和40。

所以我们将问题简化为从level开始寻找k = 5 - 2 = 3最小的元素。503

从 跳到 有50多少NIL​​？4，这太多了。

下一层。从 跳到 有50多少70​​？2. 现在找到3 - 2 = 1从70level开始的最小元素2。

从 跳到 有70多少NIL​​？2，一个太多了。

从70到90水平1? 1（本身）。所以答案是70。

因此，您需要存储每个级别的每个节点跳过了多少节点，并使用这些额外信息来获得有效的解决方案。这似乎是fDistance[i]您的代码中所做的。

推荐阅读