Сортировка кучей (пирамидальная сортировка, heap sort)

27.11.19

Разработка - Математика и алгоритмы

Алгоритм сортировки массива кучей (пирамидальная сортировка).

Скачать файлы

Наименование Файл Версия Размер
Сортировка кучей c визуализацией
.epf 9,32Kb
5
.epf 9,32Kb 5 Скачать

Это классический алгоритм сортировки который, пожалуй, должен знать любой программист. В основу данной сортировки заложен принцип построения "Кучи". Куча - это структура данных, которая удовлетворяет следующему свойству: значения потомков всегда меньше, его родителя. У одного родителя не может быть больше двух потомков. Таким образом, мы всегда имеем максимальное значение из всего подмножества в вершине кучи.

Алгоритм сортировки состоит из следующих шагов:

1. Построение кучи.

Кучу всегда можно легко построить используя массив: 

Вершина кучи это всегда первый элемент массива.

Левый потомок идентифицируется по индексу 2*i + 1.

Правый потомок идентифицируется по индексу 2*i + 2.

2. Меняем местами первый и последний элемент.

3. Восстанавливаем кучу (операция просеивания) для N-1 элементов.

Временная сложность алгоритма O(N*log N).

На практике может применяться для нахождения k-го максимального элемента (для этого не требуется полная сортировка массива).  

Обработка протестирована на версии платформы 1С:Предприятие 8.3 (8.3.12.1616).

heap куча пирамида сортировка нахождение элемента

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1757    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4432    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7472    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7857    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4451    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8846    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7814    dusha0020    8    

70
Оставьте свое сообщение