Reference no: EM134046210

Assignment:

Suppose you have a max heap in which each node stores a distinct integer. Consider the following algorithm which claims to implement the Pop operation, i.e. remove the node of largest value from the heap. Maintain a pointer to the node of largest value, initially at the top of the heap, and recurse downwards. At each stage:

• if the node has two children, swap it with the child of larger value;

• if the node has only one child, swap it with that child;

• if the node has no children, delete it.

1. Demonstrate the execution of the algorithm on a nontrivial example in which it correctly removes the node of largest value from the heap

2. Explain why this algorithm does not correctly implement the Pop operation.