PQ -- insert ( )

The insert operation must maintain

• Heap Shape ( the Complete Binary Tree property )
  
      Insert the new element at the right end of the array
  
  
• Heap Order ( partial ordering )
  
      Maintaining Heap Shape could violate Heap Order
  
      Continuously swap the new element with it's parent until
      the parent is not greater than it.  ("shift up" or "percolate up")