Max Binary Heap:
class MaxBinaryHeap {
#content
constructor() {
this.#content = []
}
// Private class methods
#swap(i, j) {
const temp = this.#content[i]
this.#content[i] = this.#content[j]
this.#content[j] = temp
}
// Also called heapify up or swim up
#bubbleUp(i) {
const element = this.#content[i]
while (i > 0) {
const p = Math.floor((i - 1) / 2),
parent = this.#content[p]
if (element > parent) {
this.#swap(p, i)
i = p
} else {
break
}
}
}
// Also called heapify down
#sinkDown(p) {
const element = this.#content[p],
lastIndex = this.size - 1
while (p < lastIndex) {
const r = 2 * p + 2,
l = r - 1,
left = this.#content[l],
right = this.#content[r]
let swapIndex = null,
max = element
if (l <= lastIndex && left > max) {
swapIndex = l
max = left
}
if (r <= lastIndex && right > max) {
swapIndex = r
}
if (swapIndex == null) break
this.#swap(p, swapIndex)
p = swapIndex
}
}
// getters
get size() {
return this.#content.length
}
get max() {
return this.size ? this.#content[0] : null
}
// public class methods
printMaxHeap() {
console.log(this.#content)
return this.#content
}
insert(element) {
this.#content.push(element)
this.#bubbleUp(this.size - 1)
}
extractMax() {
if (this.size <= 0) return null
const lastIndex = this.size - 1,
firstIndex = 0
if (firstIndex !== lastIndex) this.#swap(firstIndex, lastIndex)
const max = this.#content.pop()
if (this.size > 0) {
this.#sinkDown(0)
}
return max
}
remove(element) {
for (let i = 0; i < this.size; i++) {
if (this.#content[i] !== element) continue
const lastIndex = this.size - 1
if (i === lastIndex) {
this.#content.pop()
break
}
this.#swap(i, lastIndex)
this.#content.pop()
this.#bubbleUp(i)
this.#sinkDown(i)
break
}
}
}
module.exports = MaxBinaryHeapMin Binary Heap:
// https://www.youtube.com/watch?v=WCm3TqScBM8
// Any node has a value at least as small as the values in that node's children.
// Source: https://eloquentjavascript.net/1st_edition/appendix2.html
class MinBinaryHeap {
#content
constructor() {
this.#content = []
}
// Private class methods
#swap(i, j) {
const temp = this.#content[i]
this.#content[i] = this.#content[j]
this.#content[j] = temp
}
/* bubbleUp - Also called heapify up or swim up
1. Compare item to parent and check if it's less than parent.
2. If it is less than parent, swap it.
3. Now, compare to the new parent and keep swapping until it either reaches the top of the heap or it is >= parent.
*/
#bubbleUp(i) {
const element = this.#content[i]
/*
indexing from 0
p is the index of the parent
i is the index of either left or right child
l is index of left child
r is the index of the right child
l = 2p + 1
r = 2p + 2
p = Math.floor((i-1)/2)
*/
while (i > 0) {
const p = Math.floor((i - 1) / 2),
parent = this.#content[p]
if (element < parent) {
this.#swap(p, i)
// make sure to change index to that of parent after swapping
i = p
} else {
break
}
}
}
/* sinkDown - Also called heapify down
1. Check the minimum value between the parent, left child and right child.
2. If parent is the min, you don't need to sink it down anymore.
3. If either child is minimum, swap the parent with the minimum child.
4. Set the parent index to the child's index and continue to sink down the new parent.
*/
#sinkDown(p) {
const element = this.#content[p],
lastIndex = this.#content.length - 1
while (p < lastIndex) {
const r = 2 * p + 2,
l = r - 1, //Or 2 * p + 1,
left = this.#content[l],
right = this.#content[r]
let swapIndex = null,
min = element //start out assuming the min between left, right, element is the element
// if left child < element, set swapIndex to the left index (l) and min to left
if (l <= lastIndex && left < min) {
// Don't need to check if left is undefined because undefined < number is always false
swapIndex = l
min = left
}
// compare the right to the min so far to make sure the min of the three items gets bubbled up while the parent gets sunk
if (r <= lastIndex && right < min) {
swapIndex = r
}
// parent is smaller than both left and right child so break
if (swapIndex == null) break
this.#swap(p, swapIndex)
// set the parent index to the swap index so it will continue to sink down
p = swapIndex
}
}
// Getters
get size() {
return this.#content.length
}
get min() {
return this.size ? this.#content[0] : null
}
get size() {
return this.#content.length
}
get min() {
return this.size ? this.#content[0] : null
}
// Public class methods
printMinHeap() {
console.log(this.#content)
return this.#content
}
/* insert
1. insert new item into this.#content
2. bubble it up
*/
insert(element) {
this.#content.push(element)
this.#bubbleUp(this.#content.length - 1)
}
/* extractMin
1. swap first and last items if this.#content.length > 1 (or first !== last)
2. pop out last item of array and save it in min
3. If length is more than one, bubble the first item down
4. Return the min that was saved
*/
extractMin() {
if (this.#content.length <= 0) return null //return null if array is empty
const lastIndex = this.#content.length - 1,
firstIndex = 0
if (firstIndex !== lastIndex) this.#swap(firstIndex, lastIndex)
const min = this.#content.pop()
if (this.#content.length > 0) {
this.#sinkDown(0)
}
return min
}
remove(element) {
for (let i = 0; i < this.size; i++) {
// if curr item doesn't match the element to remove, continue searching
if (this.#content[i] !== element) continue
// if it does match
const lastIndex = this.size - 1
// if it's the last item, pop it and break
if (i === lastIndex) {
this.#content.pop()
break
}
// if it's not the last item
// 1. swap it with the last item
// 2. pop the swapped last item
// 3. Then call bubbleUp and sinkDown.
this.#swap(i, lastIndex)
this.#content.pop()
this.#bubbleUp(i)
this.#sinkDown(i)
break
}
}
}
module.exports = MinBinaryHeapTests (jest):
const { MaxBinaryHeap } = require('../src')
describe('MaxBinaryHeap', () => {
test('creates a new instance of MaxBinaryHeap', () => {
const maxHeap = new MaxBinaryHeap()
expect(maxHeap instanceof MaxBinaryHeap).toBe(true)
})
describe('printMaxHeap', () => {
test('prints all items of heap as an array', () => {
const maxHeap = new MaxBinaryHeap()
maxHeap.insert(0)
maxHeap.insert(1)
expect(maxHeap.printMaxHeap()).toEqual([1, 0])
})
})
describe('insert', () => {
test('inserts item at correct place in heap', () => {
const maxHeap = new MaxBinaryHeap(),
arr = [10, 3, 4, 8, 2, 9, 7, 1, 2, 6, 5]
for (const el of arr) {
maxHeap.insert(el)
}
expect(maxHeap.printMaxHeap()).toEqual([10, 8, 9, 3, 6, 4, 7, 1, 2, 2, 5])
})
})
describe('scoped max heap', () => {
let maxHeap, length
beforeEach(() => {
maxHeap = new MaxBinaryHeap()
const arr = [10, 3, 4, 8, 2, 9, 7, 1, 2, 6, 5]
length = arr.length
for (const el of arr) {
maxHeap.insert(el)
}
})
describe('size', () => {
test('gets correct size of max heap', () => {
expect(maxHeap.size).toEqual(length)
})
test('returns 0 if size of heap is 0', () => {
const maxHeap = new MaxBinaryHeap()
expect(maxHeap.size).toBe(0)
})
})
describe('max', () => {
test('gets correct max of max heap', () => {
expect(maxHeap.max).toBe(10)
})
test('returns null if size of heap is 0', () => {
const maxHeap = new MaxBinaryHeap()
expect(maxHeap.max).toBe(null)
})
})
describe('extractMax', () => {
test('removes the correct max item from heap and returns it', () => {
const max = maxHeap.extractMax(),
heapContent = [9, 8, 7, 3, 6, 4, 5, 1, 2, 2]
expect(max).toBe(10)
expect(maxHeap.printMaxHeap()).toEqual(heapContent)
})
test('returns null if size of heap is 0', () => {
const maxHeap = new MaxBinaryHeap()
expect(maxHeap.max).toEqual(null)
})
})
describe('sinkDown', () => {
test('sinks parent down correct path if both left and right child are greater than parent', () => {
const maxHeap = new MaxBinaryHeap(),
arr = [7, 6, 5, 1, 2, 4]
for (const el of arr) {
maxHeap.insert(el)
}
const max = maxHeap.extractMax(),
heapContent = [6, 4, 5, 1, 2]
expect(max).toBe(7)
expect(maxHeap.printMaxHeap()).toEqual(heapContent)
})
test('sinks parent down to the left if parent < left but parent > right', () => {
const maxHeap = new MaxBinaryHeap(),
arr = [8, 6, 1, 2]
for (const el of arr) {
maxHeap.insert(el)
}
const max = maxHeap.extractMax(),
heapContent = [6, 2, 1]
expect(max).toBe(8)
expect(maxHeap.printMaxHeap()).toEqual(heapContent)
})
test('sinks parent down to the right if parent > left but parent < right', () => {
const maxHeap = new MaxBinaryHeap(),
arr = [8, 3, 6, 2, 1, 4]
for (const el of arr) {
maxHeap.insert(el)
}
const max = maxHeap.extractMax(),
heapContent = [6, 3, 4, 2, 1]
expect(max).toBe(8)
expect(maxHeap.printMaxHeap()).toEqual(heapContent)
})
})
describe('remove', () => {
test('removes the correct item from heap', () => {
maxHeap.remove(2)
const heapContent = [10, 8, 9, 5, 6, 4, 7, 1, 3, 2]
expect(maxHeap.printMaxHeap()).toEqual(heapContent)
})
})
})
})const { MinBinaryHeap } = require('../src')
describe('MinBinaryHeap', () => {
test('creates a new instance of MinBinaryHeap', () => {
const minHeap = new MinBinaryHeap()
expect(minHeap instanceof MinBinaryHeap).toBe(true)
})
describe('printMinHeap', () => {
test('prints all items of heap as an array', () => {
const minHeap = new MinBinaryHeap()
minHeap.insert(0)
minHeap.insert(1)
expect(minHeap.printMinHeap()).toEqual([0, 1])
})
})
describe('insert', () => {
test('inserts item at correct place in heap', () => {
const minHeap = new MinBinaryHeap(),
arr = [10, 3, 4, 8, 2, 9, 7, 1, 2, 6, 5]
for (const el of arr) {
minHeap.insert(el)
}
expect(minHeap.printMinHeap()).toEqual([1, 2, 4, 2, 5, 9, 7, 10, 3, 8, 6])
})
})
describe('scoped min heap', () => {
let minHeap, length
beforeEach(() => {
minHeap = new MinBinaryHeap()
const arr = [10, 3, 4, 8, 2, 9, 7, 1, 2, 6, 5]
length = arr.length
for (const el of arr) {
minHeap.insert(el)
}
})
describe('size', () => {
test('gets correct size of min heap', () => {
expect(minHeap.size).toEqual(length)
})
test('returns 0 if size of heap is 0', () => {
const minHeap = new MinBinaryHeap()
expect(minHeap.size).toBe(0)
})
})
describe('min', () => {
test('gets correct min of min heap', () => {
expect(minHeap.min).toBe(1)
})
test('returns null if size of heap is 0', () => {
const minHeap = new MinBinaryHeap()
expect(minHeap.min).toBe(null)
})
})
describe('extractMin', () => {
test('removes the correct min item from heap and returns it', () => {
const min = minHeap.extractMin(),
heapContent = [2, 2, 4, 3, 5, 9, 7, 10, 6, 8]
expect(min).toBe(1)
expect(minHeap.printMinHeap()).toEqual(heapContent)
})
test('returns null if size of heap is 0', () => {
const minHeap = new MinBinaryHeap()
expect(minHeap.min).toEqual(null)
})
})
describe('sinkDown', () => {
test('sinks parent down correct path if both left and right child are less than parent', () => {
const minHeap = new MinBinaryHeap(),
arr = [2, 3, 4, 5]
for (const el of arr) {
minHeap.insert(el)
}
const min = minHeap.extractMin(),
heapContent = [3, 5, 4]
expect(min).toBe(2)
expect(minHeap.printMinHeap()).toEqual(heapContent)
})
test('sinks parent down to the left if parent > left but parent < right', () => {
const minHeap = new MinBinaryHeap(),
arr = [2, 4, 6, 5]
for (const el of arr) {
minHeap.insert(el)
}
const min = minHeap.extractMin(),
heapContent = [4, 5, 6]
expect(min).toBe(2)
expect(minHeap.printMinHeap()).toEqual(heapContent)
})
test('sinks parent down to the right if parent < left but parent > right', () => {
const minHeap = new MinBinaryHeap(),
arr = [2, 6, 4, 7, 8, 5]
for (const el of arr) {
minHeap.insert(el)
}
const min = minHeap.extractMin(),
heapContent = [4, 6, 5, 7, 8]
expect(min).toBe(2)
expect(minHeap.printMinHeap()).toEqual(heapContent)
})
})
describe('remove', () => {
test('removes the correct item from heap', () => {
minHeap.remove(2)
const heapContent = [1, 2, 4, 3, 5, 9, 7, 10, 6, 8]
expect(minHeap.printMinHeap()).toEqual(heapContent)
})
})
})
})