二叉树

二叉树(Binary Tree)是一种树形结构，它的特点是每个节点最多只有两个分支节点，一棵二叉树通常由根节点，分支节点，叶子节点组成。而每个分支节点也常常被称作为一棵子树。

常用术语

在二叉树中，我们常常还会用父节点和子节点来描述，比如图中2为6和3的父节点，反之6和3是2子节点

二叉树的三个性质

1. 在二叉树的第i层上，至多有2^i-1个节点

2. i=1时，只有一个根节点，2^(i-1) = 2^0 = 1

3. 深度为k的二叉树至多有2^k-1个节点

4. i=2时，2^k-1 = 2^2 - 1 = 3个节点

5. 对任何一棵二叉树T，如果总结点数为n0，度为2(子树数目为2)的节点数为n2,则n0=n2+1

树和二叉树的三个主要差别

二叉树分类

二叉树分为完全二叉树(complete binary tree)和满二叉树(full binary tree)

二叉树的数组表示

用一个数组来表示二叉树的结构，将一组数组从根节点开始从上到下，从左到右依次填入到一棵完全二叉树中，如下图所示

通过上图我们可以分析得到数组表示的完全二叉树拥有以下几个性质：

二叉堆

二叉堆由一棵完全二叉树来表示其结构，用一个数组来表示，但一个二叉堆需要满足如下性质：

从上图可以看出：

二叉堆的主要操作

初始化一个二叉堆

从上面简单的介绍，我们可以知道，一个二叉堆的初始化非常的简单，它就是一个数组

 class Heap{
 constructor(arr){
 this.data = [...arr];
 this.size = this.data.length;
 }
 }

max-heapify最大堆操作

max-heapify是把每一个不满足最大堆性质的分支节点进行调整的一个操作。

如上图：

1. 调整分支节点2（分支节点2不满足最大堆的性质）

2. 默认该分支节点为最大值

3. 将2与左右分支比较，从2，12，5中找出最大值，然后和2交换位置

4. 根据上面所将的二叉堆性质，分别得到分支节点2的左节点和右节点

5. 比较三个节点，得到最大值的下标max

6. 如果该节点本身就是最大值，则停止操作

7. 将max节点与父节点进行交换

8. 重复step2的操作，从2，4，7中找出最大值与2做交换

9. 递归

 maxHeapify(i) {
 let max = i;
 
 if(i >= this.size){
 return;
 }
 // 当前序号的左节点
 const l = i * 2 + 1;
 // 当前需要的右节点
 const r = i * 2 + 2;
 
 // 求当前节点与其左右节点三者中的最大值
 if(l < this.size && this.data[l] > this.data[max]){
 max = l;
 }
 if(r < this.size && this.data[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);
 }
 }

插入和删除

这个的插入和删除就相对比较简单了，就是对一个数组进行插入和删除的操作

 insert(key) {
 this.data[this.size] = key;
 this.size++
 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();
 }

完整代码

/**
 * 最大堆
 */

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.size && this.data[l] > this.data[max]) {
 max = l;
 }

 if (r < this.size && this.data[r] > this.data[max]) {
 max = r;
 }

 // 如果当前节点最大，已经是最大堆
 if (max === i) {
 return;
 }

 swap(this.data, i, max);

 // 递归向下继续执行
 return this.maxHeapify(max);
 }
}

module.exports = Heap;

总结

堆讲到这里就结束了，堆在二叉树里相对会比较简单，常常被用来做排序和优先级队列等。堆中比较核心的还是max-heapify这个操作，以及堆的三个性质。