binary-heap
Binary heap
npm install binary-heap
Want to see pretty graphs? Log in now!
5 | downloads in the last week |
21 | downloads in the last month |
Last Published By | |
---|---|
Version | 1.1.0 last updated 9 months ago |
License | MIT |
Keywords | heap, binary heap, datastructure, data structure |
Repository | git@github.com:tristanls/node-binary-heap.git (git) |
Bugs | https://github.com/tristanls/node-binary-heap/issues |
Dependencies | None |
Dependents | heap-sort, priority-heap-queue |
binary-heap
Stability: 1 - Experimental
Binary heap.
Installation
npm install binary-heap
Tests
npm test
Usage
var Heap = require('binary-heap');
var heap1 = new Heap();
var heap2 = Heap.build({heap: [3,7,2,1]});
Overview
Documentation
Heap
A JavaScript implementation of a binary heap.
WARNING: This heap implementation uses 1-indexed arrays (instead of 0-indexed) arrays. Therefore, the indexes used in Heap.left(index)
, Heap.right(index)
and others, are assuming that the binary tree representing the heap has a root node at index = 1.
Heap.build(options)
options
Object seenew Heap(options)
documentation
Creates a new Heap and if given options.heap
will ensure that the returned heap satisfies the heap property dictated by options.kind
.
Heap.buildMaxHeap(array, heapSize)
array
Array the 1-indexed array storage for the heap (array[0] will not be modified)heapSize
Integer heap size
Changes the array
in place so that it satisfies max heap property. Returns the resulting array
for convenience.
Heap.buildMinHeap(array, heapSize)
array
Array the 1-indexed array storage for the heap (array[0] will not be modified)heapSize
Integer heap size
Changes the array
in place so that it satisfies min heap property. Returns the resulting array
for convenience.
Heap.left(index)
index
Integer index of a node to find the left child of
Returns the index of the left child for the node at index index
.
WARNING: this method is not safe, invalid input is not checked
Heap.maxHeapify(array, index, heapSize)
array
Array the 1-indexed array storage for the heap (array[0] will not be modified)index
Integer the array index to start maxHeapify procedure onheapSize
Integer heap size
Ensures that the max-heap property is satisfied for the sub-tree rooted at index
of the array representing a binary tree.
Heap.minHeapify(array, index, heapSize)
array
Array the 1-indexed array storage for the heap (array[0] will not be modified)index
Integer the array index to start minHeapify procedure onheapSize
Integer heap size
Ensures that the min-heap property is satisfied for the sub-tree rooted at index
of the array representing a binary tree.
Heap.parent(index)
index
Integer index of a node to find the parent of
Returns the index of the parent for the node at index index
.
WARNING: this method is not safe, invalid input is not checked
Heap.right(index)
index
Integer index of a node to find the right child of
Returns the index of the right child of the node at index index
.
WARNING: this method is not safe, invalid input is not checked
new Heap(options)
options
:heap
: Array An optional array that will be used as initial heap state and not modified to satisfy the heap property.kind
: String One ofmin-heap
,max-heap
(default:max-heap
)
Creates a new Heap.
heap.build()
Builds a max or min heap, depending on the heap kind. Returns the heap for convenience.
heap.dump()
Dumps the present contents of storage used for the heap. The dump may include elements beyond heap size.
heap.maxHeapify(index)
index
Integer index of the node where to begin the procedure
Ensures that the max-heap property is satisfied for the sub-tree rooted at index
.
heap.minHeapify(index)
index
Integer index of the node where to begin the procedure
Ensures that the min-heap property is satisfied for the sub-tree rooted at index
.
heap.size()
Returns heap size.