Heap is a tree-based data structure in which all nodes in the tree are in the specific order. There are 2 types of heap, typically:

- Max Heap: all parent node's values are greater than or equal to children node's values, root node value is the largest.

- Min Heap: all parent node's values are less than or equal to children node's values, root node value is the smallest.

### Basic operations

`insert`

aka`push`

, add a new node into the heap`remove`

aka`pop`

, retrieves and removes the min or the max node of the heap`examine`

aka`peek`

, retrieves, but does not remove, the min or the max node of the heap

### Internal operations

`heapify`

, maintains max or min-heap property (all parent node's values should be greater/less than or equal to the child node's values)

### Implementations

A common implementation of a heap is the binary heap which based on binary tree data structure

You can implement a binary heap with either a static array (capacity restricted) or a dynamic array

### Binary Max Heap implementation example with Static Array

#### Approach

- Represented by 1-based integer array A[N+1]
- With a node A[k] (1<=k<=N)
- Its parent is A[k/2]
- Left child is A[k*2] (k*2 <= N)
- Right child is A[k*2+1] (k*2+1 <= N)

- A[1] is root node, A[0] is
`Integer.MAX_VALUE`

```
```

### Binary Min Heap implementation example with Static Array

#### Approach

- Represented by 1-based integer array A[N+1]
- With a node A[k] (1<=k<=N)
- Its parent is A[k/2]
- Left child is A[k*2] (k*2 <= N)
- Right child is A[k*2+1] (k*2+1 <= N)

- A[1] is root node, A[0] is
`Integer.MIN_VALUE`

```
```

### Applications

Heaps can be used to implement Priority Queues

Find the shortest paths between vertices in a Graph Data Structure

The shortest path is a path between two vertices in a graph such that the total sum of the weights of the constituent edges is minimum

You can implement an algorithm to find the shortest path by using a Min-Heap and Dijkstra algorithm

### Heaps in Java

In Java, the binary heap data structure is used to implement priority queues including java.util.PriorityQueue and java.util.concurrent.PriorityBlockingQueue