Стек против кучи
Стек - это упорядоченный список, в котором вставка и удаление элементов списка может выполняться только на одном конце, называемом вершиной. По этой причине стек считается структурой данных «последним пришел - первым вышел» (LIFO). Куча - это специальная структура данных, основанная на деревьях и удовлетворяющая специальному свойству, называемому свойством кучи. Кроме того, куча является полным деревом, что означает, что между листьями дерева нет промежутков, т.е. в полном дереве каждый уровень заполняется перед добавлением нового уровня в дерево, а узлы на данном уровне заполняются из слева направо.
Что такое стек?
Как упоминалось ранее, стек - это структура данных, в которой элементы добавляются и удаляются только с одного конца, называемого вершиной. Стеки допускают только две основные операции, называемые push и pop. Операция push добавляет новый элемент на вершину стека. Операция pop удаляет элемент из вершины стека. Если стек уже заполнен, при выполнении операции push это считается переполнением стека. Если операция извлечения выполняется с уже пустым стеком, это считается потерей значимости стека. Из-за небольшого количества операций, которые могут быть выполнены со стеком, он считается ограниченной структурой данных. Кроме того, согласно тому, как определены операции push и pop, становится ясно, что элементы, которые были добавлены в стек последними, уходят из стека первыми. Поэтому стек считается структурой данных LIFO.
Что такое куча?
Как упоминалось ранее, куча - это полное дерево, удовлетворяющее свойству кучи. Свойство кучи указывает, что если y является дочерним узлом x, то значение, хранящееся в узле x, должно быть больше или равно значению, хранящемуся в узле y (т. е. значение (x) ≥ значение (y)). Это свойство подразумевает, что узел с наибольшим значением всегда будет находиться в корне. Куча, построенная с использованием этого свойства, называется максимальной кучей. Существует еще один вариант свойства кучи, в котором утверждается обратное. (т. е. значение (x) ≤ значение (y)). Это означает, что узел с наименьшим значением всегда будет помещаться в корень, что называется минимальной кучей. Существует широкий спектр операций, выполняемых над кучами, таких как нахождение минимума (в мини-кучах) или максимума (в макс-кучах), удаление минимума (в мини-кучах) или максимума (в макс-кучах), увеличение (в макс. -кучи) или убывающий (в мин-кучах) ключ и т.д.
В чем разница между стеком и кучей?
Основное различие между стеками и кучами заключается в том, что стек - это линейная структура данных, а куча - нелинейная структура данных. Стек - это упорядоченный список, который соответствует свойству LIFO, а куча - это полное дерево, которое следует свойству кучи. Кроме того, стек - это ограниченная структура данных, которая поддерживает только ограниченное количество операций, таких как push и pop, в то время как куча поддерживает широкий спектр операций, таких как поиск и удаление минимума или максимума, увеличение или уменьшение ключа и слияние.
