为何基于有序数组实现的Priority Queue的remove min操作是常数时间？

你说的完全在理，这里的核心是有序数组的排序方向：

• 如果采用降序排列的数组（最大值在数组开头，最小值在末尾）：
  • Find min：直接取数组最后一个元素，时间复杂度是O(1)；
  • Remove min：只需要删除数组最后一个元素，根本不用移动其他元素，所以是O(1)的常数时间；
  • Insert：得遍历数组找到合适的插入位置（第一个比新元素小的位置），然后移动后面的元素腾出空间，时间复杂度是Θ(n)。

这正好和你给出的时间复杂度图表对应上。

而你一开始想到的“删索引0元素要移后续元素”的情况，对应的是升序排列的数组（最小值在开头）：

• Find min：同样是O(1)（直接取索引0）；
• Remove min：必须把后面所有元素左移一位补上空位，时间复杂度变成Θ(n)；
• Insert：也要找位置移动元素，时间复杂度Θ(n)。

CS61B第16讲里说的“有序数组实现优先队列时remove min是常数时间”，指的就是降序排列的这种实现——通过调整排序方向，把删除操作放到数组尾部，避开了元素移动的开销。

内容的提问来源于stack exchange，提问作者Foo