Priority queue

This structure lets you add an element with a priority, and it lets you extract the highest-priority element. Both of these operations take $O(\log n)$ time. It's implemented with a min-heap (supposing min value is the highest priority). (A max-heap is analogous.) It's a binary tree whose keys do not decrease in value as you descend from root to leaf, so the min is at the root. We will maintain a balanced tree; all levels but the last must be complete.

To add a value, we try to add it in the next empty position in the tree, reading from top to bottom and left to right. Then as long as it's smaller than its parent, we “heapify-up” by swapping the node and its parent. We repeat this as needed $O(\log n)$ times until the heap is valid. (Heapify-up never violates the “other” branch, if you think about it.)

On the other hand, after removing any node, we fill in that place with the “last” node in the tree. If it's too small, we heapify-up as before. If it's too large, we heapify-down in a similar fashion. In this case we want to swap the node with the smaller of its two children, in order not to cause a problem with the other branch. Again, repeat as needed $O(\log n)$ times.

That's about it. Oh, and of course, to pick the smallest element, you just pull it off the top and follow the same procedure to repair the heap as if you had deleted any other node.