Let H[1...n] be a heap with n elements and val the value must be inserted. The value val will be stored in the heap at position n+1, then the heap will possibly be modified, promoting the value val to the root, until the heap property is restored.