部分重新排序的高效算法

Question

考虑以下对象数组：

[
{v: 'a'},
{v: 'b'},
{v: 'c', ptr: 'b'},
{v: 'd', ptr: 'a'},
{v: 'e'},
]

某些对象包含

ptr

属性，引用其应直接位于其前面的对象的

v

属性值。两个对象永远不会尝试直接位于同一个对象之前，并且数组中永远不会出现循环（例如 a->b->c->a）。

因此，这里有两种可能的有效的对象重新排列：

[
{v: 'e'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'c', ptr: 'b'},
{v: 'b'},
]

[
{v: 'c', ptr: 'b'},
{v: 'b'},
{v: 'd', ptr: 'a'},
{v: 'a'},
{v: 'e'}
]

如果没有

ptr

属性引用对象，则对象出现在输出中的位置并不重要。重要的是，根据

ptr

属性的要求，某些对象直接位于其他对象之前。

执行这种重新排列的相当有效的算法是什么？

虽然保证数据不包含循环，但重新排列时应小心，不要陷入无限循环，从而永远重新排列对象。

请注意，虽然这些示例使用字符串表示

v

和

ptr

，但实际应用程序将涉及 DOM 元素作为

v

和

ptr

引用的值。因此，解决方案应该只能比较

v

和

ptr

属性是否相等。

Answer 1

找出哪些对象有另一个对象指向它们。然后，对于每个没有有另一个对象指向它的对象，将该对象以及以下 ptr 链中的所有内容添加到输出中：

let val_to_obj = new Map();
let has_predecessor = new Set();
for (let obj of arr) {
    val_to_obj.set(obj.v, obj);
    if ('ptr' in obj) {
        has_predecessor.add(obj.ptr);
    }
}
let res = [];
for (let obj of arr) {
    if (has_predecessor.has(obj.v)) {
        continue;
    }
    while (obj !== undefined) {
        res.push(obj);
        obj = val_to_obj.get(obj.ptr);
    }
}