Сортировка кучи Получить родителя

Question

Чтобы получить родителя узла в массиве сортировки кучи, вычисление должно быть (index - 1) / 2.

Однако предположим, что каждый узел занимает 4 пробела в массиве.Чтобы получить доступ к записи / узлу, я должен получить доступ к первой позиции четырех из этой записи.Итак, вот пример:

Если родитель начинается с позиции 4, левый ребенок начинается с позиции 12, а правый ребенок начинается с позиции 16. Уравнение для получения левого ребенка будет 2*position + 4, а уравнениеполучить правильного ребенка было бы 2*position + 8.

Каково было бы уравнение, чтобы получить родителя, хотя?Мне нужно одно уравнение, чтобы получить родителя для левого или правого ребенка, точно так же, как index-1/2.Это будет возможно?Если мне понадобятся два отдельных уравнения, это не сработает, поскольку я не знаю, является ли запись левым или правым потомком.

Спасибо,

Answer 1

Посмотрите на следующее C # Мин. Куча .

    public int GetParent(int i, out int index)
    {
        double element = i;
        index = (int)Math.Floor((element - 1)  / 2);

        if(index < 0)
        {
            return 0;
        }

        return _collection[index];
    }

Это работает для обычной кучи, в том числе

вы можете увидеть остальные MinHeapреализация здесь.

Обычно структура кучи поддерживается массивом, и, что интересно, куча хочет начать с массива 1 , чтобы упростить вычисление родительских и дочерних элементов.

если вы хотите изменить дочерний, родительский, как вы упомянули в своей задаче, вам следует подумать об обёртывании 4-х узлов в узле, но сохранить, как работает куча, как есть

Answer 2

Вы должны оставить первый индекс (или, в данном случае, первые четыре индекса) пустым;это упрощает расчеты.Таким образом, корень должен быть в 4-7, дети корня в 8-11 и 12-15, и так далее.Учитывая это, родительский узел находится на index / 8 * 4.Если вы хотите, чтобы корень был в 0-3, вы можете использовать (index + 4) / 8 * 4 - 4.

(Тем не менее, вы должны рассмотреть обертывание четырех связанных элементов в классе, чтобы с ними было легче работатьи вы можете обрабатывать один элемент массива за раз.)