Read this in other languages: 简体中文, Русский, 日本語, Français, Português, Türkçe, 한국어, Українська
In computer science, a heap is a specialized tree-based data structure that satisfies the heap property described below.
In a min heap, if P is a parent node of C, then the
key (the value) of P is less than or equal to the
key of C.
Made with okso.app
In a max heap, the key of P is greater than or equal
to the key of C
The node at the "top" of the heap with no parents is called the root node.
Here are time complexities of various heap data structures. Function names assume a max-heap.
| Operation | find-max | delete-max | insert | increase-key | meld |
|---|---|---|---|---|---|
| Binary | Θ(1) |
Θ(log n) |
O(log n) |
O(log n) |
Θ(n) |
| Leftist | Θ(1) |
Θ(log n) |
Θ(log n) |
O(log n) |
Θ(log n) |
| Binomial | Θ(1) |
Θ(log n) |
Θ(1) |
O(log n) |
O(log n) |
| Fibonacci | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| Pairing | Θ(1) |
Θ(log n) |
Θ(1) |
o(log n) |
Θ(1) |
| Brodal | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| Rank-pairing | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| Strict Fibonacci | Θ(1) |
Θ(log n) |
Θ(1) |
Θ(1) |
Θ(1) |
| 2-3 heap | O(log n) |
O(log n) |
O(log n) |
Θ(1) |
? |
Where:
- find-max (or find-min): find a maximum item of a max-heap, or a minimum item of a min-heap, respectively (a.k.a. peek)
- delete-max (or delete-min): removing the root node of a max heap (or min heap), respectively
- insert: adding a new key to the heap (a.k.a., push)
- increase-key or decrease-key: updating a key within a max- or min-heap, respectively
- meld: joining two heaps to form a valid new heap containing all the elements of both, destroying the original heaps.
In this repository, the MaxHeap.js and MinHeap.js are examples of the Binary heap.
- MaxHeap.js and MinHeap.js
- MaxHeapAdhoc.js and MinHeapAdhoc.js - The minimalistic (ad hoc) version of a MinHeap/MaxHeap data structure that doesn't have external dependencies and that is easy to copy-paste and use during the coding interview if allowed by the interviewer (since many data structures in JS are missing).