A progressive Node.js framework for building efficient and scalable server-side applications.
Nest framework TypeScript starter repository.
$ npm install
# development
$ npm run start
# watch mode
$ npm run start:dev
# production mode
$ npm run start:prod
# unit tests
$ npm run test
# e2e tests
$ npm run test:e2e
# test coverage
$ npm run test:cov
Nest is an MIT-licensed open source project. It can grow thanks to the sponsors and support by the amazing backers. If you'd like to join them, please read more here.
- Author - Kamil Myśliwiec
- Website - https://nestjs.com
- Twitter - @nestframework
Nest is MIT licensed.
The essential operations of the priority queue are:
- enqueue: insert elements on the queue
- dequeue: remove elements from the queue in the same order they were inserted.
Enqueue The algorithm to insert an element is the following:
- Insert the element into the next empty position (tail).
- From that position, “bubble up” the element to keep the min-heap invariant “parent should be smaller than any children” (the opposite if max-heap).
- If the invariant is broken, fix it by swapping the node with its parent and repeat the process all the way to the root node if necessary.
Complexity:
- Time: O(log n), in the worst case, you will have to bubble up the inserted element up to the root of the tree. These will involve log n swaps, where n is the total number of nodes.
- Space: O(n)
Dequeue
The algorithms for dequeuing an element is:
Remove the root element
- Since the root element is gone, you need to fill the hole by promoting a child to take its place. This process is called “heapify” or bubbleDown.
- You choose the child that has the min value for min-heap (or max value for max-heap). You do this recursively until you found a leaf (node without children).
Complexity:
- Time: O(log n), The maximum number of swaps is given by the tree’s height, which is log n.
- Space: O(n).