堆排序的删除和添加

function Heap(type = &＃39;min&＃39;) {this.type = type;this.value = [];
}Heap.prototype.create = function () {const length = this.value.length;// 构建大顶堆 for (let i = Math.floor((length / 2) - 1); i >= 0; i--) {this.ajust(i, length);}
}Heap.prototype.ajust = function (index, length) {const array = this.value;for (let i = 2 * index + 1; i array[i]) || // 找出2个孩子最大的一个(this.type === &＃39;min&＃39; && array[i + 1] [array[i]])) {[array[index], array[i]] = [array[i], array[index]];index = i;} else {break;}}
}
// 由于堆属于优先队列 只能从末尾添加
Heap.prototype.add = function (element) {const array = this.value;array.push(element);if (array.length > 1) {let index = array.length - 1;let target = Math.floor((index - 1) / 2);while (target >= 0) {if ((this.type === &＃39;min&＃39; && array[index] array[target])) {[array[index], array[target]] = [array[target], array[index]]index = target;target = Math.floor((index - 1) / 2);} else {break;}}}
}Heap.prototype.pop = function () {const array = this.value;let result = null;if (array.length > 1) {result = array[0];array[0] = array.pop();this.ajust(0, array.length);} else if (array.length === 1) {return array.pop();}return result;
}var heap = new Heap(&＃39;max&＃39;);
heap.add(6)
heap.add(10)
heap.add(12)console.log(heap.value);
console.log(heap.pop());
console.log(heap.value)// 最小堆
class MinHeap {constructor() {this.heap = [];}getParentIndex(i) {return (i - 1) >> 1;}getLeftIndex(i) {return i * 2 + 1;}getRightIndex(i) {return i * 2 + 2;}shiftUp(index) {if(index === 0) { return; }const parentIndex = this.getParentIndex(index);if(this.heap[parentIndex] > this.heap[index]){this.swap(parentIndex, index);this.shiftUp(parentIndex);} }swap(i1, i2) {const temp = this.heap[i1];this.heap[i1]= this.heap[i2];this.heap[i2] = temp;}insert(value) {this.heap.push(value);this.shiftUp(this.heap.length - 1);}pop() {this.heap[0] = this.heap.pop();this.shiftDown(0);return this.heap[0];}shiftDown(index) {const leftIndex = this.getLeftIndex(index);const rightIndex = this.getRightIndex(index);if (this.heap[leftIndex] }作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/chou-shu-lcof/solution/chou-shu-by-leetcode-solution-0e5i/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。