0
$\begingroup$

Does finding the successor of an element in a heap take $O(\log n)$?

An heap is not a binary search tree, so couldn't an element's successor be found in $O(n)$ time?

$\endgroup$
1
  • 1
    $\begingroup$ In my opinion, finding an arbitrary element takes O(n) time in both a mini-heap and a max-heap $\endgroup$
    – Elidor00
    Mar 19 at 21:59
0
$\begingroup$

Suppose you have a min heap $H$, and you want to find successor one of the leaf node that its successor is maximum value, so you need to scan all leaves in tree, in addition we know that number of leaves in $H$ is $O(n)$. So you need read $O(n)$ nodes.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy