Insertion (heap)

Insertion: consider inserting entry $(k,x)=(1,S)$ to the priority queue implement with a heap $T$. The insertion algorithm (insert(k,x)) is as follows:

• Add a node $z$ to $T$ with operation add so that this new node becomes the last node of $T$ and stores entry $(k,x)$.
• Restore the heap-order property that may be violated by the previous action.