Max Heap

A MaxHeap is a complete binary tree in which the value in each internal node is greater 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 MaxHeap is a wrapper around Javascript array with a standard heap interface.

Operations

insert: Adds elements to the heap.
extractMax: Removes and returns the max element from the heap.
property max: Returns the max 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 negative value if the first argument is less than the second argument, zero if they're equal, and a positive value otherwise.

import { MaxHeap } from '@ultify/datastructure'

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

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

fromArray `(static)`

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

import { MaxHeap } from '@ultify/datastructure'

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

toArray

import { MaxHeap } from '@ultify/datastructure'

// Create a MaxHeap
const foo = new MaxHeap([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 { MaxHeap } from '@ultify/datastructure'

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

console.log(foo.toArray())

Extract Max

import { MaxHeap } from '@ultify/datastructure'

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

console.log(foo.extractMax())
console.log(foo.toArray())

Max

import { MaxHeap } from '@ultify/datastructure'

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

console.log(foo.max)
console.log(foo.toArray())

Is Valid

import { MaxHeap } from '@ultify/datastructure'

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

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

Heap Min Heap