图解二叉堆（优先队列）TS实现

结构性：用数组表示的完全二叉树

堆序性：任意一个根节点比其所有子树节点大（小）

我们以数组作为存储结构，这样直接就可以明白，二叉堆需要的是完全二叉树即除了最后一层其他层都需要填满且最后一层的节点需要满足从左往右。

节点关系：

对于给定的节点i（假设数组索引从0开始）：

• 父节点的索引是 (i - 1) / 2（向下取整）。
• 左节点的索引是 2 * i + 1。
• 右节点的索引是 2 * i + 2。

重点思想

图解以大根堆为例子

增加元素

**时间复杂度**O(logN)

在底层最右侧添加节点，并不断与父节点进行比较，直到父节点比它小或者大于根节点。

上浮代码实现

swim(node:number){
  // 处于堆顶
    if(node == 0){
        return;
    }
  // 不断与父节点比较替换
    while(this.comp(this.heap[node], this.heap[this.parent(node)])){
        this.swap(node, this.parent(node));
        // 指针移动
        node = this.parent(node);
    }
}

往堆底添加元素

上浮操作

还原堆序性

刪除元素

**时间复杂度**O(logN)

移除最顶根节点，并把底层最右侧的节点移到堆顶，然后不断寻找子树最小节点交换，直到本身都小于子树。

下沉代码实现

private sink(node:number){
        // 传入参数不对
        if(node < 0){
            return;
        }
        // 边界
        while(this.left(node) < this.size() || this.right(node) < this.size()){
            let min_nodex = node;
            // 检测左子树
            if(this.left(node) < this.size() && this.comp(this.heap[this.left(node)], this.heap[min_nodex])){
                min_nodex = this.left(node);
            }
            // 检测右子树
            if(this.right(node) < this.size() && this.comp(this.heap[this.right(node)], this.heap[min_nodex])){
                min_nodex = this.right(node);
            }

            if(min_nodex == node){
                break;
            }
            // 与符合值交换
            this.swap(min_nodex, node);
            // 指针移动
            node = min_nodex;
        }
        
    }

弹出堆顶元素

将堆底元素移到堆顶

对堆顶元素进行 下沉 操作

还原堆序性

TS代码实现

注意此实现没有包括扩容缩容操作，读者需要的话可以自行实现。

class PriorityQueue<T>{
    private heap:T[];
    private _size:number;
  	private comp:(x:T, y:T)=>boolean;
    constructor(comp:(x:T, y:T)=>boolean){
        this.heap = [];
        this._size = 0;
    		this.comp = comp;
    }
    // 堆的大小
    public size(){
        return this._size;
    }
    // 判断堆是否为空
    public isEmpty(){
        return this._size === 0;
    }
    // 添加元素
    public push(val:T){
        this.heap.push(val);
        this._size++;
        this.swim(this.size() - 1);
    }
    // 弹出元素
    public pop():T{
        if(this.isEmpty()){
            throw new Error("PriorityQueue pop error, queue is empty");
        }
        let val = this.heap[0];
        // 将堆底节点移到堆顶
        this.heap[0] = this.heap[this._size-1];
        // 对原本在堆底的节点下沉操作
    		this.sink(0);
        this._size--;
        return val;
    }
    // 获得节点的父节点
    private parent(node:number){
        // 向下取整
        return Math.floor((node-1) / 2);
    }
    // 获得节点的左节点
    private left(node:number){
        return 2 * node + 1;
    }
    // 获得节点的右节点
    private right(node:number){
        return 2 * node + 2;
    }
    // 交换两个节点 
    private swap(i:number, j:number){
        [this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]]
    }
    // 上浮操作
    private swim(node:number){
        if(node == 0){
            return;
        }
        while(this.comp(this.heap[node], this.heap[this.parent(node)])){
            this.swap(node, this.parent(node));
            // 指针移动
            node = this.parent(node);
        }
    }
    // 下沉操作
    private sink(node:number){
        // 传入参数不对
        if(node < 0){
            return;
        }
        // 边界
        while(this.left(node) < this.size() || this.right(node) < this.size()){
            let min_nodex = node;
            // 检测左子树
            if(this.left(node) < this.size() && this.comp(this.heap[this.left(node)], this.heap[min_nodex])){
                min_nodex = this.left(node);
            }
            // 检测右子树
            if(this.right(node) < this.size() && this.comp(this.heap[this.right(node)], this.heap[min_nodex])){
                min_nodex = this.right(node);
            }

            if(min_nodex == node){
                break;
            }
            // 与符合值交换
            this.swap(min_nodex, node);
            // 指针移动
            node = min_nodex;
        }
        
    }
    


}

// 用法
let h = new PriorityQueue<number>((x,y)=>{return x>y});
h.push(10);
h.push(1);
h.push(2);
h.push(4);
h.push(5);
h.push(0);
h.push(2);
let s = h.size();
for (let i = 0; i < s; i++) {
    console.log(h.pop());
}

适应场景

优化A*寻路算法

在A*算法中，需要维护一个开放列表（open list），用于存储待处理的节点。二叉堆可以用来优化这个开放列表的管理。通过使用最小堆，可以快速地从开放列表中找到具有最低F值（即总成本最低的节点）的节点进行处理。

优先队列

比如说，可以通过设置优先级来判断加载的资源包，根据重要程度进行加载。亦或是UI弹窗等等，适用于需要设置优先级的功能。