1

自从我参加 DSA 课程以来，已经快十年了。我浏览了Wikipedia 的排序算法列表，但没有一个比这更突出。它是优先级队列实现的一部分，似乎排序的一部分发生在 push 函数 ( EnQueue) 中，而另一部分发生在 pop 函数中 (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（据我所知，这相当于检查 if 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为 double开始的循环j。如果i在边界内（指向一个元素）但相对于下一个元素是无序的，i则递增。如果i相对于j（前部；换句话说，如果前部相对于 ）是有序的，i则交换两个位置，并j设置为所在的位置i。我们继续循环，直到j经过中间。

大部分是上面的粗体部分我不明白。我认为它正在做的是对一半的堆进行排序DeQueue，并为 中的新元素做一些排序EnQueue，但我不确定......

4

1 回答 1

4

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

出队移除堆的顶部项目，该项目存储在数组的第一项中，然后将其替换为数组的最后一项并将其从堆中筛选出来，每次只要有孩子就与孩子交换小于该项目（并且小于其兄弟，如果它有一个）。当没有更小的孩子时停止，即当项目到达堆底部或它小于它的孩子（或孩子，它只有一个）。

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

于 2015-03-20T14:28:55.340 回答