3.1. Heap Operations: Insert and Delete

An important consequence of the ordering property (every node is smaller than the values in its subtrees) is that every path in a heap is a sorted list. Have a close look at the example above to convince yourself of this.

This property is the key to efficient insertion and deletion. These operations on heaps will be almost identical to the corresponding operations on sorted lists!