题目描述

在这一章节中，我们经常看到y总在实现各种数据结构中经常用到idx这个变量，这个变量到底有什么用呢？
为什么链表，Trie树和堆会用到idx来维护这个数据结构，而栈和队列就不用idx来维护，而是用hh和tt来维护呢？

解答

可以看出不管是链表，Trie树还是堆，他们的基本单元都是一个个结点连接构成的，可以成为“链”式结构。这个结点包含两个基本的属性：本身的值和指向下一个结点的指针。按道理，应该按照结构体的方式来实现这些数据结构的，但是做算法题一般用数组模拟，主要是因为比较快。

那就有个问题，原来这两个属性都是以结构体的方式联系在一起的，现在如果用数组模拟，如何才能把这两个属性联系起来呢，如何区分各个结点呢？

这就需要用到idx这个东东啦！

从y总给出的代码可以看出，idx的操作总是idx++，这就保证了不同的idx值对应不同的结点。因此可以利用idx把结构体内两个属性联系在一起了。因此，idx可以理解为结点。

链表：
链表中会使用到这几个数组来模拟：

h, e[N], ne[N], idx;

h表示头结点指针，一开始初始化指向-1，每次插入x的操作idx++。利用idx联系结构体本身的值和next指针，因此e[idx]可以作为结点的值，ne[idx]可以作为next指针。同理可以理解双链表。

//单链表
void add_to_head (int x)
{
    e[idx] =  x;
    ne[idx] = h;
    h = idx ++ ;
}
//双链表
void insert(int a,  int x)
{
    e[idx] = x;

    l[idx] = a;
    r[idx] = r[a];

    l[r[a]] = idx;
    r[a] = idx ++;
}

Trie树
Trie树中有个二维数组son[N][26]，表示当前结点的儿子，如果没有的话，可以等于++idx。Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。所以这个数组包含了两条信息。比如：son[1][0]=2表示1结点的一个值为a的子结点为结点2。如果son[1][0] = 0，则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。

void insert(char str[])
{
    int p = 0; //从根结点开始遍历
    for (int i = 0; str[i]; i ++ )
    {
        int u =str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx; //没有该子结点就创建一个
        p = son[p][u]; //走到p的子结点
    }

    cnt[p] ++;
}

堆
堆中的每次插入都是在堆尾，但是堆中经常有up和down操作。所以结点与结点的关系并不是用一个ne[idx][2]可以很好地维护的。但是好在堆是个完全二叉树。子父节点的关系可以通过下标来联系（左儿子2n，右儿子2n+1）。就数组模拟来说知道数组的下标就知道结点在堆中的位置。所以核心就在于即使有down和up操作也能维护堆数组的下标（k）和结点（idx）的映射关系。比如说：h[k] = x, h数组存的是结点的值，按理来说应该h[idx]来存，但是结点位置总是在变的，因此维护k和idx的映射关系就好啦，比如说用ph数组来表示ph[idx] = k, 那么结点值为h[ph[idx]], 儿子为ph[idx] * 2和ph[idx] * 2 + 1, 这样值和儿子结点不就可以通过idx联系在一起了吗？

详细请见 https://www.acwing.com/solution/AcWing/content/5661/

if (op == "I")
{
    scanf("%d", &x);
    size ++ ;
    idx ++ ;
    ph[idx] = size, hp[size] = idx;//每次插入都是在堆尾插入
    h[size] = x;//h[k], k是堆数组的下标，h存储的是结点的值，也就是链表中的e[idx]
    up(size);
}

由于idx只有在插入的时候才会更新为idx ++，自然idx也表示第idx插入的元素