Разница между стеком и кучей

2024 Автор: Mildred Bawerman | [email protected]. Последнее изменение: 2023-12-16 08:42

Стек против кучи

Стек - это упорядоченный список, в котором вставка и удаление элементов списка могут выполняться только на одном конце, называемом верхним. По этой причине стек считается структурой данных Last in First Out (LIFO). Куча - это особая структура данных, основанная на деревьях и удовлетворяющая специальному свойству, называемому свойством кучи. Кроме того, куча - это полное дерево, что означает, что между листьями дерева нет промежутков, то есть в полном дереве каждый уровень заполняется перед добавлением нового уровня к дереву, а узлы на данном уровне заполняются из слева направо.

Что такое стек?

Как упоминалось ранее, стек - это структура данных, в которой элементы добавляются и удаляются только с одного конца, называемого вершиной. Стеки позволяют выполнять только две основные операции, называемые push и pop. Операция push добавляет новый элемент на вершину стека. Операция pop удаляет элемент из вершины стека. Если стек уже заполнен, когда выполняется операция push, это считается переполнением стека. Если операция выталкивания выполняется для уже пустого стека, это считается опустошением стека. Из-за небольшого количества операций, которые могут быть выполнены со стеком, он считается ограниченной структурой данных. Кроме того, в соответствии со способом определения операций push и pop очевидно, что элементы, которые были добавлены в стек последними, выходят из стека первыми. Поэтому стек рассматривается как структура данных LIFO.

Что такое куча?

Как упоминалось ранее, куча - это полное дерево, удовлетворяющее свойству кучи. Свойство кучи утверждает, что если y является дочерним узлом x, то значение, хранимое в узле x, должно быть больше или равно значению, хранящемуся в узле y (то есть значение (x) ≥ value (y)). Это свойство подразумевает, что узел с наибольшим значением всегда будет располагаться в корне. Куча, созданная с использованием этого свойства, называется максимальной кучей. Есть еще один вариант свойства heap, который утверждает обратное. (т.е. значение (x) ≤ значение (y)). Это означает, что узел с наименьшим значением всегда будет помещен в корень, что называется минимальной кучей. Существует широкий спектр операций, выполняемых с кучами, таких как поиск минимума (в минимальных кучах) или максимума (в максимальных кучах), удаление минимума (в минимальных кучах) или максимума (в максимальных кучах),увеличение (в максимальных кучах) или уменьшение (в минимальных кучах) ключа и т. д.

В чем разница между стеком и кучей?

Основное различие между стеками и кучей заключается в том, что, хотя стек - это линейная структура данных, куча - это нелинейная структура данных. Стек - это упорядоченный список, который следует за свойством LIFO, а куча - это полное дерево, следующее за свойством кучи. Кроме того, стек - это ограниченная структура данных, которая поддерживает только ограниченное количество операций, таких как push и pop, в то время как куча поддерживает широкий спектр операций, таких как поиск и удаление минимума или максимума, увеличение или уменьшение ключа и слияние.