throughtheether

Я бы на вашем месте использовал префиксные деревья. Суммаризацию (вам же необходимо минимальное количество префиксов, или, как вы их называете, "масок"), скорее всего, придется писать самостоятельно.

Вы можете новые записи создавать? Если да, попробуйте провести атаку типа chosen plaintext, создайте записи с полями вида 'а', 'аа', 'ааа', затем 'б', 'бб', 'ббб'. Может быть, что-то прояснится (или нет).

Спасибо, что "призвали", помогу чем смогу.

узлы-братья удалены друг от друга на динамически задаваемое значение (в данном случаи 20), так же как и узлы-соседи (в данном случаи 40)

Давайте с терминологией определимся, под соседями подразумеваются узлы на одном уровне дерева, не имеющие общего непосредственного родителя (не братья)?

Ваш алгоритм, к сожалению, до конца не понял, при наличии времени попробую повторить попозже. Но идея двигать отдельные ноды "вручную" мне не импонирует.

Если есть какие-то идеи я буду рад выслушать

Идея такая. Дерево, как правило, имеет на нижних уровнях больше узлов, чем на верхних. Больше узлов - меньше свободы в плане сколь-нибудь равномерного их размещения. Так и начинайте снизу. Из готовых алгоритмов навскидку могу только вспомнить Tidier drawing of trees (за авторством Reingold, Tilford), вполне возможно, что удастся его адаптировать под ваши требования.

Дайте совет, когда и как стоит приступать к этим вкусняшкам?

Когда у вас появятся релевантные задачи. Например, как вам уже рекомендовали, "олимпиадные". (рекомендую codeeval и codewars). Вы можете сначала решить задачу каким-либо "наивным" способом, затем поискать (спросить) подходящую структуру данных, сравнить производительность подходов. На мой взгляд, привязка к какой-никакой практике позволяет знаниям лучше усваиваться.

Еще могу порекомендовать курс (там две части) на coursera от Stanford за авторством Tim Roughgarden. Очень доступно объясняет.

После выполнения алгоритма, мы получим, что кратчайшее расстояние до второй вершины равно 10.

Вот здесь непонятно, поясните вашу мысль.

Изначально (стартуем из вершины 1) у вас вершина 1 имеет ассоциированное число (длину пути, d[1]) 0, она же находится во множестве посещенных вершин. Длина пути до других вершин - бесконечность.
Для всех ребер, соединяющих множества посещенных и непосещенных вершин (т.е. для ребер 1-2 и 1-3) рассмотрим суммы d[u]+w(u,v), где d[u]-длина кратчайшего пути до вершины u, w(u,v) - вес (длина) соответствующего ребра. Минимальная сумма наблюдается для ребра 1-3, соответствующего пути 1,3. Добавляем 3 в посещенные.
Снова, для всех ребер, соединяющих множества посещенных и непосещенных вершин (т.е. для ребер 1-2, 3-2) рассматриваем соответствующие суммы (10 и 2), выбираем минимальную, т.е. добавляем вершину 2 в путь (и во множество посещенных вершин), имеющий вид 1,3,2. Так как непосещенных вершин не осталось, завершаем работу алгоритма.

Написал пятнашки, крестики нолики в консоли с применением мега мелькающей дефолтной графики по средствам раскрашивания askii.

Может подскажите что можно написать ради себя, ради души и практики,

Напишите игру/демку, кторая рендерится в ascii-символы, вот пример.

if (command == com_extract) {
			cout << bh.heapSort() << endl;
		}

Вам надо извлечь корневое значение, восстановить свойство кучи и вернуть предварительно извлеченное значение. Мне не вполне ясно, что вы делаете:

int heapSort()
	{

		for (int i = heap_data.size() - 1; i >= 0; i--)
		{

			heapify(0);
			return extract();
		}
	}

Почему, например, return в цикле?
Если я правильно понял, то вам надо строку cout << bh.heapSort() << endl; заменить на cout << bh.extract() << endl;

Каким будет время работы построения кучи, если просто последовательно добавить в кучу все n элементов?

Мне нужно выбрать все верные варианты из следующих
O(n)
Ω(n2)
Ω(n)
O(n2)
Ω(nlogn)
O(nlogn)

Если мы последовательно добавляем элементы (всего их n) в кучу (бинарную кучу) и каждый раз восстанавливаем свойство кучи (верхняя оценка сложности O(logn), нижняя оценка Ω(1)), то верхняя оценка общей сложности будет O(nlogn), нижняя - Ω(n). Правильные варианты, на мой взгляд:
Ω(n), O(n2) (если имеется в виду O(n*n)),O(nlogn)

Мое авторитетное мнение дилетанта таково.
Во-первых, имеет смысл ознакомиться с первоисточником по данной теме, а именно со статьей Дональда Кнута. В ней на стр.19 дается удобное, на взгляд автора, определение отношений Θ,O,Ω. Эти отношения первоначально задаются как отношения значений неких двух функций. Оценка временной и пространственной сложности - это приложения. Целью введения такой нотации было упростить вычисление количества операций, требуемых для выполнения алгоритма, без потери качественных характеристик, а также отвязаться от возможных зависимостей от архитектуры, компилятора и т.д. Грубо говоря, если алгоритм обсчитывает 1000 единиц входных данных час, то эта нотация помогает быстро оценить, как долго будут обсчитываться, например, 2000 единиц. Естественно, что эта нотация "огрубляет" информацию о значениях функции, в этом ее предназначение.

Что такое «асимптотически точная оценка времени работы алгоритма»?

Если речь идет о Θ-нотации, то это функция (или множество функций), растущая так же быстро, как и время работы алгоритма с увеличением длины входных данных.

Оценка Θ() существует только тогда, когда O() и Ω() совпадают и равна им.

Это положение мне представляется частично верным. Если f(n)=O(g(n)) и f(n)=Ω(g(n)), то f(n)=Θ(g(n)), где g(n) - некая функция, например, вида nlogn. Другое дело, что если f(n)=O(n), то также верно, что f(n)=O(n^2), то есть, несмотря на то, что у функции есть Θ-оценка, ее O- и Ω-оценки могут не совпадать.

Итак, O() - асимптотическая оценка алгоритма на худших входных данных, Ω() - на лучших входных данных

Если определить "лучшие"/"худшие" данные как требующие минимального/максимального времени среди наборов входных данных такой же длины, то это утверждения мне также представляется частично корректным. Количество операций, которое выполняет алгоритм в худшем, среднем и лучшем случаях - это функции от длины входных данных. Каждую из этих функций можно оценить при помощи каждой из трех (Ω,Θ,O) нотаций.

Мне представляется разумным такое восприятие оценок:
f(n)=O(g(n)) - функция f(n) растет не быстрее функции g(n)
f(n)=Ω(g(n)) - функция f(n) растет не медленнее функции g(n)
f(n)=Θ(g(n)) - функция f(n) растет так же быстро, как и функция g(n)
Попробуйте нарисовать график некоей возрастающей функции в логарифмическом масштабе по оси ординат, и представить, где расположены значения функций, корректно оценивающих исходную при помощи Ω,O,Θ нотаций, пользуясь определениями из статьи Кнута и отметив на графике константы C и n0.

Известно, что например для сортировки qsort средняя оценка для случайного распределения входных данных (она же лучшая, для полностью сбаллансированного варианта) равна Θ(nlogn),

С моей точки зрения, корректно также будет сказать, что средняя оценка также равна O(nlogn) или Ω(n).

тогда как верхняя оценка (для специально подобранных неоптимальных данных) равна O(n^2).

а также равна Θ(n^2).

Правильно ли будет сказать, что реально асимптотически точная оценка алгоритма дается в первую очередь на основании особенностей работы конкретного алгоритма для усредненных входных данных (понимая под усредненными данными случайно распределенный массив данных), а в сложных случаях - отталкиваясь от оценок сверху O() и снизу Ω()?

С моей точки зрения, если есть совпадающие оценки O и Ω, элементарно получается Θ-оценка. Другое дело, что "худшая", "лучшая", "средняя" вычислительные сложности - это функции от длины входных данных. Для каждой из этих функций может быть дана оценка асимптотической скорости возрастания, будь то Ω, Θ или O. Рассуждая о "случайно распределенном массиве данных", можно углубиться в матстатистику, что, на мой взгляд, не упростит задачу.

Пользуясь случаем, рекомендую курс на coursera от Tim Roughgarden. Релевантные видео есть на youtube.