mirror of
https://github.com/TheAlgorithms/JavaScript.git
synced 2025-07-05 16:26:47 +08:00
566d9103cd
* ref: KeyPriorityQueue in separate file #1298 * feat: add tests for KeyPriorityQueue #1298 * fix: _shiftDown refactored and corrected #1298 * fix: use KeyPriorityQueue in PrimMST #1298 * feat: add test for PrimMST #1298 * fix: format files #1298 * fix: minor coding style changes * fix: use map for keys and priorities #1298
127 lines
3.5 KiB
JavaScript
127 lines
3.5 KiB
JavaScript
import { KeyPriorityQueue } from '../KeyPriorityQueue.js'
|
|
|
|
describe('Key Priority Queue', () => {
|
|
describe('Method isEmpty', () => {
|
|
test('Check heap is empty', () => {
|
|
const queue = new KeyPriorityQueue()
|
|
const res = queue.isEmpty()
|
|
expect(res).toEqual(true)
|
|
})
|
|
|
|
test('Check heap is not empty', () => {
|
|
const queue = new KeyPriorityQueue()
|
|
queue.push(0, 2)
|
|
const res = queue.isEmpty()
|
|
expect(res).toEqual(false)
|
|
})
|
|
})
|
|
|
|
describe('Methods push and pop', () => {
|
|
test('Test Case 1', () => {
|
|
// create queue
|
|
const queue = new KeyPriorityQueue()
|
|
queue.push(0, 3)
|
|
queue.push(1, 7)
|
|
queue.push(2, 9)
|
|
queue.push(3, 13)
|
|
// create expected queue
|
|
const expectedQueue = new KeyPriorityQueue()
|
|
expectedQueue.push(1, 7)
|
|
expectedQueue.push(3, 13)
|
|
expectedQueue.push(2, 9)
|
|
// result from popping element from the queue
|
|
queue.pop()
|
|
expect(queue).toEqual(expectedQueue)
|
|
})
|
|
|
|
test('Test Case 2', () => {
|
|
// create queue
|
|
const queue = new KeyPriorityQueue()
|
|
queue.push(0, 3)
|
|
queue.push(1, 9)
|
|
queue.push(2, 7)
|
|
queue.push(3, 13)
|
|
// create expected queue
|
|
const expectedQueue = new KeyPriorityQueue()
|
|
expectedQueue.push(2, 7)
|
|
expectedQueue.push(1, 9)
|
|
expectedQueue.push(3, 13)
|
|
// result from popping element from the queue
|
|
queue.pop()
|
|
expect(queue).toEqual(expectedQueue)
|
|
})
|
|
|
|
test('Test Case 3', () => {
|
|
// create queue
|
|
const queue = new KeyPriorityQueue()
|
|
queue.push(0, 3)
|
|
queue.push(1, 7)
|
|
queue.push(2, 9)
|
|
queue.push(3, 12)
|
|
queue.push(4, 13)
|
|
// create expected queue
|
|
const expectedQueue = new KeyPriorityQueue()
|
|
expectedQueue.push(1, 7)
|
|
expectedQueue.push(3, 12)
|
|
expectedQueue.push(2, 9)
|
|
expectedQueue.push(4, 13)
|
|
// result from popping element from the queue
|
|
queue.pop()
|
|
expect(queue).toEqual(expectedQueue)
|
|
})
|
|
})
|
|
|
|
describe('Method contains', () => {
|
|
test('Check heap does not contain element', () => {
|
|
const queue = new KeyPriorityQueue()
|
|
const res = queue.contains(0)
|
|
expect(res).toEqual(false)
|
|
})
|
|
|
|
test('Check heap contains element', () => {
|
|
const queue = new KeyPriorityQueue()
|
|
queue.push(0, 2)
|
|
const res = queue.contains(0)
|
|
expect(res).toEqual(true)
|
|
})
|
|
})
|
|
|
|
describe('Method update', () => {
|
|
test('Update without change in position', () => {
|
|
// create queue
|
|
const queue = new KeyPriorityQueue()
|
|
queue.push(0, 3)
|
|
queue.push(1, 5)
|
|
queue.push(2, 7)
|
|
queue.push(3, 11)
|
|
// create expected queue
|
|
const expectedQueue = new KeyPriorityQueue()
|
|
expectedQueue.push(0, 2)
|
|
expectedQueue.push(1, 5)
|
|
expectedQueue.push(2, 7)
|
|
expectedQueue.push(3, 11)
|
|
// result from updating to similar priority
|
|
queue.update(0, 2)
|
|
expect(queue).toEqual(expectedQueue)
|
|
})
|
|
|
|
test('Update with change in position', () => {
|
|
// create queue
|
|
const queue = new KeyPriorityQueue()
|
|
queue.push(0, 3)
|
|
queue.push(1, 5)
|
|
queue.push(2, 7)
|
|
queue.push(3, 11)
|
|
// create expected queue
|
|
const expectedQueue = new KeyPriorityQueue()
|
|
expectedQueue.push(1, 5)
|
|
expectedQueue.push(3, 11)
|
|
expectedQueue.push(2, 7)
|
|
expectedQueue.push(0, 9)
|
|
// result from updating to similar priority
|
|
queue.update(0, 9)
|
|
expect(queue).toEqual(expectedQueue)
|
|
})
|
|
})
|
|
})
|