算法复杂度计算：首个while循环的复杂度是O(n)还是O(logn)？

Hey there! Let's break this down clearly:

首先要敲个警钟：你的第一个while循环的查找逻辑是有bug的——它只沿着「最后一个元素→根节点」的这条路径向上查找，但堆是个完全二叉树，符合(value, oldPriority)的元素完全可能在其他分支上，这会导致明明元素存在，代码却错误地抛出"元素不存在"的异常。

回到你最关心的复杂度问题：

• 从代码的执行流程看，这个循环每次迭代都会让i跳到当前节点的父节点，而堆的高度是O(logn)（n个节点的完全二叉树高度是⌊log₂n⌋+1），所以这个循环最多只会执行O(logn)次，每一步都是O(1)的操作，因此这个循环的时间复杂度是O(logn)。
• 哪怕目标元素不在这条路径上，循环也只会走到根节点就停止，此时复杂度依然是O(logn)——只是这种情况下代码会误判元素不存在而已。

为什么查找逻辑不对？ #

堆的核心特性是「父节点优先级优于子节点」（大顶/小顶堆的区别），但它不保证同一层级、不同分支的节点有任何顺序关系。举个例子：你要找的元素可能在左子树的某个节点上，但你的循环从最后一个元素（可能在右子树最底层）开始往上走，根本不会遍历到左子树的节点，自然找不到目标。

如果要正确查找元素该怎么做？ #

如果要确保找到堆中任意符合条件的元素，你得遍历整个堆（比如用递归遍历左右子树，或者迭代遍历所有索引），这种情况下查找的时间复杂度就是O(n)——毕竟堆的设计初衷不是快速查找任意元素，而是快速获取极值和调整结构。

附上你的代码便于参考：

public void increasePriority(T value, int oldPriority, int newPriority) throws PriorityQueueException { 
    if (c.compare(oldPriority, newPriority) > 0) 
        throw new PriorityQueueException("The new priority is lower than the current one"); 
    int i = getSize() - 1; 
    while (i > 0 && !(queue.get(i).getPriority() == oldPriority && queue.get(i).getValue() == value)) { 
        i = getParent(i); 
    } 
    if (i == 0) 
        throw new PriorityQueueException("Element (" + value + "," + oldPriority +") doesn't exits in the queue"); 
    queue.get(i).setPriority(newPriority); 
    while (i > 0 && c.compare(queue.get(i).getPriority(), queue.get(getParent(i)).getPriority()) > 0) { 
        swap(i, getParent(i)); 
        i = getParent(i); 
    } 
}

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