21-数据结构-二叉堆-一一网

二叉堆结构

二叉堆是一种特殊的二叉树，有以下两个特性：

1.它是一棵完全二叉树，表示树的每一层都有左侧和右侧子节点（除了最后一层的叶节点）

2.并且最后一层的叶节点尽可能都是左侧子节点，这叫作结构特性。

二叉堆不是最小堆就是最大堆。最小堆允许你快速导出树的最小值，最大堆允许你快速导出树的最大值。

所有的节点都大于等于（最大堆）或小于等于（最小堆）每个它的子节点。这叫作堆特性。

二叉堆合法不合法.png

在上图中：

图1第二层的右侧没有左右子节点，所以不合法。

图2第二层的左侧没有左右子节点，所以不合法。

图3右侧的最后一个子节点应该在左侧第二层的右侧子节点的位置上。

图4应该像图6那样。

图5符合二叉堆的两个特性，所以合法。

图6也符合二叉堆的两个特性，所以合法。

图7左侧第二层没有左侧子节点就有了右侧子节点4，不合法。

图8符合二叉堆的两个特性，所以合法。

二叉堆结构之实现最小堆结构

二叉树有两种表示方式。第一种是使用一个动态的表示方式，也就是指针（用节点表示），如下图左侧。第二种是使用一个数组，通过索引值检索父节点、左侧和右侧子节点的值，如下图右侧。

由于二叉堆的特性，所以每次新节点插入值的时候都会按照从上到下、从左往右的顺序插入。由此也可以将节点的值与数组的下标一一映射。

所有节点的左侧子节点的下标是：2 × 父节点的下标 + 1

所有节点的右侧子节点的下标是：2 × 父节点的下标 + 2

所有节点的父节点的下标是：Math.floor((当前节点的下标 - 1) / 2)

例如：节点1是第一个值，所以它的下标是0。节点1的左侧子节点2的下标就是2*0+1=1，节点1的右侧子节点3的下标就是2*0+0=2。

最小堆结构的插值操作

假设我们想要向这个堆中插入一个值1。

首先会检查根节点上有没有值，有值2。

所以再检查左侧子节点有没有值，有值3。

再检查右侧子节点有没有值，有值4。

再检查节点3的左侧子节点有没有值，有值5。

再检查节点3的右侧子节点有没有值，没有，所以先把值1插入到节点3的右侧子节点。

然后进行交换位置，节点1与节点3交换，然后节点2又与节点1交换。这样就完成了在最小堆结构中插入新值的操作。

最小堆结构移除最小值

移除最小值（最小堆）或最大值（最大堆）表示移除数组中的第一个元素（堆的根节点）。在移除后，我们将堆的最后一个元素直接移动到根节点位置，然后再慢慢与下面的节点进行交换。直到交换到堆的结构正常。

例如将最小堆中的根节点1移除。

首先将最后一个节点9从原来的位置上直接移到根节点的位置，

然后节点9与左侧子节点2比较，9大于2，交换位置，交换之后节点2在根节点的位置上，节点9成为节点2的左侧子节点。

然后节点9继续与左侧子节点4比较，9大于4，交换位置，交换之后节点9成为节点4的左侧子节点。

然后节点9继续与左侧子节点8比较，9大于8，交换位置，交换完成之后，节点9下方没有比它小的节点了，则堆结构正常。

最小堆结构的自我实现

class MinHeap{ // 因为二叉堆是完全按顺序来排列的，没有任何特殊结构，所以用类似数组的结构来表示就行，因为数组下标就是递增顺序的
    constructor() {
        this.heap = []
    }
    getLeftIndex(index){ // 指定节点的索引
        // 某个节点的左侧子节点索引
        return 2 * index + 1
    }

    getRightIndex(index){
        return 2 * index + 2
    }

    getParentIndex(index){
        if(index === 0){ // 如果是根节点，那么它没有父节点
            return undefined
        }
        // 剩下的就是非根节点的情况 减1减2都行，减1向下取整，减2向上取整
        return Math.floor((index-1)/2) // 左侧子节点的父节点是（i-1）/2，右侧子节点的父节点是（i-2）/2，所以减1用向下取整
    }

    insert(value){
        if(value){
            this.heap.push(value) // 把值添加到数组最后面
            // 提档，把数组中最小值提到最上面
            this.shiftUp(this.heap.length-1) // 从最后一个值开始一个个提档
            return true
        }
        // 如果没有值返回false
        return false
    }

    shiftUp(index){ // 提档
        let parentIndex = this.getParentIndex(index) // 获取父节点索引
        while(index > 0 && this.heap[parentIndex] > this.heap[index]){ // 一直往上交换，直到换到顶
            this.swap(this.heap,parentIndex,index)
            index = parentIndex
            parentIndex = this.getParentIndex(index)
        }
    }

    swap(arr,a,b){ // 交换
        let temp = arr[a]
        arr[a] = arr[b]
        arr[b] = temp
    }

    size(){
        return this.heap.length
    }

    isEmpty(){
        return this.heap.length === 0 // 方法一
        // return this.size() === 0 // 方法二
    }

    findMinValue(){
        return this.isEmpty()?undefined:this.heap[0]
    }

    extract(){ // 删除顶上最小值
        if(this.isEmpty()){ // 如果为空
            return undefined
        }
        if(this.size() === 1){
            return this.heap.shift()
        }
        let removeNode = this.heap[0] // 把当前最小的返回回去
        this.heap[0] = this.heap.pop() // 把最大一个挪到最前面
        this.shiftDown(0) // 最大的往下挪
        return removeNode
    }

    shiftDown(index){ // 一次次把最大值往下挪
        let currentIndex = index
        let leftIndex = this.getLeftIndex(index) // 获取左侧子节点
        let rightIndex = this.getRightIndex(index) // 获取右侧子节点
        let size = this.size() // 当索引超出长度的时候
        if(leftIndex < size && this.heap[currentIndex] > this.heap[leftIndex]){
            currentIndex = leftIndex
        }
        if(rightIndex < size && this.heap[currentIndex] > this.heap[rightIndex]){
            currentIndex = rightIndex
        }
        if(currentIndex !== index){
            this.swap(this.heap,currentIndex,index)
            this.shiftDown(currentIndex) // 递归
        }
    }
}
复制代码