src/utils/BinaryHeap.ts
export default class BinaryHeap {
private _elements
constructor (options) {
options = options || {}
this._elements = options.elements || []
this._score = options.score || this._score
}
add () {
for (let i = 0; i < arguments.length; i++) {
const element = arguments[i]
this._elements.push(element)
this._bubble(this._elements.length - 1)
}
}
first () {
return this._elements[0]
}
removeFirst () {
const root = this._elements[0]
const last = this._elements.pop()
if (this._elements.length > 0) {
this._elements[0] = last
this._sink(0)
}
return root
}
clone () {
return new BinaryHeap({
elements: this.toArray(),
score: this._score
})
}
toSortedArray () {
const array: any[] = []
const clone = this.clone()
while (true) {
const element = clone.removeFirst()
if (element === undefined) break
array.push(element)
}
return array
}
toArray () {
return [].concat(this._elements)
}
size () {
return this._elements.length
}
_bubble (bubbleIndex) {
const bubbleElement = this._elements[bubbleIndex]
const bubbleScore = this._score(bubbleElement)
while (bubbleIndex > 0) {
const parentIndex = this._parentIndex(bubbleIndex)
const parentElement = this._elements[parentIndex]
const parentScore = this._score(parentElement)
if (bubbleScore <= parentScore) break
this._elements[parentIndex] = bubbleElement
this._elements[bubbleIndex] = parentElement
bubbleIndex = parentIndex
}
}
_sink (sinkIndex) {
const sinkElement = this._elements[sinkIndex]
const sinkScore = this._score(sinkElement)
const length = this._elements.length
while (true) {
let swapIndex
let swapScore
let swapElement = null
const childIndexes = this._childIndexes(sinkIndex)
for (let i = 0; i < childIndexes.length; i++) {
const childIndex = childIndexes[i]
if (childIndex >= length) break
const childElement = this._elements[childIndex]
const childScore = this._score(childElement)
if (childScore > sinkScore) {
if (swapScore === undefined || swapScore < childScore) {
swapIndex = childIndex
swapScore = childScore
swapElement = childElement
}
}
}
if (swapIndex === undefined) break
this._elements[swapIndex] = sinkElement
this._elements[sinkIndex] = swapElement
sinkIndex = swapIndex
}
}
_parentIndex (index) {
return Math.floor((index - 1) / 2)
}
_childIndexes (index) {
return [
2 * index + 1,
2 * index + 2
]
}
_score (element) {
return element.valueOf()
}
}