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

Question

In steven skiena's the algorithm design manual (page 85),

The author show in a table that priority queue implemented in unsorted array only take O(1) for both insertion and find minimum operation.

For my understanding unsorted array wasn't able get the minimum item in O(1) , because it has to search through the whole array to get the minimum.

is there any details i missed out in priority queue ?

Answer 1

It's (mostly) written there under the table:

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

Presumably, the next word is "value", meaning it's a simple O(1) dereference to get the minimum.

When inserting an item, you just append it to the end and, if it's less than the current minimum, update that pointer/index. That means O(1) for the insert.

The only "expensive" operation is then delete-minimum. You know where it is due to the pointer/index but it will take O(n) operations to shuffle the array elements beyond it down one.

And, since the cost is already O(n), you may as well take the opportunity to search the array for the new minimum and store its position in the pointer/index.

---

The pseudo-code for those operations be something along the lines of (first up, initialisation and insertion, and assuming zero-based indexes):

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

Then a function to find the actual minimum value:

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

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

And, finally, to extract the minimum value (remove it from the queue and return it):

    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

As an aside, the two loops in the extractMin function could be combined in to one for efficiency. I've left it as two separate loops for readability.

---

One thing you should keep in mind, there are actually variations of the priority queue that preserve insertion order (within a priority level) and variations that do not care about that order.

For the latter case, you don't have to shuffle all the elements to remove an extracted one, you can simply move the last one in the array over the extracted one. This may result in some time savings if you don't actually need to preserve insertion order - you still have to scan the entire array looking for the new highest-priority item but at least the number of shuffle assignments will be reduced.