二叉树------最小堆，最大堆。

什么是最小堆：

        堆是一种二叉树，最小堆中所有父亲节点的值都要比自己的子节点的值要小。而根节点称为堆顶。根据定义我们可以得到堆中最小元素就在堆顶。（节点左上角是编号，内部是元素值）

        

---

         假设该图中的堆顶元素是24呢？显然不符合最小堆的定义，那么我们要怎么处理呢？

        假设7号节点的值是1呢？显然不符合最小堆的定义，那么我们要怎么处理呢？

如何调整堆：

        

        在该图中我们先让 24 与左孩子的值比较发现 左孩子比自己小，再看右孩子，发现右孩子比左孩子还小，于是1号节点值和3号节点值交换。然后再看3号节点的左孩子和右孩子值都比 24 小，但是6号节点值更小，所以3号节点值24和6号节点值交换，完成最小堆的向下调整。

        

        该图我们先让7号节点与3号节点比较，发现5 比 1大 然后交换两个节点的值，3号节点再和1号节点比较发现2比1大，然后交换节点的值，完成了最小堆的向上调整。

        如果忘记了怎么存储二叉树，参考这篇博文：树------二叉树-CSDN博客

具体代码：

void down(int i)//i为需要调整的节点编号。
{
    int t, flag = 0;

    while (2 * i <= n && flag == 0)//判断当前节点是否有左子树。
    {
        if (arr[i] > arr[2 * i])
            t = 2 * i;
        else
            t = i;//如果左子树比本节点小，记录该节点下标，否则记录该节点下标。
        if (2 * i + 1 <= n)//如果有右子树。
            if (arr[2 * i + 1] < arr[t])
                t = 2 * i + 1;//确定最终交换值的节点下标。

        if (t != i)
        {
            swap(i, t);
            i = t;
        }//如果最终交换值的下标不等于本节点，证明需要交换值。
        else
            flag = 1;//如果没有交换，证明本节点调整完毕，退出循环。
    }
}

void up(int i)//向上调整函数。
{
    int flag = 0;

    if (i == 1)//如果已经在堆顶，不需要调整。
        return;

    while (i != 1 && flag == 0)
    {
        if (arr[i] < arr[i / 2])
            swap(i, i / 2);//如果本节点小于父亲节点，交换值，负责退出循环。
        else
            flag = 1;

        i /= 2;//节点编号调整为父亲节点。
    }
}

void swap(int i, int j)
{
    int k = arr[i];
    arr[i] = arr[j];
    arr[j] = k;
}//交换函数。

注意点：

        最大堆和最小堆差不多，最大堆定义是任何父亲节点都要比子节点要大，至于如何调整，可以改变以上代码的大小判断符号。

        另外关于昨天的 Bellman-Ford算法的优化的答案博文因为某些原因今天无法更新（其实是我忘记写了。。。。。。），明天再为大家呈上。该算法博文链接如下。

        图论------贝尔曼-福德（Bellman-Ford）算法-CSDN博客