We define a Delete-Insert-Stable (DIS) heap as a heap with no duplicate elements where the result of extracting the root element and immediately re-inserting that element is the original heap.

1. Provide an example of a DIS max heap with seven elements. Display both the original heap (which is of course also the final heap) and the intermediate heap (after the call to ExtractMax) as trees.

2. Provide an example of a max heap with seven distinct elements that is not a DIS heap. Display the original heap, the intermediate heap and the final heap all as trees.

3. Formally describe the relationship between the elements that must hold for a heap to be a DIS max heap.

4. Prove that your description in part (c) describes all DIS max heaps and does not hold for max heaps that are not DIS.