A Heap is a special Tree-based data structure which is an almost complete tree that satisfies the heap property:
- in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C.
- In a min heap, the key of P is less than or equal to the key of C. The node at the “top” of the heap (with no parents) is called the root node.
A common implementation of a heap is the binary heap, in which the tree is a binary tree.