Priority Queue using just array and binary search

Question

So I have come across priority queue data structure, the implementation is usually with heaps or binary tree.

Why can't a priority queue just use a simple array and use binary search for insertion, it would still be O(logn) with retrieval time of O(1).

while true {
    // We will eventually reach the search with only two or less elements remaining.
    // The insert can be in front of (first element index), between (second element index)
    // or behind of the two element (second element index + 1).
    //
    // The lowerBound is the first element index if the first element (aka middle) has a 
    // higher priority than the insert priority (last call is upperBound = middle - 1 so 
    // lowerBound unchange)
    //
    // The lowerBound will be the second element index if the first element (aka middle) 
    // has a lower priority than the insert priority (last call is lowerBound = middle + 1)
    //
    if lowerBound >= upperBound {
        // We still need to check if lowerBound is now in the second element, in which it can also 
        // be greater than priority of the second element. If so, we need to add 1 to the index 
        // (lowerBound)
        return array[lowerBound].priority > insert.priority ? lowerBound : lowerBound + 1
    }

    var middle = (lowerBound + upperBound) / 2
    let middleValue = array[middle]

    if middleValue.priority > insert.priority {
        upperBound = middle - 1
    } else { // treat equal as less than so it put the same priority in order of insertion
        lowerBound = middle + 1
    }
}

user395760 · Accepted Answer · 2015-02-26 15:10:02Z

3

Your loop, the binary search, only finds the index at which the new item should be inserted to maintain sorted order. Actually inserting it there is the hard part. Simply put, this takes linear time and there's nothing we can do about that. A sorted array is very fast for retrieval, but pretty slow for insertion. Binary heaps are fast (logarithmic) for both insertion and retrieval.

answered Feb 26, 2015 at 15:10

user395760

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Priority Queue using just array and binary search

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related