Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/8: Рейтинг темы: голосов - 8, средняя оценка - 4.50
comcor2013
0 / 0 / 0
Регистрация: 19.08.2013
Сообщений: 149
1

Алгоритм слияния двух двоичных (бинарных) куч

11.01.2015, 23:13. Просмотров 1546. Ответов 1
Метки нет (Все метки)

Товарищи, можете объяснить мне как будет выглядеть этот алгоритм на языке программирования? Всё перерыл, но не нашел(
0
QA
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.01.2015, 23:13
Ответы с готовыми решениями:

Динамика слияния двух капель
Здравствуйте Есть шарики которые могут сливаться, этот эффект/техника известны давно, см...

Алгоритм слияния двух строк
Здравствуйте. Прошу подсказать алгоритм слияния двух строк. Первая строка - исходная, втроая - ее...

Разложить камни в 2 кучи так, что разность весов двух куч была минимальной
Разложить камни в 2 кучи так, что разность весов двух куч была минимальной. Вот мой вариант,...

Распределить камни в две кучи так, чтобы разность весов этих двух куч была минимальной
Ограничение времени: 1.0 секунды Ограничение памяти: 64 МБ У вас есть несколько камней...

Распределить камни в две кучи так, чтобы модуль разности весов этих двух куч был минимальным
Доброго времени суток! Требуется программу, которая распределит камни в две кучи так, чтобы модуль...

1
RaiaNKnight
97 / 71 / 12
Регистрация: 29.06.2011
Сообщений: 465
Записей в блоге: 1
17.01.2015, 22:52 2
Очень просто, нарисуйте на бумажке 2 кучи. Потом поразмышляйте, "а если бы второй кучи не было и я хотел бы добавить новые элементы в первую кучу, то чтобы я сделал"? Вероятно, просто начали бы добавлять элементы в первую кучу.

Теперь, у вас есть 2 кучи. Вы хотите их слить в одну. Вероятно, вы посчитаете неплохой идеей (для начала) начать вытаскивать элементы из одной кучи и добавлять их в другую.

Пусть размер 1-й кучи равен n1, а второй - n2. Тогда слияние двух куч отработает за O(n2 * log(n1)). Можно ли сделать эту операцию оптимальнее, скажем добиться линейной верхней оценки? Ответ: можно.

Заметим следующее: операция построения кучи выполняется за линейное от n время над массивом из n элементов. Почему бы нам не скопировать все элементы из второй кучи в конец первой кучи, и запустив алгоритм построения кучи? Здесь мы и получаем верхнюю оценку O(n).

Есть ещё более хитрые алгоритмы соединения двух куч, которые работают за O(log(n1) * log(n2)), но тогда только лишь посоветую вам читать статьи на эту тему.
Вот пара ссылок:
http://link.springer.com/article/10.1007%2FBF00264229
http://stackoverflow.com/questions/1...-two-max-heaps
1
Answers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
17.01.2015, 22:52

Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной
Здравствуйте! Пытаюсь решить задачу http://acm.timus.ru/problem.aspx?space=1&num=1005 мне нужно...

Алгоритм многопутевого слияния
Задание: Отсортировать текстовый файл,содержащий целые числа,в порядке убывания методом...

Алгоритм сортировки методом слияния
Напишите программу, реализующую алгоритм сортировки методом слияния и получите для нее эмпирические...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.