data-structures - 为什么在未排序数组中实现的优先级队列中的 Find-Minimum 操作只需要复杂度 = O(1) ？

Question

在 stevenskiena 的算法设计手册(第 85 页)中，

作者在表格中展示了在未排序数组中实现的优先级队列，插入和查找最小操作都只需要 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)取消引用以获得最小值。

插入项目时，您只需将其附加到末尾，如果它小于当前最小值，则更新该指针/索引。这意味着 O(1)为插入。

唯一的“昂贵”操作是删除最小操作。由于指针/索引，你知道它在哪里，但它需要 O(n)操作将超出它的数组元素打乱一个。

并且，由于成本已经是 O(n) ，您也可以借此机会在数组中搜索新的最小值并将其位置存储在指针/索引中。

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

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]

最后，提取最小值(将其从队列中移除并返回):

    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 中的两个循环功能可以合二为一以提高效率。为了便于阅读，我将其保留为两个单独的循环。

您应该记住的一件事是，实际上优先级队列的变体保留了插入顺序(在优先级内)和不关心该顺序的变体。

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