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
npm i heap-typed --save
Copy
yarn add heap-typed
Copy
Min Heap
Max Heap
import { MinHeap , MaxHeap } from 'data-structure-typed' ; // /* or if you prefer */ import {MinHeap, MaxHeap} from 'heap-typed'; const minNumHeap = new MinHeap < number >(); minNumHeap . add ( 1 ). add ( 6 ). add ( 2 ). add ( 0 ). add ( 5 ). add ( 9 ); minNumHeap . has ( 1 ) // true minNumHeap . has ( 2 ) // true minNumHeap . poll () // 0 minNumHeap . poll () // 1 minNumHeap . peek () // 2 minNumHeap . has ( 1 ); // false minNumHeap . has ( 2 ); // true const arrFromHeap = minNumHeap . toArray (); arrFromHeap . length // 4 arrFromHeap [ 0 ] // 2 arrFromHeap [ 1 ] // 5 arrFromHeap [ 2 ] // 9 arrFromHeap [ 3 ] // 6 minNumHeap . sort () // [2, 5, 6, 9] 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 ) // true maxHeap . has ( myObj9 ) // false maxHeap . add ( 6 , myObj6 ); maxHeap . has ( myObj6 ) // true maxHeap . add ( 5 , myObj5 ); maxHeap . has ( myObj5 ) // true maxHeap . add ( 2 , myObj2 ); maxHeap . has ( myObj2 ) // true maxHeap . has ( myObj6 ) // true maxHeap . add ( 0 , myObj0 ); maxHeap . has ( myObj0 ) // true maxHeap . has ( myObj9 ) // false maxHeap . add ( 9 , myObj9 ); maxHeap . has ( myObj9 ) // true const peek9 = maxHeap . peek ( true ); peek9 && peek9 . val && peek9 . val . keyA // 'a9' const heapToArr = maxHeap . toArray ( true ); heapToArr . map ( item => item ?. val ?. keyA ) // ['a9', 'a2', 'a6', 'a1', 'a0', 'a5'] 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 // values[i] i ++; }
Copy
const { MinHeap , MaxHeap } = require ( 'data-structure-typed' ); // /* or if you prefer */ const {MinHeap, MaxHeap} = require('heap-typed'); const minNumHeap = new MinHeap (); minNumHeap . add ( 1 ). add ( 6 ). add ( 2 ). add ( 0 ). add ( 5 ). add ( 9 ); minNumHeap . has ( 1 ) // true minNumHeap . has ( 2 ) // true minNumHeap . poll () // 0 minNumHeap . poll () // 1 minNumHeap . peek () // 2 minNumHeap . has ( 1 ); // false minNumHeap . has ( 2 ); // true const arrFromHeap = minNumHeap . toArray (); arrFromHeap . length // 4 arrFromHeap [ 0 ] // 2 arrFromHeap [ 1 ] // 5 arrFromHeap [ 2 ] // 9 arrFromHeap [ 3 ] // 6 minNumHeap . sort () // [2, 5, 6, 9] 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 ) // true maxHeap . has ( myObj9 ) // false maxHeap . add ( 6 , myObj6 ); maxHeap . has ( myObj6 ) // true maxHeap . add ( 5 , myObj5 ); maxHeap . has ( myObj5 ) // true maxHeap . add ( 2 , myObj2 ); maxHeap . has ( myObj2 ) // true maxHeap . has ( myObj6 ) // true maxHeap . add ( 0 , myObj0 ); maxHeap . has ( myObj0 ) // true maxHeap . has ( myObj9 ) // false maxHeap . add ( 9 , myObj9 ); maxHeap . has ( myObj9 ) // true const peek9 = maxHeap . peek ( true ); peek9 && peek9 . val && peek9 . val . keyA // 'a9' const heapToArr = maxHeap . toArray ( true ); heapToArr . map ( item => item ?. val ?. keyA ) // ['a9', 'a2', 'a6', 'a1', 'a0', 'a5'] 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 // values[i] i ++; }
Copy
API Docs
Live Examples
Examples Repository
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
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
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