What are heaps? Viewed abstractly, heaps are nearly complete binary trees (every level is filled completely except possible for the bottom level which is filled from the left up to a point) which satisfy the heap property: every node has a key which is greater than or equal to the key of its parent.
- To find the minimum, just look at the root.
- To remove the minimum, replace it with the last key x (the one in the rightmost node of the bottom level; that node is removed), and once x is at the root, repeatedly swap x with the smaller of its two children until the heap property is satisfied.
- To insert a new value y, just add a node to the tree, at the first available spot (the leftmost non-existent node at the bottom level), put y in it, and repeatedly swap y with its parent until the heap property is satisfied.