A Heap is a binary tree such that:
Ordering property: The value in a node is smaller than all the values in the node's subtrees.
Structural Property: All the levels all full, except perhaps the bottom level, and all the nodes are as far to the left as possible.
Complete Trees: Height = O(logN), resulting in O(logN) operations
Examples (only 1 is a heap):
How about this:
