Построение кучи:
На основе имеющегося массива элементов создать полное двоичное дерево
Вызвать метод heapify (привести к виду, удовлетворяющему основному условию кучи – родитель всегда больше потомка)
Сложность такого построения
Добавление элемента в кучу:
Вставить новый элемент в конец кучи
Вызвать метод heapify (привести к виду, удовлетворяющему основному условию кучи – родитель всегда больше потомка)
Удаление элемента из кучи:
Поменять выбранный элемент с последним
Удалить последний элемент
Вызвать метод heapify (привести к виду, удовлетворяющему основному условию кучи – родитель всегда больше потомка)
Сортировка с помощью двоичной кучи:
Можно отсортировать массив, сначала построив из него двоичную кучу, а потом последовательно извлекая максимальные элементы. Оценим временную сложность такого элемента: построение кучи – , извлечение элементов – . Следовательно, итоговая оценка . При этом дополнительная память для массива не используется.
Кучи используют для сортировки объектов или реализации очередей с приоритетом, а также алгоритма Дейкстры.
Структура данных: граф (способы представления, основные алгоритмы на графах: обход графа в глубину и в ширину, поиск элемента в графе, применение).
Структура данных графа представляет собой набор узлов, которые имеют данные и связаны с другими узлами.
С точки зрения компьютерных наук и дискретной математики, графы — это абстрактный способ представления типов отношений, например дорог, соединяющих города, и других видов сетей.
Точнее, граф — это структура данных , которая состоит из:
Коллекции вершин .
Набора ребер , представленного в виде упорядоченных пар вершин .
Достарыңызбен бөлісу: |
