hello-algo/ru/docs/chapter_heap/summary.md

Резюме

Ключевые моменты

• Куча -- это полное двоичное дерево, которое в зависимости от условий делится на максимальную и минимальную кучу. Элемент на вершине максимальной (минимальной) кучи является наибольшим (наименьшим).
• Приоритетная очередь определяется как очередь с приоритетом извлечения элементов и обычно реализуется с помощью кучи.
• Основные операции с кучей и их временная сложность включают: вставка элемента в кучу O(\log n), извлечение элемента с вершины кучи O(\log n) и доступ к элементу на вершине кучи O(1) и т. д.
• Полное двоичное дерево очень удобно представлять в виде массива, поэтому для хранения кучи обычно используется массив.
• Операция упорядочивания кучи используется для поддержания свойств кучи и применяется как при вставке, так и при извлечении элементов.
• Временная сложность построения кучи из n элементов может быть оптимизирована до O(n), что очень эффективно.
• Top-k -- это классическая алгоритмическая задача, которая может быть эффективно решена с помощью структуры данных кучи с временной сложностью O(n \log k).

Вопросы и ответы

В: Являются ли «куча» в структурах данных и «куча» в управлении памятью одним и тем же понятием?

Это не одно и то же понятие, просто они случайно называются одинаково -- «куча». Куча в памяти компьютерной системы является частью динамического распределения памяти, которую программа может использовать для хранения данных во время выполнения. Программа может запросить определенный объем памяти кучи для хранения сложных структур, таких как объекты и массивы. Когда эти данные больше не нужны, программа должна освободить эту память, чтобы предотвратить утечки памяти. По сравнению с памятью стека, управление и использование памяти кучи требует большей осторожности, неправильное использование может привести к утечкам памяти и висячим указателям.