Heap

A Heap is a complete binary tree data structure that satisfies the heap property: for every node, the value of its children is less than or equal to its own value. Heaps are usually used to implement priority queues, where the smallest (or largest) element is always at the root of the tree.

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

Types

@ultify/datastructure also comes with some implementations of Heap datastructure.

Max Heap Min Heap

Operations

insert: Adds elements to the heap.
extractRoot: Removes and returns the root element from the heap.
property root: Returns the 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

By default, a Heap will be created as a Max Heap. To create another type of Heap, you can provide the compareFn to create the Heap accordingly.

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 { Heap } from '@ultify/datastructure'

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

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

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

fromArray `(static)`

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

import { Heap } from '@ultify/datastructure'

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

toArray

import { Heap } from '@ultify/datastructure'

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

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

console.log(foo.toArray())

Extract Root

import { Heap } from '@ultify/datastructure'

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

console.log(foo.extractRoot())
console.log(foo.toArray())

Root

import { Heap } from '@ultify/datastructure'

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

console.log(foo.root)
console.log(foo.toArray())

Is Valid

import { Heap } from '@ultify/datastructure'

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

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

Queue Max Heap