如果需要按照第k次插入为序对节点进行修改、删除操作,就需要对堆的每个节点插入顺序与其对应下标进行记录。这里我们用ph[N]数组来记录这种对应关系。
ph[k]为第k次插入元素的下标。当我们在up()操作和down()操作中需要对两个节点进行交换时,我们首先就需要交换这两个节点的ph[N]里对应的值,从而实现在维护堆中值的同时对插入顺序与下标的关系一并维护。
那为什么我们还需要多一个hp[N]呢?
hp[N]可以理解成ph[N]的一个反映射,即hp[k]是下标为k的节点元素的插入顺序。因为我们在对两个节点进行交换的时候,我们只知道这两个节点的下标,那么我们要交换两个节点的ph[N],就需要知道这两个节点的插入顺序。所以我们在这里也要有一个数组来储存下标与插入顺序之间的映射,并且在交换的时候一并维护。