2.0.14 • Published 3 years ago

@algorithm.ts/priority-queue v2.0.14

Weekly downloads
-
License
MIT
Repository
github
Last release
3 years ago

A typescript implementation of Priority Queue, the internal data structure is a max heap.

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

Install

  • npm

    npm install --save @algorithm.ts/priority-queue
  • yarn

    yarn add @algorithm.ts/priority-queue
  • deno

    import { createPriorityQueue } from 'https://raw.githubusercontent.com/guanghechen/algorithm.ts/main/packages/priority-queue/src/index.ts'

Usage

  • IPriorityQueue

    MemberReturnDescription
    init(elements?: T[], startPos?: number, endPos?: number)voidInitialize priority queue with initial elements.
    enqueue(val: T)voidDrop a element into the priority queue.
    enqueues(elements: T[], startIndex?: number, endIndex?: number)voidDrop multiple elements into the priority queue.
    dequeue()T|undefinedPopup the top element.
    splice(filter, newElements?: T[], startIndex?: number, endIndex?: number)voidRemove existed elements which is not passed the filter, then enqueues the additional elements.
    replaceTop(newElement: T)voidReplace top element with new one. (If the queue is empty, then the newElement will be enqueued.)
    top()T|undefinedGet the top element.
    size()numberReturn the number of elements of the priority queue.
    isEmpty()booleanCheck if the priority queue is empty.
    collect()T[]Return all of the elements of the priority queue.
  • createPriorityQueue

    export function createPriorityQueue<T>(
      cmp: (x: T, y: T) => -1 | 0 | 1 | number,
    ): IPriorityQueue<T>
    • createPriorityQueue<number>((x, y) => x - y): The top element has a maximum value.
    • createPriorityQueue<number>((x, y) => y - x): The top element has a minimum value.

Example

  • Basic

    import { createPriorityQueue } = '@algorithm.ts/priority-queue'
    
    const Q = createPriorityQueue<number>((x, y) => x - y)
    
    Q.enqueue(3)
    Q.enqueue(7)
    Q.enqueue(1)
    Q.enqueue(-5)
    
    Q.size()      // => 4
    Q.isEmpty()   // => false
    
    Q.dequeue()   // => 7
    Q.dequeue()   // => 3
    Q.top()       // => 1
    Q.top()       // => 1
    Q.dequeue()   // => 1
    Q.top()       // => -5
    Q.dequeue()   // => -5
    Q.top()       // => undefined
    Q.dequeue()   // => undefined
    
    Q.isEmpty()   // => true
  • A solution for 剑指offer#63 https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1

    import { createPriorityQueue } from '@algorithm.ts/priority-queue'
    
    const lowerQ = createPriorityQueue<number>((x, y) => x - y)
    const upperQ = createPriorityQueue<number>((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.top()! + upperQ.top()!) / 2
        : lowerQ.top()!
    }

Related

2.0.14

3 years ago

2.0.13

3 years ago

2.0.12

3 years ago

2.0.5

3 years ago

2.0.4

3 years ago

2.0.11

3 years ago

2.0.7

3 years ago

2.0.6

3 years ago

2.0.9

3 years ago

2.0.10

3 years ago

2.0.8

3 years ago

2.0.8-alpha.0

3 years ago

2.0.7-alpha.1

3 years ago

2.0.7-alpha.0

3 years ago

2.0.3

3 years ago

2.0.2

3 years ago

2.0.0-alpha.0

3 years ago

2.0.1

3 years ago

1.0.24

3 years ago

2.0.0

3 years ago

1.0.23

4 years ago

1.0.19

4 years ago

1.0.22

4 years ago

1.0.21

4 years ago

1.0.20

4 years ago

1.0.18

4 years ago

1.0.17

4 years ago

1.0.16

4 years ago

1.0.15

4 years ago

1.0.14

4 years ago

1.0.13

4 years ago

1.0.12

4 years ago

1.0.11

4 years ago

1.0.10

4 years ago

1.0.9

4 years ago

1.0.8

4 years ago

1.0.7

4 years ago

1.0.6

4 years ago

1.0.5

4 years ago

1.0.4

4 years ago

1.0.3

4 years ago