Skip to content

Instantly share code, notes, and snippets.

@dsasse07
Last active Jun 22, 2021
Embed
What would you like to do?
MaxHeap with heapify & Heap sort
class MaxHeap {
constructor(arr = []){
this.size = 0
this.values = this._heapify(arr)
}
insert(value){
// If no value, do nothing
if (value === undefined) return
// Insert the value, and increment the size of the heap
this.values.push(value)
this.size++
// Check to see if there is not more than 1 item in the heap
// If there is only 1 item, there is no need to bubble up
if (this.size > 1) this._bubbleUp()
return this.values
}
extract(){
if (this.size === 0) return
const lastIndex = this.size - 1
this.size--
this._swap(0, lastIndex)
const extractValue = this.values.pop()
if (this.size > 1) this._trickleDown()
return extractValue
}
// Helper function using object destructuring to swap the elements at two indices
_swap(index1, index2){
[this.values[index1], this.values[index2]] = [this.values[index2], this.values[index1]]
}
_heapify(arr){
if (this.size > 0) return // Optional: Prevent overriding existing heap values
this.size = arr.length
/**
* To prevent mutating current array, replace line 18 with
* this.values = [...arr]
*/
this.values = arr
const nodeCount = this.size - 1
// Finds the last node of the tree that has children
let cIdx = Math.floor((nodeCount - 2)/2)
/** For each node up through the root,
* call trickleDown
*/
for (let i = cIdx; i >= 0; i--){
this._trickleDown(i)
}
return this.values
}
_bubbleUp(){
// Grab the most recently added value and its parent
let currentIndex = this.size - 1
let parentIndex = Math.floor( (currentIndex - 1) / 2 )
// Swap the new node with its parent until the new node either
// becomes the root, or is no longer greater than its parent
while (parentIndex >= 0 && this.values[currentIndex] > this.values[parentIndex]){
this._swap(currentIndex, parentIndex)
currentIndex = parentIndex
parentIndex = Math.floor((currentIndex - 1) / 2 )
}
}
_trickleDown(start = 0, stop = this.size){
let currentIndex = start
/**
* These will be the indexes corresponding to the left and right
* child of the node at currentIndex
* swapIdx will be which of the children the currentIndex will
* actually switch with, if any
*/
let leftIdx, rightIdx, swapIdx
while (true) {
leftIdx = 2 * currentIndex + 1
rightIdx = 2 * currentIndex + 2
swapIdx = null
/**
* If there is a valid left child and it is greater than the current value,
* prepare to swap it
*/
if (
leftIdx < stop &&
this.values[currentIndex] < this.values[leftIdx]
) {
swapIdx = leftIdx
}
/**
* If there is a valid right child and it is greater than the current value,
* prepare to swap it if we haven't already prepared to swap with left child.
* If we have prepared to swap with left child, we should only choose to swapIdx
* with the right child instead if it is greater than the left child, meaning
* it better fits the heap rule
*/
if (
rightIdx < stop &&
((swapIdx === null &&
this.values[currentIndex] < this.values[rightIdx]) ||
(swapIdx !== null && this.values[rightIdx] > this.values[leftIdx]))
) {
swapIdx = rightIdx
}
if (swapIdx === null) break // If no possibel swap was ID'd, we're done
// Swap the parent with the identified child, update the currentIndex, and repeat
this._swap(currentIndex, swapIdx)
currentIndex = swapIdx
}
}
static heapSort(arr){
const heap = new MaxHeap(arr)
for (let i = arr.length - 1; i > 0; i--){
heap._swap(0,i)
heap._trickleDown(0, i)
}
return heap.values
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment