PHP - 构建前 k 个项目的排序列表

Question

通过“列表”，我的意思是英语单词，而不是必要的链接列表。您可以使用任何数据结构。但是，PHP对某些数据结构具有内置支持：https://www.php.net/manual/en/spl.datastructures.php 从中最小堆似乎适合我的问题。虽然我不知道如何使用PHP的最小堆设施。

假设一个循环正在从数据库中读取并输出一些用户ID，并且每个用户ID的用户名与输入的单词的相似程度。循环结束后，我想按分数的降序查看前10个用户。分数计算在循环内完成。

对我来说，最简单的方法是：在计算分数（在循环内）时，将所有用户ID及其分数存储在数组中。存储所有分数后，使用PHP的内置排序工具对数组进行排序。显示数组中的前 10 个元素。
但是，当我只想要10个顶级用户时，为什么要打扰（系统）存储和排序所有分数。那么，有什么好方法吗？

我想象的另一个可能的解决方案是这样的，随意忽略：

PS：我对选择所有元素后对顶部k元素进行排序没有问题。

Answer 1

您可以使用最小堆或最小优先级队列（在 PHP 中略有不同）。当该堆具有 k 个元素时，当您找到的条目的分数高于堆中该最小分数时，请交换堆的顶部元素。然后，您最终将获得k个顶部条目，得分最低的位于顶部。因此，作为最后一步，您将从堆中提取条目并反转其顺序。以下是使用SplPriorityQueue的外观。请注意，此结构将最大优先级值放在顶部，因此我们将为其提供负分数，以便在堆/队列顶部获得最低分数：function getTop($input, $k) {&nbsp; &nbsp; $q = new SplPriorityQueue();&nbsp; &nbsp; $q->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY);&nbsp; &nbsp; foreach ($input as $entry) {&nbsp; &nbsp; &nbsp; &nbsp; if ($q->count() < $k) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $q->insert($entry, -$entry["score"]); // negate score to get lower scores first&nbsp; &nbsp; &nbsp; &nbsp; } else if ($entry["score"] > -$q->top() ) { // better score than least in queue? Exchange&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $q->extract();&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; $q->insert($entry, -$entry["score"]);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; $q->setExtractFlags(SplPriorityQueue::EXTR_DATA);&nbsp; &nbsp; return array_reverse(iterator_to_array($q));}下面是一些示例输入数据以及如何调用上述函数：$input = [&nbsp; &nbsp; ["user" => "a", "score" => 17],&nbsp; &nbsp; ["user" => "b", "score" =>&nbsp; 3],&nbsp; &nbsp; ["user" => "c", "score" => 10],&nbsp; &nbsp; ["user" => "d", "score" => 11],&nbsp; &nbsp; ["user" => "e", "score" =>&nbsp; 5],&nbsp; &nbsp; ["user" => "f", "score" => 19],&nbsp; &nbsp; ["user" => "g", "score" =>&nbsp; 7],&nbsp; &nbsp; ["user" => "h", "score" =>&nbsp; 2],&nbsp; &nbsp; ["user" => "i", "score" => 18],&nbsp; &nbsp; ["user" => "j", "score" => 12],&nbsp; &nbsp; ["user" => "k", "score" => 10],&nbsp; &nbsp; ["user" => "l", "score" =>&nbsp; 6],&nbsp; &nbsp; ["user" => "m", "score" =>&nbsp; 9],&nbsp; &nbsp; ["user" => "n", "score" => 15],];$top = getTop($input, 5);print_r($top);

Answer 2

$topMatches = new SplMinHeap();/* Building the list */while($user = mysqli_fetch_assoc($users)){&nbsp;.. calculate score of the $user against the inputted word ..&nbsp;if($topMatches->count() === $k)&nbsp; if($topMatches->top()[0] < $score) //haven't && both if's cause ->top will give error when heap empty&nbsp; &nbsp;$topMatches->extract();&nbsp;if($topMatches->count() !== $k)&nbsp; $topMatches->insert([$score, $user['id']]);}输出上述创建的最小堆：检查其是否为 0。如果是的话.下一个：$topMatchesisEmpty()count()return;do{&nbsp;list($score, $userid) = $topMatches->extract();&nbsp;//echoing}while($topMatches->valid());