1
$\begingroup$

Let $T$ be a max heap tree with no duplicate values amongst the nodes. When does $T$ satisfy the following.

  1. Remove the root, and restructure the tree to satisfy the heap property.
  2. Reinsert the root, and restructure the tree to satisfy the heap property.

After 1, and 2, the resulting heap is exactly the same as the original heap. I'm trying to the exact condition that a max heap $T$ must have in order to satisfy this invariant property. i.e. a condition $\phi$ such that $T$ satisfies $\phi$ if and only if it is invariant after steps 1 and 2.

$\endgroup$
1
  • 1
    $\begingroup$ Please don't delete questions after you've received a good answer. Part of our mission here is to build up an archive of high-quality questions and answers that will be useful not only to you but also to others in the future. Answerers may have responded on that basis, so it might be considered impolite to delete your question after receiving an answer. $\endgroup$
    – D.W.
    Feb 7, 2022 at 19:17

1 Answer 1

1
$\begingroup$

Start with the second step. When a large number is added as the last leaf to the (binary) heap, all elements on the path from the leaf to the root are swapped. Hence the first step (removing the maximum) must be like that, but in reverse.

$\endgroup$
2
  • $\begingroup$ So I understand intuitively that the node swaps must be reversible exactly to preserve $T$. But how would you state a precise general condition for $T$? $\endgroup$
    – user7828
    Jan 31, 2022 at 21:20
  • $\begingroup$ When the root (maximum) is removed, its place is taken by the last element, which is then moved down in the heap by swapping with the largest child. So, in order to reverse this proces after reintroducing the old maximum it seems the largest child must be on the path to the last leaf. That property can be expressed as a ordering of keys on that path. (This is my intuition, not a full proof.) $\endgroup$ Feb 1, 2022 at 11:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.