Glossary

Elements in a binary heap are stored in a complete binary tree, namely, a binary tree in which each level is filled in from left to right, and must be full before the next level is started. In addition, a special ordering constraint is enforced: the key value of any node of the tree is less than or equal to that of its children. In particular, therefore, the root always contains the smallest element.

To insert an element, place the new element at the bottom of the tree (in the first available position), and let it “bubble up.” That is, if it is smaller than its parent, swap the two and repeat. The number of swaps is at most the height of the tree, which is $\lceil \log_2 n \rceil$ when there are $n$ elements.

Decreasing a key of an element of a binary heap is similar, except that the element is already in the tree, so we let it bubble up from its current position.

To delete the minimum element from a binary heap, return the root value. To then remove this element from the heap, take the last node in the tree (in the rightmost position in the bottom row) and place it at the root. Let it “sift down”: if it is bigger than either child, swap it with the smaller child and repeat. Again this takes $O(\log n)$ time.

Source: Algorithms by Dasgupta, Papadimitriou, Vazirani. McGraw-Hill. 2006.

Visualization of min heap by David Galles: http://www.cs.usfca.edu/~galles/visualization/Heap.html.