为什么在未排序数组中实现的优先级队列中的 Find-Minimum 操作只需要 complexity = O(1) ？ <steven skiena's the algorithm design manual>

Question

在 steven skiena 的算法设计手册（第 85 页）中，

作者在 table 中展示了在未排序数组中实现的优先级队列只需要 O(1) 进行插入和查找最小操作。

根据我的理解，未排序的数组无法在 O(1) 中获得最小项，因为它必须搜索整个数组才能获得最小值。

我在优先队列中遗漏了任何细节吗？

Answer 1

它（大部分）写在 table 下：

The trick is using an extra variable to store a pointer/index to the minimum ...

据推测，下一个单词是 "value"，这意味着这是一个简单的 O(1) 解引用以获得最小值。

插入项目时，只需将其附加到末尾，如果小于当前最小值，则更新 pointer/index。这意味着插入 O(1)。

唯一的 "expensive" 操作是最小删除。您知道其中是由于 pointer/index 但需要 O(n) 操作才能将数组元素向下移动一个。

而且，既然成本已经是O(n)，你不妨趁机在数组中搜索新的最小值，并将其位置存储在pointer/index。

这些操作的伪代码类似于（首先，初始化和插入，并假设索引从零开始）：

class prioQ:
    array = []      # Empty queue.
    lowIndex = 0    # Index of lowest value (for non-empty queue).

    def insert(item):
        # Add to end, quick calc if array empty beforehand.

        array.append(item)
        if len(array) == 1:
            lowIndex = 0
            return

        # Adjust low-index only if inserted value smaller than current.

        if array[lowIndex] > item:
            lowIndex = len(array) - 1

然后是求实际最小值的函数：

    def findMin():
        # Empty array means no minimum. Otherwise, return minimum.

        if len(array) == 0: return None
        return array[lowIndex]

最后，提取最小值（将其从队列中移除并return）：

    def extractMin():
        # Empty array means no minimum. Otherwise save lowest value.

        if len(array) == 0: return None
        retVal = array[lowIndex]

        # Shuffle down all following elements to delete lowest one

        for index = lowIndex to len(array) - 2 inclusive:
            array[index] = array[index + 1]

        # Remove final element (it's already been shuffled).

        delete array[len(array) - 1]

        # Find lowest element and store.

        if len(array) > 0:
            lowIndex = len(array) - 1
            for index = len(array) - 2 to 0 inclusive:
                if array[index] <= array[lowIndex]:
                    lowIndex = index

        # Return saved value.

        return retVal

顺便说一句，extractMin 函数 中的两个循环可以 合并为一个以提高效率。为了便于阅读，我将其保留为两个单独的循环。

有一件事你应该记住，实际上有优先级队列的变体保留插入顺序（在优先级内）和不关心该顺序的变体。

对于后一种情况，您不必打乱所有元素来删除提取的元素，只需将数组中的最后一个元素移动到提取的元素上即可。如果您实际上需要保留插入顺序，这可能会节省一些时间 - 您仍然必须扫描整个数组以查找新的最高优先级项目，但至少随机分配的数量将减少。

Answer 2

@paxdiablo的回答给出了书中提到的方案。实现相同复杂度的另一种方法是始终将最小值存储在数组的第一个索引处：

要在O(1)时间内插入x，要么在末尾插入（如果大于当前最小值），要么将当前最小值复制到末尾，然后存储x 在索引 0.
O(1)时间查询最小值，return索引0处的值。
要在O(n)时间内删除最小值，从索引1开始寻找新的最小值，写在索引0处，然后"fill in the gap"交换新的最小值曾经所在的最后一个索引处的元素。

为什么在未排序数组中实现的优先级队列中的 Find-Minimum 操作只需要 complexity = O(1) ？ <steven skiena's the algorithm design manual>

why Find-Minimum operation in priority queue implemented in unsorted array take only complexity = O(1) ? <steven skiena's the algorithm design manual>

priority-queue

data-structures