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

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

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

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

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

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

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

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

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