堆(优先队列)

堆可以用来排序，还可以用来解决“最值问题”，可以高效的处理动态集合的最值问题，这样就解决了排序的缺点。
堆是一颗完全二叉树，且这颗树中，节点之间也有顺序，顺序：任何一个结点都比其两个子节点的值要大于等于，类比于BST中，左子树所有结点比根节点大，根节点比右子树中所有结点大
由于它是一棵完全二叉树的特性，它一般是使用简单数据的形式进行存储，这样存储不会浪费一点空间，同时也依然很容易根据一个元素找到其父元素或子元素

删除堆顶元素并调整堆中元素的位置的代码

//从heap中删除堆顶元素并返回
//同时调整它让它继续满足堆的性质
//heap是一个数组
function 删除堆顶元素(heap) {if(heap.length <= 1{return heap.pop()}var result = heap[0]; // 取出堆定元素heap[0] = heap.pop(); // 将末尾元素放入堆定var idx = 0;while (true) {var leftIdx = idx * 2 + 1;var rightIdx = idx * 2 + 2;var maxIdx = idx; //先假设此时的根元素是最大的//左子结点存在并且大于当前最大元素if (leftIdx < heap.length && heap[leftIdx] > heap[maxIdx]) {maxIdx = leftIdx;}//右结点存在并且大于当前最大元素if (rightIdx < heap.length && heap[rightIdx] > heap[maxIdx]) {maxIdx = rightIdx;}if (maxIdx !== idx) {swap(heap, maxIdx, idx);idx = maxIdx; //从末尾上来的元素换到了哪里，哪里就是新的焦点} else {break;}}return result;
}function swap(array, i, j) {var t = array[i];array[i] = array[j];array[j] = t;
}

向堆中添加元素

function swap(array, i, j) {var t = array[i];array[i] = array[j];array[j] = t;
}function 向堆中添加元素(heap, val) {heap.push(val);heapUp(heap, heap.length - 1);return heap;
}function heapUp(heap, idx) {//除2取整while (idx > 0) {//计算出焦点元素父节点的位置var pIdx = (idx - 1) >> 1;if (heap[pIdx] < heap[idx]) {swap(heap, pIdx, idx);idx = pIdx;} else {break;}}
}

数组的堆化

function swap(array, i, j) {var t = array[i];array[i] = array[j];array[j] = t;
}
function heapDown(heap, idx) {while (true) {var leftIdx = idx * 2 + 1;var rightIdx = idx * 2 + 2;var maxIdx = idx; //先假设此时的根元素是最大的//左子结点存在并且大于当前最大元素if (leftIdx < heap.length && heap[leftIdx] > heap[maxIdx]) {maxIdx = leftIdx;}//右结点存在并且大于当前最大元素if (rightIdx < heap.length && heap[rightIdx] > heap[maxIdx]) {maxIdx = rightIdx;}if (maxIdx !== idx) {swap(heap, maxIdx, idx);idx = maxIdx; //从末尾上来的元素换到了哪里，哪里就是新的焦点} else {break;}}
}function heapify(array) {for (var i = array.length - 1; i >= 0; i--) {heapDown(array, i);}return array;
}

堆排序

空间复杂度1，时间复杂度n * log(n)

function swap(array, i, j) {var t = array[i];array[i] = array[j];array[j] = t;
}
//最多调整到stop位置，不包含stop位置
function heapDown(heap, idx, stop = heap.length) {while (true) {var leftIdx = idx * 2 + 1;var rightIdx = idx * 2 + 2;var maxIdx = idx; //先假设此时的根元素是最大的//左子结点存在并且大于当前最大元素if (leftIdx < stop && heap[leftIdx] > heap[maxIdx]) {maxIdx = leftIdx;}//右结点存在并且大于当前最大元素if (rightIdx < stop && heap[rightIdx] > heap[maxIdx]) {maxIdx = rightIdx;}if (maxIdx !== idx) {swap(heap, maxIdx, idx);idx = maxIdx; //从末尾上来的元素换到了哪里，哪里就是新的焦点} else {break;}}
}
function heapify(array) {for (var i = array.length - 1; i >= 0; i--) {heapDown(array, i);}return array;
}
function heapSort(array) {heapify(array); for (var i = array.length - 1; i > 0; i--) {swap(array, i, 0);heapDown(array, 0, i);}return array;
}

构造大顶堆类

class PriorityQueue {constructor(init = []) {this.heap = []for (var item of init) {this.heap.push(item)}this.heapify()}heapify() {for (var i = (this.heap.length - 2) >> 1; i >= 0; i--) {this.heapDown(i)}return this}swap(array, i, j) {if (i !== j) {var t = array[i]array[i] = array[j]array[j] = t}}// 从堆heap中删除零顶元素并返回// 同时调整它让它继续满足堆的性质remove() {if (this.heap.length <= 1) {return this.heap.pop()}var result = this.heap[0] // 取出堆顶元素this.heap[0] = this.heap.pop() // 将末尾元素放入堆顶this.heapDown(0)return result}add(val) {this.heap.push(val)this.heapUp(this.heap.length - 1)return this}heapUp(idx) {while (idx > 0) {var pIdx = (idx - 1) >> 1 // 计算出焦点的父元素位置if (this.heap[pIdx] < this.heap[idx]) {this.swap(this.heap, pIdx, idx)idx = pIdx} else {break}}}// 从idx位置开始向下调整heapDown(idx) {while (true) {var leftIdx = idx * 2 + 1var rightIdx = idx * 2 + 2var maxIdx = idx // 先假设此时的根元素是最大的// 左子结点存在并且大于当前当前最大元素if (leftIdx < this.heap.length && this.heap[leftIdx] > this.heap[maxIdx]) {maxIdx = leftIdx}// 右子结点存在并且大于当前当前最大元素if (rightIdx < this.heap.length && this.heap[rightIdx] > this.heap[maxIdx]) {maxIdx = rightIdx}if (maxIdx !== idx) {this.swap(this.heap, maxIdx, idx)idx = maxIdx // 从末尾上来的元素换到了哪里,哪里就是新的焦点} else {break}}}}