怎样提高网站的流量,网站手机版模板免费下载,怎么样百度能搜到自己的网站,项目外包公司到底值不值得去一些概念
堆#xff1a;特殊的完全二叉树#xff0c;具有特定性质的完全二叉树。大根堆#xff1a;父节点 子节点小根堆#xff1a;父节点 子节点
二叉堆也属于完全二叉树#xff0c;所以可以用数组表示。
若下标从1开始#xff0c;左节点为 2*i #xff0…一些概念
堆特殊的完全二叉树具有特定性质的完全二叉树。大根堆父节点 子节点小根堆父节点 子节点
二叉堆也属于完全二叉树所以可以用数组表示。
若下标从1开始左节点为 2*i 右节点为 2*i1 父节点为 i//2 。若下标从1开始左节点为 2*i1 右节点为 2*i12 父节点为 (i-1)//2 。
最大堆
两个重要方法插入元素和移出元素。
插入元素在堆尾插入元素调用辅助方法将该元素上浮到正确位置。移出元素将堆尾元素删去并替换到堆首将该元素下沉到正确位置。
解释
上浮如果父节点更大则替换循环直至比父节点小。下沉如果子节点中较大的那个更小则替换循环直至子节点都比自身小。
实现
class MaxHeap {constructor() {this.heap []}isEmpty() {return this.heap.length 0}size() {return this.heap.length}#getParentIndex(idx) {return Math.floor((idx-1)/2)}#getLeft(idx) {return idx * 2 1}#getRight(idx) {return idx * 2 2}// 插入insert(v) {this.heap.push(v)this.#swim(this.size()-1)}// 删除最大值deleteMax() {const max this.heap[0]this.#swap(0, this.size() - 1) // 将根和最后一个元素交换this.heap.pop() // 防止对象游离this.#sink(0) // 下沉恢复有序性return max}// 第i个是否小于第j个#compare(a, b) {return a b}// 交换#swap(i, j) {[this.heap[i], this.heap[j]] [this.heap[j], this.heap[i]]}// 上浮#swim(k) {let parent this.#getParentIndex(k)while(k 0 this.#compare(this.heap[parent], this.heap[k])) {this.#swap(parent, k)k parentparent this.#getParentIndex(k)}}// 下沉#sink(k) {while (this.#getLeft(k) this.size()) {let j this.#getLeft(k)// j 指向子节点的较大值if (j1 this.size() this.#compare(this.heap[j], this.heap[j1])) j// 如果子节点都小if (this.#compare(this.heap[j], this.heap[k])) breakthis.#swap(k, j)k j}}
}测试
const mh new MaxHeap()
mh.insert(20)
mh.insert(80)
mh.insert(50)
mh.insert(40)
mh.insert(30)
mh.insert(40)
mh.insert(20)
mh.insert(10)
mh.insert(35)
mh.insert(15)
mh.insert(90)
console.log(mh.heap)
// [ 1 empty item, 90, 80, 50, 35, 40, 40, 20, 10, 20, 15, 30 ]
mh.deleteMax()
mh.deleteMax()
mh.deleteMax()
console.log(mh.heap)
// [ 1 empty item, 40, 35, 40, 20, 30, 15, 20, 10 ]最小堆
与最小堆相比仅是交换条件不同
实现
class MinHeap {constructor() {this.heap []}isEmpty() {return this.heap.length 0}size() {return this.heap.length}#getParentIndex(idx) {return Math.floor((idx-1)/2)}#getLeft(idx) {return idx * 2 1}#getRight(idx) {return idx * 2 2}// 插入insert(v) {this.heap.push(v)this.#swim(this.size()-1)}// 删除最大值deleteMin() {const max this.heap[0]this.#swap(0, this.size() - 1) // 将根和最后一个元素交换this.heap.pop() // 防止对象游离this.#sink(0) // 下沉恢复有序性return max}// 第i个是否小于第j个#compare(a, b) {return a b}// 交换#swap(i, j) {[this.heap[i], this.heap[j]] [this.heap[j], this.heap[i]]}// 上浮#swim(k) {let parent this.#getParentIndex(k)while(k 0 this.#compare(this.heap[parent], this.heap[k])) {this.#swap(parent, k)k parentparent this.#getParentIndex(k)}}// 下沉#sink(k) {while (this.#getLeft(k) this.size()) {let j this.#getLeft(k)// j 指向子节点的较小值if (j1 this.size() this.#compare(this.heap[j], this.heap[j1])) j// 如果子节点都大if (this.#compare(this.heap[j], this.heap[k])) breakthis.#swap(k, j)k j}}
}测试
const mh new MinHeap()
mh.insert(20)
mh.insert(80)
mh.insert(50)
mh.insert(40)
mh.insert(30)
mh.insert(40)
mh.insert(20)
mh.insert(10)
mh.insert(35)
mh.insert(15)
mh.insert(90)
console.log(mh.heap)
// [10, 15, 20, 30, 20, 50, 40, 80, 35, 40, 90]
mh.deleteMin()
mh.deleteMin()
mh.deleteMin()
console.log(mh.heap)
// [20, 30, 40, 35, 40, 50, 90, 80]堆自定义比较函数
默认为最大堆根据元素的大小进行排序可自定义排序规则返回值为布尔值。
class Heap {constructor(compareFn) {this.heap []this.compare (typeof compareFn function) ? compareFn : this.#defaultCompare}isEmpty() {return this.heap.length 0}size() {return this.heap.length}#getParentIndex(idx) {return Math.floor((idx-1)/2)}#getLeft(idx) {return idx * 2 1}#getRight(idx) {return idx * 2 2}// 插入insert(v) {this.heap.push(v)this.#swim(this.size()-1)}// 删除最大值delete() {const max this.heap[0]this.#swap(0, this.size() - 1) // 将根和最后一个元素交换this.heap.pop() // 防止对象游离this.#sink(0) // 下沉恢复有序性return max}// 第i个是否小于第j个#defaultCompare(a, b) {return a b}// 交换#swap(i, j) {[this.heap[i], this.heap[j]] [this.heap[j], this.heap[i]]}// 上浮#swim(k) {let parent this.#getParentIndex(k)while(k 0 this.compare(this.heap[parent], this.heap[k])) {this.#swap(parent, k)k parentparent this.#getParentIndex(k)}}// 下沉#sink(k) {while (this.#getLeft(k) this.size()) {let j this.#getLeft(k)// j 指向子节点的较大值if (j1 this.size() this.compare(this.heap[j], this.heap[j1])) j// 如果子节点都小if (this.compare(this.heap[j], this.heap[k])) breakthis.#swap(k, j)k j}}
}测试
const mh new Heap((a,b)a.valb.val)
mh.insert({val: 20})
mh.insert({val: 45})
mh.insert({val: 56})
mh.insert({val: 12})
mh.insert({val: 93})
mh.insert({val: 34})
mh.insert({val: 12})
mh.insert({val: 84})
console.log(mh.heap)
// [
// { val: 93 },
// { val: 84 },
// { val: 45 },
// { val: 56 },
// { val: 20 },
// { val: 34 },
// { val: 12 },
// { val: 12 }
// ]
mh.delete()
mh.delete()
console.log(mh.heap)
// [
// { val: 56 },
// { val: 20 },
// { val: 45 },
// { val: 12 },
// { val: 12 },
// { val: 34 }
// ]堆排序
1先原地创建一个最大堆因为叶子节点没有子节点因此只需要对非叶子节点从右向左进行下沉操作
2把堆首堆的最大值和堆尾替换位置堆大小减一保持非堆是递增的保持数组最后一个元素是最大的最后对堆首进行下沉操作或者说把非堆重新堆化。
3重复第二步直至清空堆。
注意排序的数组第一个元素下标是 0 跟上面处理边界不一样。
实现
function heapSort (arr) {// arr arr.slice(0) // 是否原地排序let N arr.length - 1if (!arr instanceof Array) {return null}else if (arr instanceof Array (N 0 || N -1) ) {return arr}function exch(i, j) {[arr[i], arr[j]] [arr[j], arr[i]]}function less(i, j) {return arr[i] arr[j]}function sink(k) {while (2 *k 1 N) {let j 2 * k 1// j 指向子节点的较大值if (j1 N less(j, j1)) {j}// 如果子节点都小if (less(j, k)) breakexch(k, j)k j}}// 构建堆for(let i Math.floor(N/2); i 0; i--) {sink(i)}// 堆有序while (N 0) {exch(0, N--)sink(0)}
}另一个实现
function heapSort (arr) {// arr arr.slice(0) // 是否原地排序let N arr.lengthif (!arr instanceof Array) {return null}else if (arr instanceof Array (N 0 || N -1) ) {return arr}function getParentIndex(idx) {return Math.floor((idx-1)/2)}function getLeft(idx) {return idx * 2 1}function getRight(idx) {return idx * 2 2}function swap(i, j) {[arr[i], arr[j]] [arr[j], arr[i]]}function compare(i, j) {return i j}function sink(k) {while (getLeft(k) N) {let j getLeft(k)// j 指向子节点的较大值if (j1 N compare(arr[j], arr[j1])) j// 如果子节点都小if (compare(arr[j], arr[k])) breakswap(k, j)k j}}// 构建堆for(let i Math.floor(N/2); i 0; i--) {sink(i)}// 堆有序while (N 1) {swap(0, --N)sink(0)}
}测试
const arr1 [15, 20, 30, 35, 20, 50, 40, 80, 10, 40, 90]
heapSort(arr1)
console.log(arr1)
// [10, 15, 20, 20, 30, 35, 40, 40, 50, 80, 90]
const arr2 [62, 88, 58, 47, 35, 73, 51, 99, 37, 93];
heapSort(arr2)
console.log(arr2)
// [35, 37, 47, 51, 58, 62, 73, 88, 93, 99]参考
algs4【JS手写最小堆小顶堆、最大堆大顶堆】https://juejin.cn/post/7128369000001568798【数据结构与算法(4)——优先队列和堆】https://zhuanlan.zhihu.com/p/39615266【最大堆最小堆及堆排序】https://mingshan.fun/2019/05/14/heap/【搞定JavaScript算法系列–堆排序】https://juejin.cn/post/6844903830258188296
