Reading material

Chapter 6 from Section 6.3 up to Section 6.3.4.

Additional material

Completeness property: Let h be the height of of the binary tree. All levels 0, 1, ..., h-1 have the maximum number of nodes and at level h all missing leaves are to the right of all the leaves that are present.

Assume we have the following heap.

Removing the minimal element takes the following steps.

Inserting an element with key 8 takes the following steps.