What
Brief
This is a standalone Heap data structure from the data-structure-typed collection. If you wish to access more data
structures or advanced features, you can transition to directly installing the
complete data-structure-typed package
How
install
npm
npm i heap-typed
yarn
yarn add heap-typed
methods
Min Heap
Max Heap
snippet
TS
import {MinHeap, MaxHeap} from 'data-structure-typed';
const minNumHeap = new MinHeap<number>();
minNumHeap.add(1).add(6).add(2).add(0).add(5).add(9);
minNumHeap.has(1)
minNumHeap.has(2)
minNumHeap.poll()
minNumHeap.poll()
minNumHeap.peek()
minNumHeap.has(1);
minNumHeap.has(2);
const arrFromHeap = minNumHeap.toArray();
arrFromHeap.length
arrFromHeap[0]
arrFromHeap[1]
arrFromHeap[2]
arrFromHeap[3]
minNumHeap.sort()
const maxHeap = new MaxHeap<{ keyA: string }>();
const myObj1 = {keyA: 'a1'}, myObj6 = {keyA: 'a6'}, myObj5 = {keyA: 'a5'}, myObj2 = {keyA: 'a2'},
myObj0 = {keyA: 'a0'}, myObj9 = {keyA: 'a9'};
maxHeap.add(1, myObj1);
maxHeap.has(myObj1)
maxHeap.has(myObj9)
maxHeap.add(6, myObj6);
maxHeap.has(myObj6)
maxHeap.add(5, myObj5);
maxHeap.has(myObj5)
maxHeap.add(2, myObj2);
maxHeap.has(myObj2)
maxHeap.has(myObj6)
maxHeap.add(0, myObj0);
maxHeap.has(myObj0)
maxHeap.has(myObj9)
maxHeap.add(9, myObj9);
maxHeap.has(myObj9)
const peek9 = maxHeap.peek(true);
peek9 && peek9.val && peek9.val.keyA
const heapToArr = maxHeap.toArray(true);
heapToArr.map(item => item?.val?.keyA)
const values = ['a9', 'a6', 'a5', 'a2', 'a1', 'a0'];
let i = 0;
while (maxHeap.size > 0) {
const polled = maxHeap.poll(true);
polled && polled.val && polled.val.keyA
i++;
}
JS
const {MinHeap, MaxHeap} = require('data-structure-typed');
const minNumHeap = new MinHeap();
minNumHeap.add(1).add(6).add(2).add(0).add(5).add(9);
minNumHeap.has(1)
minNumHeap.has(2)
minNumHeap.poll()
minNumHeap.poll()
minNumHeap.peek()
minNumHeap.has(1);
minNumHeap.has(2);
const arrFromHeap = minNumHeap.toArray();
arrFromHeap.length
arrFromHeap[0]
arrFromHeap[1]
arrFromHeap[2]
arrFromHeap[3]
minNumHeap.sort()
const maxHeap = new MaxHeap();
const myObj1 = {keyA: 'a1'}, myObj6 = {keyA: 'a6'}, myObj5 = {keyA: 'a5'}, myObj2 = {keyA: 'a2'},
myObj0 = {keyA: 'a0'}, myObj9 = {keyA: 'a9'};
maxHeap.add(1, myObj1);
maxHeap.has(myObj1)
maxHeap.has(myObj9)
maxHeap.add(6, myObj6);
maxHeap.has(myObj6)
maxHeap.add(5, myObj5);
maxHeap.has(myObj5)
maxHeap.add(2, myObj2);
maxHeap.has(myObj2)
maxHeap.has(myObj6)
maxHeap.add(0, myObj0);
maxHeap.has(myObj0)
maxHeap.has(myObj9)
maxHeap.add(9, myObj9);
maxHeap.has(myObj9)
const peek9 = maxHeap.peek(true);
peek9 && peek9.val && peek9.val.keyA
const heapToArr = maxHeap.toArray(true);
heapToArr.map(item => item?.val?.keyA)
const values = ['a9', 'a6', 'a5', 'a2', 'a1', 'a0'];
let i = 0;
while (maxHeap.size > 0) {
const polled = maxHeap.poll(true);
polled && polled.val && polled.val.keyA
i++;
}
API docs & Examples
API Docs
Live Examples
Examples Repository
Data Structures
Why
Complexities
performance of Big O
Big O Notation | Type | Computations for 10 elements | Computations for 100 elements | Computations for 1000 elements |
---|
O(1) | Constant | 1 | 1 | 1 |
O(log N) | Logarithmic | 3 | 6 | 9 |
O(N) | Linear | 10 | 100 | 1000 |
O(N log N) | n log(n) | 30 | 600 | 9000 |
O(N^2) | Quadratic | 100 | 10000 | 1000000 |
O(2^N) | Exponential | 1024 | 1.26e+29 | 1.07e+301 |
O(N!) | Factorial | 3628800 | 9.3e+157 | 4.02e+2567 |
Data Structure Complexity
Data Structure | Access | Search | Insertion | Deletion | Comments |
---|
Array | 1 | n | n | n | |
Stack | n | n | 1 | 1 | |
Queue | n | n | 1 | 1 | |
Linked List | n | n | 1 | n | |
Hash Table | - | n | n | n | In case of perfect hash function costs would be O(1) |
Binary Search Tree | n | n | n | n | In case of balanced tree costs would be O(log(n)) |
B-Tree | log(n) | log(n) | log(n) | log(n) | |
Red-Black Tree | log(n) | log(n) | log(n) | log(n) | |
AVL Tree | log(n) | log(n) | log(n) | log(n) | |
Bloom Filter | - | 1 | 1 | - | False positives are possible while searching |
Sorting Complexity
Name | Best | Average | Worst | Memory | Stable | Comments |
---|
Bubble sort | n | n2 | n2 | 1 | Yes | |
Insertion sort | n | n2 | n2 | 1 | Yes | |
Selection sort | n2 | n2 | n2 | 1 | No | |
Heap sort | n log(n) | n log(n) | n log(n) | 1 | No | |
Merge sort | n log(n) | n log(n) | n log(n) | n | Yes | |
Quick sort | n log(n) | n log(n) | n2 | log(n) | No | Quicksort is usually done in-place with O(log(n)) stack space |
Shell sort | n log(n) | depends on gap sequence | n (log(n))2 | 1 | No | |
Counting sort | n + r | n + r | n + r | n + r | Yes | r - biggest number in array |
Radix sort | n * k | n * k | n * k | n + k | Yes | k - length of longest key |