Min Heap

A MinHeap is a complete binary tree in which the value in each internal node is smaller than or equal to the values in the children of that node. Mapping the elements of a heap into an array is trivial: if a node is stored an index k, then its left child is stored at index 2k + 1 and its right child at index 2k + 2.

Ultify's MinHeap is a wrapper around Javascript array with a standard heap interface.

Operations

insert: Adds elements to the heap.
extractMin: Removes and returns the Min element from the heap.
property min: Returns the Min element of the heap without removing it.
isValid: Check ifs the heap is valid.
IsEmpty: Checks if the queue is empty.
toArray: Convert a heap to an array.
static getLeftChildIndex: Returns the left child's index of a given index.
static getRightChildIndex: Returns the right child's index of a given index.
static getParentIndex: Returns the parent's index of a given index.

APIs

Constructor

Ultify's heap time complexity to create a Heap from an array is O( ${n}$ ).

`compareFn`

Type: <T>(a: T, b: T) => number
Description: Function used to determine the order of the elements. It is expected to return a positive value if the first argument is less than the second argument, zero if they're equal, and a nagative value otherwise.

import { MinHeap } from '@ultify/datastructure'

// Create an empty heap
const foo = new MinHeap()
console.log("Empty MinHeap:", foo.toArray())

// Create a heap from an array
const bar = new MinHeap([3, 7, 5, 9])
console.log("Min Heap:", bar.toArray())

fromArray `(static)`

Ultify's heap time complexity to create a Heap from an array is O( ${n}$ ).

import { MinHeap } from '@ultify/datastructure'

// Create an empty MinHeap
const foo = MinHeap.fromArray([1, 2, 3])
console.log(foo.toArray())

toArray

import { MinHeap } from '@ultify/datastructure'

// Create a MinHeap
const foo = new MinHeap([1, 2, 3])

console.log(foo.toArray())

Insert

Ultify's heap time complexity to insert a single value to a Heap is O( $\log{n}$ ).

Ultify's heap time complexity to insert multiple values to a Heap is O( ${n}$ ).

import { MinHeap } from '@ultify/datastructure'

// Create an empty MinHeap
const foo = new MinHeap()
foo.insert(1)
foo.insert(2)
foo.insert(67, -7)

console.log(foo.toArray())

Extract Min

import { MinHeap } from '@ultify/datastructure'

// Create an empty Heap
const foo = new MinHeap()
foo.insert(1)
foo.insert(2)
foo.insert(67, -7)

console.log(foo.extractMin())
console.log(foo.toArray())

Min

import { MinHeap } from '@ultify/datastructure'

// Create an empty Heap
const foo = new MinHeap()
foo.insert(1)
foo.insert(2)
foo.insert(67, -7)

console.log(foo.min)
console.log(foo.toArray())

Is Valid

import { MinHeap } from '@ultify/datastructure'

// Create an empty MinHeap
const foo = new MinHeap()
foo.insert(1)
foo.insert(2)
foo.insert(67, -7)

console.log(foo.toArray())
console.log(foo.isValid())

Max Heap Trie