作者:紫青郝_385 | 来源:互联网 | 2020-08-03 08:35
本篇文章给大家带来的内容是关于Javascript中二叉树(二叉堆)的介绍(代码示例),有一定的参考价值,有需要的朋友可以参考一下,希望对你有所帮助。
二叉树
二叉树(Binary Tree)是一种树形结构,它的特点是每个节点最多只有两个分支节点,一棵二叉树通常由根节点,分支节点,叶子节点组成。而每个分支节点也常常被称作为一棵子树。
从上图可以看出:
二叉堆的主要操作
insert:插入节点
delete:删除节点
max-hepify:调整分支节点堆性质
rebuildHeap:重新构建整个二叉堆
sort:排序
初始化一个二叉堆
从上面简单的介绍,我们可以知道,一个二叉堆的初始化非常的简单,它就是一个数组
class Heap{
constructor(arr){
this.data = [...arr];
this.size = this.data.length;
}
}
max-heapify最大堆操作
max-heapify是把每一个不满足最大堆性质的分支节点进行调整的一个操作。
如上图:
调整分支节点2(分支节点2不满足最大堆的性质)
将2与左右分支比较,从2,12,5中找出最大值,然后和2交换位置
重复step2的操作,从2,4,7中找出最大值与2做交换
maxHeapify(i) {
let max = i;
if(i >= this.size){
return;
}
// 当前序号的左节点
const l = i * 2 + 1;
// 当前需要的右节点
const r = i * 2 + 2;
// 求当前节点与其左右节点三者中的最大值
if(l this.data[max]){
max = l;
}
if(r this.data[max]){
max = r;
}
// 最终max节点是其本身,则已经满足最大堆性质,停止操作
if(max === i) {
return;
}
// 父节点与最大值节点做交换
const t = this.data[i];
this.data[i] = this.data[max];
this.data[max] = t;
// 递归向下继续执行
return this.maxHeapify(max);
}
重构堆
我们可以看到,刚初始化的堆由数组表示,这个时候它可能并不满足一个最大堆或最小堆的性质,这个时候我们可能需要去将整个堆构建成我们想要的。
上面我们做了max-heapify操作,而max-heapify只是将某一个分支节点进行调整,而要将整个堆构建成最大堆,则需要将所有的分支节点都进行一次max-heapify操作,如下图,我们需要依次对12,3,2,15这4个分支节点进行max-hepify操作
具体步骤:
rebuildHeap(){
// 叶子节点
const L = Math.floor(this.size / 2);
for(let i = L - 1; i>=0; i--){
this,maxHeapify(i);
}
}
最大堆排序
最大堆的排序,如上图所示:
sort() {
for(let i = this.size - 1; i > 0; i--){
swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}
插入和删除
这个的插入和删除就相对比较简单了,就是对一个数组进行插入和删除的操作
往末尾插入
堆长度+1
判断插入后是否还是一个最大堆
不是则进行重构堆
insert(key) {
this.data[this.size] = key;
this.size++
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
删除数组中的某个元素
堆长度-1
判断是否是一个堆
不是则重构堆
delete(index) {
if (index >= this.size) {
return;
}
this.data.splice(index, 1);
this.size--;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
完整代码
/**
* 最大堆
*/
function left(i) {
return i * 2 + 1;
}
function right(i) {
return i * 2 + 2;
}
function swap(A, i, j) {
const t = A[i];
A[i] = A[j];
A[j] = t;
}
class Heap {
constructor(arr) {
this.data = [...arr];
this.size = this.data.length;
}
/**
* 重构堆
*/
rebuildHeap() {
const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i--) {
this.maxHeapify(i);
}
}
isHeap() {
const L = Math.floor(this.size / 2);
for (let i = L - 1; i >= 0; i++) {
const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER;
const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER;
const max = Math.max(this.data[i], l, r);
if (max !== this.data[i]) {
return false;
}
return true;
}
}
sort() {
for (let i = this.size - 1; i > 0; i--) {
swap(this.data, 0, i);
this.size--;
this.maxHeapify(0);
}
}
insert(key) {
this.data[this.size++] = key;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
delete(index) {
if (index >= this.size) {
return;
}
this.data.splice(index, 1);
this.size--;
if (this.isHeap()) {
return;
}
this.rebuildHeap();
}
/**
* 堆的其他地方都满足性质
* 唯独跟节点,重构堆性质
* @param {*} i
*/
maxHeapify(i) {
let max = i;
if (i >= this.size) {
return;
}
// 求左右节点中较大的序号
const l = left(i);
const r = right(i);
if (l this.data[max]) {
max = l;
}
if (r this.data[max]) {
max = r;
}
// 如果当前节点最大,已经是最大堆
if (max === i) {
return;
}
swap(this.data, i, max);
// 递归向下继续执行
return this.maxHeapify(max);
}
}
module.exports = Heap;
总结
堆讲到这里就结束了,堆在二叉树里相对会比较简单,常常被用来做排序和优先级队列等。堆中比较核心的还是max-heapify这个操作,以及堆的三个性质。
以上就是Javascript中二叉树(二叉堆)的介绍(代码示例)的详细内容,更多请关注 第一PHP社区 其它相关文章!