A typescript implementation of Priority Queue (based on min-heap) and Circular Queue.

Install

• npm

  npm install --save @algorithm.ts/queue

• yarn

  yarn add @algorithm.ts/queue

Usage

PriorityQueue

Priority Queue is a special queue structure, the first element of the queue always returns to the minimum value in the queue, and the amortized time complexity of the enqueue and dequeue operations are both $O(\log N)$.

• IPriorityQueue: PriorityQueue implements the IPriorityQueue interface.

  | Signature | Description | | :------------------------------------------------------------------------------: | :------------------------------------------------------------------------------- | | consuming(): IterableIterator<T> | Popup the elements from the queue by the dequeue order. | | count(filter: (element: T) => boolean): number | Count the elements in the queue which matched by the filter. | | dequeue(newElement?: T): T\|undefined | Popup the top element, and push the given newElement if it is not undefined. | | enqueue(val: T): void | Push a element into the priority queue. | | enqueues(elements: Iterable<T>): void | Push multiple elements into the priority queue. | | enqueues_advance(elements: ReadonlyArray<T>, start: number, end: number): void | Push multiple elements into the priority queue. | | exclude(filter: (element: T) => boolean): void | Remove elements matched the filter. | | destroy(): void | Destroy the queue and release the memory. | | front(): T\|undefined | Get the top element from the priority queue. | | init(initialElements?: Iterable<T>: void | Initialize priority queue with initial elements. | | readonly size: number | Get the number of elements. | | readonly destroyed: number | Indicate whether the priority queue destroyed. |

• IPriorityQueueProps

  export interface IPriorityQueueProps<T> {
    /**
    * If the compare(x, y) < 0, then x has a higher precedence than y.
    */
    compare: ICompare<T>
  }

  • new PriorityQueue<number>({ compare: (x, y) => x - y }): The top element has a minimum value.
  • new PriorityQueue<number>({ compare: (x, y) => y - x }): The top element has a maximum value.

CircularQueue

Circular queue is a queue structure, the main purpose of its design is to reuse space as much as possible on the basis of ordinary queues. Circular queues usually need to specify the maximum volume C of the collector. If the number of elements in the queue exceeds C, only the most recent C elements are kept in the queue. Other operations are the same as ordinary queues.

• ICircularQueue: CircularQueue implements the ICircularQueue interface.

  | Signature | Description | | :------------------------------------------------------------------------------: | :------------------------------------------------------------------------------- | | consuming(): IterableIterator<T> | Popup the elements from the queue by the dequeue order. | | count(filter: (element: T) => boolean): number | Count the elements in the queue which matched by the filter. | | dequeue(newElement?: T): T\|undefined | Popup the top element, and push the given newElement if it is not undefined. | | enqueue(val: T): void | Push a element into the circular queue. | | enqueues(elements: Iterable<T>): void | Push multiple elements into the circular queue. | | enqueues_advance(elements: ReadonlyArray<T>, start: number, end: number): void | Push multiple elements into the circular queue. | | exclude(filter: (element: T) => boolean): void | Remove elements matched the filter. | | destroy(): void | Destroy the queue and release the memory. | | front(): T\|undefined | Get the first enqueued element from the circular queue. | | back(): T\|undefined | Get the last enqueued element from the circular queue. | | init(initialElements?: Iterable<T>: void | Initialize circular queue with initial elements. | | resize(MAX_SIZE: number): void | Resize the max-size of queue with the given size. | | rearrange(): void | Rearrange elements, that is, put the first element in place 0-index. | | readonly size: number | Get the number of elements. | | readonly destroyed: number | Indicate whether the circular queue destroyed. |

• ICircularQueueProps

  export interface ICircularQueueProps {
    /**
    * Initial capacity of the circular queue.
    */
    capacity?: number
    /**
    * Automatically extends the queue capacity when the queue is full.
    * @default true
    */
    autoResize?: boolean
    /**
    * @default 1.5
    */
    autoResizeExpansionRatio?: number
  }

Example

• Basic -- PriorityQueue

  import { PriorityQueue } = '@algorithm.ts/queue'
  
  const Q = new PriorityQueue<number>({ compare: (x, y) => y - x })
  
  Q.enqueue(3)
  Q.enqueue(7)
  Q.enqueue(-5)
  Q.enqueue(1)
  Q.size        // => 4
  Array.from(Q) // => [7, 3, -5, 1] !!!NOTE: the result are not guaranteed to be ordered.
  
  Q.dequeue()   // => 7
  Q.dequeue()   // => 3
  Q.front()     // => 1
  Q.front()     // => 1
  Q.dequeue()   // => 1
  Q.front()     // => -5
  Q.dequeue()   // => -5
  Q.front()     // => undefined
  Q.dequeue()   // => undefined

• Basic -- CircularQueue

  import { CircularQueue } from '@algorithm.ts/queue'
  
  const queue = new CircularQueue<{ name: string }>()
  
  // Initialize the circular-queue with the maximum number of elements it can
  // be managed.
  queue.init(100)
  
  // Append a element to the end of the queue.
  queue.enqueue({ name: 'alice' }) // => 0
  queue.enqueue({ name: 'bob' }) // => 1
  queue.size          // => 2
  
  // Get the front element of the queue.
  queue.front()       // => { name: 'alice' }
  
  // Get the last element of the queue.
  queue.back()        // => { name: 'bob' }
  
  // Take off the first element of the queue.
  queue.dequeue()     // => { name: 'alice' }
  queue.size          // => 1

• A solution for 剑指 offer#63 https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

  import { PriorityQueue } from '@algorithm.ts/queue'
  
  const lowerQ = new PriorityQueue<number>({ compare: (x, y) => x - y })
  const upperQ = new PriorityQueue<number>({ compare: (x, y) => y - x })
  
  export function Insert(num: number): void {
    if (lowerQ.size === upperQ.size) {
      upperQ.enqueue(num)
      lowerQ.enqueue(upperQ.dequeue()!)
    } else {
      lowerQ.enqueue(num)
      upperQ.enqueue(lowerQ.dequeue()!)
    }
  }
  
  export function GetMedian(): number {
    return lowerQ.size === upperQ.size
      ? (lowerQ.front()! + upperQ.front()!) / 2
      : lowerQ.front()!
  }

Related