algorithm - 这是什么排序算法，它是如何工作的？ (如果没有名称或知名资源。)

Question

我上 DSA 课已经将近十年了。我已经看过 Wikipedia's list of sorting algorithms但没有一个脱颖而出。它是优先级队列实现的一部分，似乎部分排序发生在推送函数 (EnQueue) 中，而另一部分发生在弹出函数 (DeQueue) 中。

这是原始的 Mathematica 代码，但由于大多数人不熟悉 Mathematica，我在每个函数下面做了一些翻译。

EnQueue[q : queue[ar_, n_, pred_], val_] := Module[{i, j},
  If[n == Length[ar], ar = Join[ar, makeArray@Length@ar]];
  n++; ar[[n]] = val;
  i = n;
  While[True,
   j = Quotient[i, 2];
   If[j < 1 || pred[ar[[j]], ar[[i]]],
    Break[]
    ];
   ar[[{i, j}]] = {ar[[j]], ar[[i]]};
   i = j;
   ];
  q
  ]

EnQueue函数首先检查元素的数量是否为 n已达到堆的大小ar ，如果是这样，则将堆加倍。接下来，它增加元素的数量并将新元素存储在该索引处(Mathematica 索引是从 1 开始的，而不是从 0 开始的)。然后，它设置 i到该索引(新元素的)，并进入一个设置 j 的循环至 floor(i/2) ，即堆中间的某个元素。现在，如果j < 1 (这相当于检查是否 i == 1 ，据我所知)，或者如果 ar[j] (中间的元素)应该在ar[i]之前(新元素)，然后我们打破。否则，我们交换 i 处的元素和 j ，并继续；所以在第二次迭代中，我们从 i 开始指向中间，和j指向四分之一路。

DeQueue[queue[ar_, n_, pred_]] := 
 Module[{i, j, res = ar[[1]]},
  ar[[1]] = ar[[n]]; ar[[n]] = Null; n--;
  j = 1;
  While[j <= Quotient[n, 2],
   i = 2 j;
   If[i < n && pred[ar[[i + 1]], ar[[i]]],
    i++
    ];
   If[pred[ar[[i]], ar[[j]]],
    ar[[{i, j}]] = {ar[[j]], ar[[i]]};
    ];
   j = i];
  res]

与此同时，DeQueue返回堆的前面，并将堆的 后面 移到前面(并取消设置后面，并减少元素的数量)。然后，从 j 开始指向前方，它进入一个循环，该循环从设置 i 开始。加倍j . 如果i在边界内(指向一个元素)但对于下一个元素来说是乱序的，i递增。如果i关于 j 是有序的(前面；换句话说，如果前面 out 相对于 i )，则交换两个位置，并且 j设置到位置i在。我们继续循环直到 j通过中间。

主要是上面加粗的部分我没看懂。我认为它正在做的是对DeQueue 上的一半 堆进行排序。 ，并对 EnQueue 中的新元素进行部分排序, 但我不确定...

Answer 1

入队对我来说似乎是一个最小堆例程
https://en.wikipedia.org/wiki/Heap_(data_structure)
https://en.wikibooks.org/wiki/Data_Structures/Min_and_Max_Heaps

Dequeue 移除堆的顶部项，它存储在数组的第一项中，然后用数组的最后一项替换它并向下筛选堆，每次与 child 交换它只要一个 child 比该项目小(并且比它的 sibling 小，如果它有的话)。当没有更小的 child 时停止，即当项目到达堆底或它小于它的 child (或 child ，它只有一个)。

编辑:“入队”和“出队”这两个词表明它是一个队列。该算法是在数组中实现的二进制堆，因此这是一个优先级队列。