Storing information in a way that is quick to retrieve, add, and search on, is a very important technique to master. Here is what you need to know about heap data structures:

Heaps | Heapify | Find Max | Extract Max | Increase Key | Insert | Delete | Merge |
---|---|---|---|---|---|---|---|

Sorted Linked List | - | O(1) | O(1) | O(n) | O(n) | O(1) | O(m+n) |

Unsorted Linked List | - | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) |

Binary Heap | O(n) | O(1) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(m+n) |

Binomial Heap | - | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) |

Fibonacci Heap | - | O(1) | O(log(n))* | O(1)* | O(1) | O(log(n))* | O(1) |