为什么Priority Queue入队（enqueue）时间复杂度是O(log n)？是否存在O(n)情况？

首先明确：你说的情况完全成立——如果队列的enqueue实现需要遍历到队尾才能找到插入位置，那不管是平均还是最坏情况，时间复杂度都是O(n)。

举个具体的例子：如果用普通数组实现队列，却没维护尾指针，每次要加新元素时，都得从数组开头挨个查找，直到找到最后一个有效元素的下一个位置才能插入。就像你给出的代码里，pq = [1,2,3,4]，第一次enqueue(5)得遍历4个元素找到末尾，第二次enqueue(6)得遍历5个元素，这种场景下每次enqueue的时间复杂度确实是O(n)。

但要注意，这只是队列的一种实现方式：

• 如果是链表实现的队列，只要维护了头指针和尾指针，enqueue直接在尾节点后追加新节点，时间复杂度是O(1)，最坏情况也是O(1)。
• 如果是带尾指针的数组队列，平时enqueue直接在尾指针位置插入，时间复杂度O(1)；只有当数组满了需要扩容时，才会出现一次O(n)的情况（因为要把原数组所有元素复制到新数组），但这种扩容操作是均摊到多次enqueue上的，不过严格按最坏情况算，确实存在O(n)的可能，但这和你说的“遍历到队尾找插入位置”不是一回事。

总结：你的疑问是对的——当enqueue操作必须通过遍历找到队尾才能插入时，最坏时间复杂度就是O(n)。

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