[РЕДАКТИРОВАНИЕ !!!] Читая о различных структурах данных и создавая многие из них (в C ++), я просто удивляюсь, как мы можем создать структуру данных, где каждый узел будет парой ключей (x, y), где x будет ссылаться на значение Max Куча и у ключ бинарного дерева поиска. Я бы хотел что-то вроде BST и Max Heap одновременно (используя кортежи или пары ключей в качестве узлов каждый раз). Чтобы сделать это более понятным, технически я имею в виду, что в каждом узле i дерева будет храниться пара ключей (x, y), где x является приоритетом ключа, а y будет значением ключа.
Он сможет поддерживать все функции вышеупомянутых структур данных, такие как вставка и удаление. Например, в отношении удаления, кортеж будет идти последовательно глубже с помощью последовательности простых последовательных вращений, пока кортеж не станет листом. Тогда удаление легко, насколько вы знаете. Если кортеж — тот, который мы хотели бы удалить — был бы листом или внутренним узлом, удаление могло бы быть сделано так же, как в BST.
Что касается вставки, кортеж будет вставлен в дерево только на основе ключа двоичного дерева поиска. После этого пара будет последовательно перемещаться выше в дереве, пока не будет нарушено фундаментальное свойство максимальных куч.
Кроме того, у меня есть некоторые дополнительные функции в моем разуме. Дополнительной функцией может быть что-то вроде find_second_next (), принимающей в качестве аргумента ключ x, который уже находится в дереве, и эта функция найдет второй меньший среди всех ключей y дерева, которые больше x.
Другой функцией может быть также print_between (k1, k2). Эта функция будет печатать все клавиши y дерева, имеющие значение в диапазоне [k1, k2]. Наконец, я хотел бы также иметь функцию print_with_higher_priority (x), которая будет печатать все x-клавиши дерева, которые больше x.
Если у вас есть дополнительные функции, напишите их! : D
Я с нетерпением жду вашего вклада в этот вопрос!
Задача ещё не решена.
Других решений пока нет …