Oleksii Trekhleb | Javascript algorithms (Heap data-structure)
This is a series of books diving deep into the core mechanisms of the JavaScript language.
· 2 phút đọc.
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.
Time Complexities
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.
Implementation
MaxHeap.js and MinHeap.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).
