Options
All
  • Public
  • Public/Protected
  • All
Menu

Class PriorityQueue<T>

A priority queue implemented using binomial heaps

Type parameters

  • T

    the type of item being stored in the priority a queue

Hierarchy

  • PriorityQueue

Index

Constructors

Properties

Methods

Constructors

constructor

  • new PriorityQueue(comparator?: undefined | ((a: T, b: T) => number)): PriorityQueue

  • The constructor function for a priority queue

    Parameters

    • Optional comparator: undefined | ((a: T, b: T) => number)

      a comparator function for comparing elements

    Returns PriorityQueue

Properties

Private array

array: T[] = []

Private compare

compare: (a: T, b: T) => number

Type declaration

    • (a: T, b: T): number

    • Parameters

      • a: T
      • b: T

      Returns number

Private size

size: number = 0

Methods

Private _percolateDown

  • _percolateDown(index: number): void

Private _percolateUp

  • _percolateUp(index: number): void

changeItem

  • changeItem(item: T, newItem: T): void

  • Swaps out an item in the queue for a new item, can be used to update the key of an item Note: has time complexity O(n)

    Parameters

    • item: T

      the item to be swapped out of the queue

    • newItem: T

      the item to be swapped into the queue

    Returns void

extractMin

  • extractMin(): T

  • Returns the highest priority item and removes it from the queue

    throws

    PriorityQueueError if the queue is empty

    Returns T

insert

  • insert(a: T): void

  • Inserts an item into the priority queue

    Parameters

    • a: T

      the item to be inserted

    Returns void

isEmpty

  • isEmpty(): boolean

peek

  • peek(): T

  • Returns the highest priority item without removing it

    throws

    PriorityQueueError if the queue is empty

    Returns T

Generated using TypeDoc