By definition, a heap is a specialized tree data structure that supports a heap property. A heap property is defined in such a way that the root of a heap structure will be either smaller or larger than its child nodes. If the parent node is greater than the child nodes, then it is known as max-heap and if the parent node is smaller than the child nodes then it is known as min-heap. The following figure shows an example of max-heap:

If we look at the root node, the value 100 is greater than the two child nodes 19 and 36. Similarly for 19, the value is greater than 17 and 3. It applies the same rule for 36 and 17. As we can see from the tree structure, the tree is not completely sorted or ordered. But the important fact is we can always find the maximum or minimum at the root of the tree, which can be very efficient for many use cases.

There are many variations of heap structure, such as binary heap, b-heap, Fibonacci heap, ternary heap, treap, weak heap, and so on. A Binary heap is one of the most popular for heap implementations. A binary heap is a complete binary tree where all inner levels of the tree are fully filled. The last level can be fully filled or partially filled. Since we are considering a binary heap, we can perform most of our operations in logarithmic time. In this book, we are going to focus on binary heap implementation and operations.