A heap is a binary tree that uses comparison methods to store items so they can be quickly retrieved in sorted order. However, the items of a heap are not fully sorted.

In a heap, the value of any parent must be greater than any of it’s child values. This means a heap is only ordered vertically (not horizontally like in AVL or Red-Black trees). Vertical-only sorting allows a heap to quickly add items in any order, but remove values based on a priority. The algorithms for maintaining vertical sorting are usually refered to as “Sifting Up” and “Sifting Down.”