Heaps are an important class of data structures that are used to represent data when we only ever need access to the extreme values. In particular, they allow us O(1) access to the max or min value. In general, a heap is any data structure that exposes the API below:
| Endpoint | Description |
|---|---|
Make Heap |
Creates a new heap |
Insert(x) |
Adds the given item into the heap |
Minimum |
Returns a reference to the smallest element in the heap |
Extract Min |
Remove smallest element and return it |
Union |
Merge the contents of this heap with those of another |
Decrease Key |
Reduce the value of the given key. This changes its position in the heap |
Delete(x) |
Remove the given key from the heap |
The most common kind of heap is the min binary heap. This can be understood conceptually as an almost complete binary tree in which the values of the child nodes are always larger than the value of the parent node. This way, the smallest value is always at the root. The concrete implementation of this data structure is often as an array, with the children of node i at i * 2 and i*2 + 1. Note here that this means that all the nodes in the upper half of the array are leaves