Options
All
  • Public
  • Public/Protected
  • All
Menu

Class BinaryHeap<T>

Heap (binary heap implementation)

In computer science, a heap is a specialized tree-based data structure which is essentially an almost complete tree that satisfies the heap property: in a max heap, for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap, the key of P is less than or equal to the key of C.[2] The node at the "top" of the heap (with no parents) is called the root node.

Min heap

min heap source: tutorialspoint.com

Max heap

max heap source: tutorialspoint.com

Complexity

Algorithm Average Worst case
Access O(1) O(n)
Search O(n) O(n)
Insert O(1) O(log n)
Delete O(log n) O(log n)
Peek O(1) O(1)
- - -
Space O(n) O(n)

Reference

import { BinaryHeap } from '@pencroff/ts-algorithms/dist/structure/heap';
const h = new BinaryHeap([1, 2, 3])

Type parameters

  • T

Hierarchy

Implements

  • Iterable<T>

Index

Constructors

Properties

Accessors

Methods

Constructors

constructor

Properties

Protected comparator

comparator: ComparatorFn<T>

Private items

items: T[]

Accessors

length

  • get length(): number

Methods

__@iterator

  • __@iterator(): Iterator<T>

clear

  • clear(): void

extract

  • extract(): T

find

  • find(value: T): number

Private getLeftChild

  • getLeftChild(idx: number): T

Private getLeftChildIdx

  • getLeftChildIdx(parentIdx: number): number

Private getParent

  • getParent(idx: number): T

Private getParentIdx

  • getParentIdx(childIdx: number): number

Private getRightChild

  • getRightChild(idx: number): T

Private getRightChildIdx

  • getRightChildIdx(parentIdx: number): number

Private hasLeftChild

  • hasLeftChild(idx: number): boolean

Private hasRightChild

  • hasRightChild(idx: number): boolean

insert

  • insert(v: T): void

Protected isCorrectOrder

  • isCorrectOrder(elA: T, elB: T): boolean

  • Order comparator, has influence on type of [[Heap]] Current implementation - min heap

    Parameters

    • elA: T
    • elB: T

    Returns boolean

isEmpty

  • isEmpty(): boolean

peek

  • peek(): T

Private reBalance

  • reBalance(idx: number): void

remove

  • remove(v: T): boolean

replace

  • replace(oldValue: T, newValue: T): boolean

Private siftDown

  • siftDown(startIdx?: number): void

Private siftUp

  • siftUp(startIdx?: number): void