Есть ли эффективный способ сортировки массива объектов с родительскими / дочерними отношениями?

Question

Я пытаюсь найти эффективный способ сортировки массива, где каждый объект может указывать на индекс «родительского» объекта в том же массиве.
Каждый объект может не иметь ни одного родителя (индекс -1) или одного родителя, так что это только отношение многие-к-одному.
Вы можете объединить любое количество объектов вместе, создав глубокие иерархии.
Однако все они находятся в одном непрерывном массиве и добавляются вв произвольном порядке.

Вот пример того, как выглядит объект:

struct Object
{
    void* data;

    int ParentIndex; //Will either be '-1' or will be an index in 'objects' where the parent of this object is.
};

std::vector<Object> objects;

Казалось бы, единственный способ сделать это с отношением многие-к-одному - это использоватьглубокая рекурсия для каждого родителя.
Это, однако, имеет крайне плохую производительность.
Существует ли алгоритм, который может справиться с такой проблемой?

Answer 1

Есть некоторые проблемы, которые вы должны рассмотреть:

• теоретически, он может содержать рекурсивную цепочку.2 или более объектов являются родительскими.
• при сортировке и перемещении родительского объекта он должен обновить все свои дочерние элементы.

Поэтому я считаю единственным эффективным способомэто перевести его в граф (многодетное дерево) с указателями вместо индексов.

struct Object2
{
    void* data;
    Object2* FirstChild; // Will point to first child (if there is), or null.
    Object2* NextSibling;// Will point to next sibling (if there is), or null.
};

На самом деле, вы можете использовать любую библиотеку XML для сортировки:

• Любой дочерний элементпросто необходимо добавить к родительскому элементу.
• По завершении вы читаете элементы из XML и переупорядочиваете новые индексы.