仅使用数组和二进制搜索的优先级队列

Question

所以我接触到了优先级队列这个数据结构，一般都是用堆或者二叉树来实现的。

为什么优先队列不能只用一个简单的数组，用二分查找插入，还是O(logn)，检索时间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
    }
}

Answer 1

您的循环，即二分查找，只找到索引应该插入新项目以保持排序顺序。实际上将它插入那里是困难的部分。简而言之，这需要线性时间，我们对此无能为力。排序数组的检索速度非常快，但插入速度非常慢。二进制堆的插入和检索速度都很快（对数）。

仅使用数组和二进制搜索的优先级队列

Priority Queue using just array and binary search

queue

priority-queue

binary-search

data-structures