Heap: Is an Abstract Data structure that allows a set of operations that must be supported (such as insert, delete, and extract-min/max).
Disclaimer: A heap can be viewed as both a data structure and an ADT. For now we are viewing it as an ADT—the underlying implementation is not specified.
A sorted array can be used to implement the ADT heap (max/min), certain operations will have a higher time complexity, but every insert and delete operation will require us to sort the entire array, resulting in a time complexity of nlogn.
heap= [
10
9
8
7
6
5
4
3
2
1
]
To efficiently perform operations such as extracting max/min, insertions, and deletions, we typically use a binary tree as the underlying structure. Since we only need to have the correct location of the max/min, we don’t need to sort the whole set of values. This brings us to the point that a heap is not a sorted structure. It is partially sorted, requiring only that the max or min element is at the top of the heap. Sacrificing the whole sortedness for only the max/min facilitated by a binary tree allows us to perform all heap operations in log(n). (Why log(n) will talk in the sections below).
Representing heaps as binary trees requires us to satisfy two conditions: