二叉堆是一种特殊的二叉树。
- 它是一颗完全二叉树,表示树的每一层都有左侧和右侧子节点(除了最后一层的叶节点),并且最后一层的叶节点尽可能都是左侧子节点,这叫结构特性。
- 二叉堆不是最小堆就是最大堆。最小堆允许快速导出树的最小值,最大堆允许快速导出输的最大值。所有的节点都大于等于(最大堆)或小于等于(最小堆)每个它的子节点。这叫堆特性。
// 创建最小堆 class MinHeap { constructor(compareFn = defaultCompare){ this.compareFn = compareFn this.heap = [] } } MinHeap.prototype.getLeftIndex = function(index){ return 2 * index + 1 } MinHeap.prototype.getRightIndex = function(index){ return 2 * index + 2 } MinHeap.prototype.getParentIndex = function(index){ if(index === 0){ return undefined } return Math.floor((index - 1) / 2) } MinHeap.prototype.insert = function(value){ if(value != null){ this.heap.push(value) this.shiftUp(this.heap.length - 1) } } MinHeap.prototype.shiftUp = function(index){ let parentIndex = this.getParentIndex(index) while(index > 0 && this.heap[parentIndex] > this.heap[index]){ swap(this.heap,parentIndex,index) index = parentIndex parentIndex = this.getParentIndex(index) } } MinHeap.prototype.size = function(){ return this.heap.length } MinHeap.prototype.isEmpty = function(){ return this.size() == 0 } MinHeap.prototype.findMinimum = function(){ return this.isEmpty() ? undefined : this.heap[0] } MinHeap.prototype.extract = function(){ if(this.isEmpty()){ return undefined } if(this.size() == 1){ return this.heap.shift() } const removedValue = this.heap.shift() this.shiftDown(0) return removedValue } MinHeap.prototype.shiftDown = function(index){ let element = index const left = this.getLeftIndex(index) const right = this.getRightIndex(index) const size = this.size() if(left < size && this.heap[element] - this.heap[left] > 0){ element = left }else if(right < size && this.heap[element] - this.heap[right] > 0){ element = right } if(index !== element){ swap(this.heap,index,element) this.shiftDown(element) } }