Skip to main content
Module

x/ssds/mod.ts>ArrayHeapPQ

Some Specialized Data Structures for Deno.
claytsay/ssds-deno
Latest
class ArrayHeapPQ
implements ExtrinsicPQ<T>
import { ArrayHeapPQ } from "https://deno.land/x/ssds@0.2.0/mod.ts";

Constructors

new
ArrayHeapPQ(isMax?: boolean)

Constructs a priority queue.

If the parameter 'isMax' is 'true', will be a maximum priority queue. If not, will default to a minimum priority queue.

Properties

private
_locations: Map<T, number>
private
_max: boolean
private
_nodes: Array<PQNode<T>>

Methods

private
_getRelationIndex(index: number, relation: Relation): number

Gets the index of the specified relation.

Is not safe (i.e. might cause an error by trying to access an index not present in the list of PQNodes). If the given Relation is invalid, returns 0.

private
_getRelationPriority(index: number, relation: Relation): number

Gets the priority value of the specified relation.

If the relation is invalid (e.g. does not exist), will return positive infinity for the priority.

private
_hasRelation(index: number, relation: Relation): boolean

Determines whether the node at the given index has a given relation or not.

If the provided Relation is invalid, will return 'false' by default.

private
_isValidIndex(index: number): boolean

Checks whether an index is acceptable or not.

Checks to verify that:

  • The index is within the bounds of the list
  • The reference at the index is not 'null'
private
_shouldSwap(index: number, relation: Relation): boolean

Determines if the node should be swapped with its relation or not.

The method will return 'true' if the relation exists and comparison of the priorities shows that the two should be swapped.

private
_swap(i: number, j: number): void

Swaps the items at the specified indices of the list.

private
_swim(index: number): void

Attempts to swim a node to its correct position.

private
_validateSize(): void

Checks to see if the size of the queue is greater than zero.

add(item: T, priority: number): void
changePriority(item: T, priority: number): void
contains(item: T): boolean
get(): T
size(): number