@algorithm.ts/queue

@algorithm.ts/queue

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 Collection interface.

  Member	Return	Description
  init(elements?: T[], startPos?: number, endPos?: number)	void	Initialize priority queue with initial elements.
  enqueue(val: T)	void	Drop a element into the priority queue.
  enqueues(elements: T[], startIndex?: number, endIndex?: number)	void	Drop multiple elements into the priority queue.
  dequeue(newElement?: T)	`T	undefined`
  splice(filter, newElements?: T[], startIndex?: number, endIndex?: number)	void	Remove existed elements which is not passed the filter, then enqueues the additional elements.
  front()	`T	undefined`
  size	number	Get the number of elements.

• 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 Collection interface.

  Signature	Description
  init(elements?: T[], startPos?: number, endPos?: number): void	Initialize circular queue with initial elements.
  enqueue(val: T): void	Drop a element into the circular queue.
  enqueues(elements: T[], startIndex?: number, endIndex?: number): void	Drop multiple elements into the circular queue.
  `dequeue(newElement?: T): T	undefined`
  splice(filter, newElements?: T[], startIndex?: number, endIndex?: number): void	Remove existed elements which is not passed the filter, then enqueues the additional elements.
  `front(): T	undefined`
  `pop(): T	undefined`
  `back(): T	undefined`
  `unshift(): T	undefined`
  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.

• 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