堆

堆

描述：

​ 堆有两个操作：down和up

模板：

void down(int u)    //down操作，将每个节点与其左右儿子比较，判断其是否需要进行下移
{
    int t = u;  //t记录的是该节点以及其左右两个儿子中最小的值
    while (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;  //先与左儿子进行比较
    while (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;  //再与右儿子进行比较
    if (t != u) //若不等于，说明t发生了变化，必须进行下移
    {
        swap(h[t], h[u]);   //将t位置的值，与u位置的值进行交换位置
        down(t); //递归，直至其不再需要下移为止
    }
}

void up (int u) //up操作， 判断一个节点是否需要根据小根堆的特性进行上移操作
{
    while (u / 2 && h[u] < h[u / 2])    //判断，只要存在父节点，且父节点的值大于该节点的值，则需要进行交换
    {   
        swap(u, u / 2); //同样进行所有信息的交换
        u >>= 1;        //交换后，将该节点往上移，while继续判断是否需要上移
    }
}