堆

堆通常是一颗完全二叉树的数组对象，是非线性数据结构
堆通常有最大堆和最小堆两个分类

最大堆： 每个根节点的值都大于子节点
最小堆： 每个根节点的值都小于子节点

堆本质上一种二叉树，但使用的是数组形式

/*
                80
      29   38
    15 6  20 10 
     3 4    
*/
//  表示为数组的形式
var arr = [80, 29, 38, 15, 6, 20, 10, 3,4]

按照二叉树的每一排依次进行序号的排序，图中从上到下索引
如果节点不是最后一个子节点，那么这个节点必须包含左右两个子节点

节点索引的计算
对于序号为k的节点，它的左节点为 2k + 1, 右节点为 2k+2, 父节点为 (k - 1) / 2

堆的操作
堆化，维护最大、最小堆的过程，和子节点不断比较，将最大、最小值和父节点交换

实现堆

/*
        80
      29   38
    15 6  20 10 
   3 4    
*/
//  表示为数组的形式
var arr = [80, 29, 38, 15, 6, 20, 10, 3,4]
class MaxHeap {
    constructor(initArray, maxSize = 9999) {
        this.arr = initArray || []
        this.currSize = this.arr.length;
        this.maxSize = maxSize
        this.heap = new Array(this.arr.length)
        this.init()
    }
    init() {
        for (let i = 0; i < this.currSize; i++) {
            this.heap[i] = this.arr[i]
        }
        //如果initDataArray非空，那么需要对数据进行堆化。若initDataArray为空，此步可以省略
        // 获取最后一个分支节点的父节点的索引
        let curPos = Math.floor((this.curSize - 2) / 2)
        while(curPos >= 0) {
            // 局部的自上往下下滑调整
            this.upToDown(curPos, this.currSize - 1)
            curPos--;
        }
    }
    // 得到栈结构数组
    getHeap() {
        return this.heap;
    }
    // 由上至下堆化数据
    upToDown(start, m) {
        let parentIndex = start;
        // 左节点的值
        let maxChildIndex = parentIndex *2 + 1;
        while(maxChildIndex <= m) {
            // 如果右节点的值 > 左节点的值
            if (maxChildIndex < m && this.heap[maxChildIndex] < this.heap[maxChildIndex + 1]) {
                maxChildIndex = maxChildIndex + 1;
            }
            // 如果父节点值的大于子节点的值，不需要交换
            if (this.heap[parentIndex] >= this.heap[maxChildIndex]) {
                break
            } else {
                // 否则，交换父子节点的值
                let temp = this.heap[parentIndex]
                this.heap[parentIndex] = this.heap[maxChildIndex]
                this.heap[maxChildIndex] = temp;
                parentIndex = maxChildIndex
                maxChildIndex = maxChildIndex * 2 + 1
            }
        }
    }   
    insert(data) {
        // 当前容量大小等于最大容量，返回插入失败
        if (this.currSize == this.maxSize) return false;
        this.heap[this.currSize] = data;
        // 由下至上堆化数据
        this.downToUp(this.currSize);
        this.currSize++;
        return true;
    }
    // 由下至上堆化数据
    downToUp(start) {
        let childIndex = start;
        let parentIndex = Math.floor((childIndex - 1) / 2);
        while(childIndex > 0) {
            // 如果大就不交换
            if(this.heap[parentIndex] >= this.heap[childIndex]) {
                break
            } else {
                // 否则，交换父子节点的值
                let temp = this.heap[parentIndex]
                this.heap[parentIndex] = this.heap[childIndex]
                this.heap[childIndex] = temp;
                childIndex = parentIndex
                parentIndex = Math.floor((parentIndex - 1) / 2)
            }
        }
    }
    // 移除根元素并返回
    removeRoot() {
        if (this.currSize <= 0) return null;
        let maxValue = this.heap[0]
        this.heap[0] = this.heap[this.currSize]
        this.currSize--;
        // 重新堆化数据
        this.upToDown(0, this.currSize - 1);
        return maxValue;
    }
}
const maxHeap = new MaxHeap()
const initArray = [1,2,3,4,5]
for(let  i = 0; i < 5; i++) {
    maxHeap.insert(initArray[i])
} 
console.log(maxHeap.getHeap()) // [5,4,2,1,3]
console.log('max1:', maxHeap.removeRoot()) // 5
console.log(maxHeap.getHeap()) // [5,4,2,1,3]
console.log('max2:', maxHeap.removeRoot()) // 4
console.log(maxHeap.getHeap()) // [5,4,2,1,3]
console.log('max3:', maxHeap.removeRoot()) // 3
console.log(maxHeap.getHeap()) // [5,4,2,1,3]

小结

1. 堆的条件和生成堆的几个条件
2. 节点的索引计算
3. 堆的操作

练习题

报数。
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：

1.     1
2.     11
3.     21
4.     1211
5.     111221
1 被读作 "one 1" ("一个一") , 即 11。
11 被读作 "two 1s" ("两个一"）, 即 21。
21 被读作 "one 2", "one 1" （"一个二" , "一个一") , 即 1211。
给定一个正整数 n（1 ≤ n ≤ 30），输出报数序列的第 n 项。
输入: 1
输出: "1"
输入: 4
输出: "1211"

function countAndSay(n) {
        if ( n === 1) {
        return '1'
    }
      let origin = 1;
      let text = '';
    let html = '';
    while(origin <n) {
        if(!html) {
          html = `${origin}`
      }
      let arr = []
      let data = ''
      for (let i = 0, len = html.length; i <len; i++) {
        // 将字符中相同的数字做统计
          if (!data) {
            data += html[i]
        } else {
          // 如果碰到不同的数字，则将data清空，重新计算
          if (html[i] !== data[data.length - 1]) {
              arr.push(data)
            data = ''
          }
          data += html[i]
        }
      }
      arr.push(data)
      text = ''
      arr.forEach(item => {
          text += `${item.length}${item[0]}`
        html = text
      })
      origin++;
    }
  return text;
}