,data-structures,priority-queue"/>
时间戳

首页 > 解决方案 > 为什么在未排序数组中实现的优先级队列中的 Find-Minimum 操作只需要复杂度 = O(1) ？

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

问题描述

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

作者在一个表中显示，在未排序数组中实现的优先级队列只需要 O(1) 进行插入和查找最小操作。 优先队列分析 - steven skiena 的算法设计手册

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

有没有我在优先队列中错过的任何细节？

标签： data-structurespriority-queue

解决方案

它（大部分）写在桌子下面：

诀窍是使用一个额外的变量将指针/索引存储到最小值......

大概，下一个词是“价值”，这意味着它是一个简单的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顺便说一句，为了提高效率，函数中的两个循环可以合并为一个。为了便于阅读，我将其保留为两个单独的循环。

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

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

推荐阅读