Mheap

<h1 align="center"> Mheap </h1> <h4 align="center"> Binary min & max heaps for ES6 </h4> <p align="center"> <a href="https://travis-ci.com/klaussinani/mheap"> <img alt="Build Status" src="https://travis-ci.com/klaussinani/mheap.svg?branch=master"> </a> <a href='https://coveralls.io/github/klaussinani/mheap?branch=master'> <img alt="Coverage Status" src="https://coveralls.io/repos/github/klaussinani/mheap/badge.svg?branch=master"> </a> </p>

Description

ES6 implementation of the binary min & max heap data structures with TypeScript support.

Visit the contributing guidelines to learn more on how to translate this document into more languages.

Contents

• Description
• Install
• In Depth
• Usage
• API
• Development
• Related
• Team
• License

Install

Yarn

yarn add mheap

NPM

npm install mheap

In Depth

A binary heap is a heap data structure that takes the form of a binary tree, defined with two additional constraints:

• Shape property: A binary heap is a complete binary tree, that is all levels, except possibly the last one / deepest are fully filled, and if the last level of the tree is not complete, the nodes of that level are filled from left to right.

• Heap property: The key stored in each node is either greater than or equal to or less than or equal to the keys in the node's children, according to the maximum & minimum total orders, respectively.

Heaps, where the parent key is greater than or equal to the child keys are called max-heaps, and those where it is less than or equal to are called min-heaps.

Mheap binary min & max heaps are internally implemented with an array, where nodes are stored by the level order traversal of the heap and the root node is always placed at index 0. This is due to the fact that any binary tree can be stored in an array, but because a binary heap is always a complete binary tree, it can be compactly & uniquely represented by storing its level order traversal in an array. As a result, no space is required for pointers, instead, the parent and children of each node are found by arithmetic calculations on array indices.

Usage

Mheap exposes a chainable API, that can be utilized through a simple and minimal syntax, allowing you to combine methods effectively.

Usage examples can be also found at the test directory.

'use strict';
const {MaxHeap, MinHeap, Node} = require('mheap');

const maxHeap = new MaxHeap();
//=> MaxHeap { data: [] }

maxHeap.insert(15, 'A');
//=> MaxHeap { data: [Node { key: 15, value: 'A' }] }

maxHeap.root;
//=> Node { key: 15, value: 'A' }

const node = new Node(15, 'A');

maxHeap.root.toPair();
//=> [15, 'A']

maxHeap.root.key === node.key;
//=> true

maxHeap.root.value === node.value;
//=> true

maxHeap.insert(10, 'B').insert(5, 'C');
//=> MaxHeap { data: [
// Node { key: 15, value: 'A' },
// Node { key: 10, value: 'B' },
// Node { key: 5, value: 'C' } ] }

maxHeap.left(0);
//=> Node { key: 10, value: 'B' }

maxHeap.right(0);
//=> Node { key: 5, value: 'C' }

maxHeap.insert(7, 'D').insert(8, 'E').insert(2, 'F');
//=> MaxHeap { data: [
// Node { key: 15, value: 'A' },
// Node { key: 10, value: 'B' },
// Node { key: 5, value: 'C' },}
// Node { key: 7, value: 'D' },
// Node { key: 8, value: 'E' },
// Node { key: 2, value: 'F' } ] }

maxHeap.search(8);
//=> Node { key: 8, value: 'E' }

maxHeap.includes(2);
//=> true

maxHeap.includes(100);
//=> false

maxHeap.height();
//=> 2

maxHeap.indexOf(7);
//=> 3

maxHeap.remove(1);
//=> MaxHeap { data: [
// Node { key: 15, value: 'A' },
// Node { key: 8, value: 'E' },
// Node { key: 5, value: 'C' },
// Node { key: 7, value: 'D' },
// Node { key: 2, value: 'F' } ] }

maxHeap.children(0);
//=> { left: Node { key: 8, value: 'E' },
// right: Node { key: 5, value: 'C' } }

maxHeap.extractMax();
//=> Node { key: 15, value: 'A' }

maxHeap.toPairs();
//=> [ [ 8, 'E' ], [ 7, 'D' ], [ 5, 'C' ], [ 2, 'F' ] ]

API

The following documentation holds for both binary max & min heaps. The below described heap instance is used to depict the same methods that are available to both a min and a max heap, without overlooking their above described differences and unique qualities. For dedicated methods to min or max binary heaps, the min & max instances are used respectively.

heap.root

• Return Type: Node | undefined

Returns the root node of the heap. If the heap is empty undefined is returned.

heap.insert(10, 'A');
heap.root;
// => Node { key: 10, value: 'A' }

heap.size

• Return Type: Number

Returns the total number of nodes residing in the heap.

heap.insert(15, 'A').insert(10, 'B').insert(5, 'C');
heap.size;
// => 3

heap.childIndices(index)

• Return Type: { left?: Number, right?: Number }

Returns an object containing the child indices of the parent node corresponding to the given index. Both the given parent index and the returned child indices are relative to the unique level order array representation of the heap. If the parent node is either a full, a partial or leaf node then the returned object will respectively contain both, only one or none of the child indices.

index

• Type: Number

Node index relative to the unique level order array representation of the binary heap.

heap.insert(15, 'A').insert(10, 'B').insert(5, 'C');
heap.childIndices(0);
// => { left: 1, right: 2 }
heap.childIndices(1);
// => { }
heap.childIndices(2);
// => { }

heap.children(index)

• Return Type: { left?: Node, right?: Node }

Returns an object containing the children of the parent node corresponding to the given index. If the parent node is either a full, a partial or leaf node then the returned object will respectively contain both, only one or none of the child nodes.

index

• Type: Number

Node index relative to the unique level order array representation of the binary heap.

heap.insert(15, 'A').insert(10, 'B').insert(5, 'C');
heap.children(0);
// => { left: Node { key:10, value 'B' }, right: Node { key: 5, value 'C' } }
heap.children(1);
// => { }
heap.children(2);
// => { }

heap.clear()

• Return Type: Heap

Mutates the heap by removing all residing nodes and returns it empty.

heap.insert(15, 'A').insert(10, 'B').insert(5, 'C');
//=> Heap { data: [
// Node { key: 15, value: 'A' },
// Node { key: 10, value: 'B' },
// Node { key: 5, value: 'C' } ] }
heap.size;
//=> 3
heap.clear();
//=> Heap { data: [] } }
heap.size;
//=> 0

heap.degree(index)

• Return Type: Number

Returns the number of sub-heaps that the node, corresponding to the give index, points to.

index

• Type: Number

Node index relative to the unique level order array representation of the binary heap.

heap.insert(15, 'A').insert(10, 'B').insert(5, 'C');
heap.degree(0);
//=> 2
heap.degree(1);
//=> 0

heap.extract(index)

• Return Type: Node | undefined

Mutates the binary heap by removing the node, corresponding to the given index, and properly readjusts the heap in order for it to fulfill the two shape & heap properties. Returns the removed node, if the node is found, or undefined if it is not.

index

• Type: Number

Node index relative to the unique level order array representation of the binary heap.

heap.insert(15, 'A').insert(10, 'B').insert(5, 'C').insert(8, 'D').insert(7, 'E').insert(1, 'F');
//=> Heap { data: [ 
// Node { key: 15, value: 'A' },
// Node { key: 10, value: 'B' },
// Node { key: 5, value: 'C' },
// Node { key: 8, value: 'D' },
// Node { key: 7, value: 'E' },
// Node { key: 1, value: 'F' } ] }
heap.extract(1);
//=> Node { key: 10, value: 'B' }
heap;
//=> Heap { data: [ 
// Node { key: 15, value: 'A' },
// Node { key: 8, value: 'D' },
// Node { key: 5, value: 'C' },
// Node { key: 1, value: 'F' },
// Node { key: 7, value: 'E' } ] }

maxHeap.extractMax()

• Return Type: Node | undefined

Mutates the binary max heap by removing the node with the greatest key, known as maximum node / root node, and properly readjusts the max heap in order for it to fulfill the two shape & heap properties. Returns the maximum node, if the heap is not empty, or undefined if it is.

maxHeap.insert(15, 'A').insert(10, 'B').insert(5, 'C').insert(8, 'D').insert(7, 'E').insert(1, 'F');
//=> MaxHeap { data: [ 
// Node { key: 15, value: 'A' },
// Node { key: 10, value: 'B' },
// Node { key: 5, value: 'C' },
// Node { key: 8, value: 'D' },
// Node { key: 7, value: 'E' },
// Node { key: 1, value: 'F' } ] }
maxHeap.extractMax();
//=> Node { key: 15, value: 'A' }
heap;
//=> MaxHeap { data: [ 
// Node { key: 10, value: 'B' },
// Node { key: 8, value: 'D' },
// Node { key: 5, value: 'C' },
// Node { key: 1, value: 'F' },
// Node { key: 7, value: 'E' } ] }

minHeap.extractMin()

• Return Type: Node | undefined

Mutates the binary min heap by removing the node with the smallest key, known as minimum node / root node, and properly readjusts the min heap in order for it to fulfill the two shape & heap properties. Returns the minimum node, if the heap is not empty, or undefined if it is.

minHeap.insert(15, 'A').insert(10, 'B').insert(5, 'C').insert(8, 'D').insert(7, 'E').insert(1, 'F');
//=> MinHeap { data: [ 
// Node { key: 1, value: 'F' },
// Node { key: 7, value: 'E' },
// Node { key: 5, value: 'C' },
// Node { key: 15, value: 'A' },
// Node { key: 8, value: 'D' },
// Node { key: 10, value: 'B' } ] }
minHeap.extractMin();
//=> Node { key: 1, value: 'F' }
heap;
//=> MinHeap { data: [ 
// Node { key: 5, value: 'C' },
// Node { key: 7, value: 'E' },
// Node { key: 1