Кучи против стопок: что их отличает?
Как программист, вы, скорее всего, встречали термины «куча» и «стек». Новички часто используют эти два термина взаимозаменяемо и неправильно.
Хотя студенты курса «Структуры данных» и опытные программисты легко различают эти две структуры данных, другим они могут показаться одинаковыми.
Программистам необходимо различать эти два понятия и надлежащим образом использовать их в практических ситуациях программирования. Интервьюеры часто стремятся дать кандидатам сценарий, а затем запросить наиболее подходящую структуру данных.
Читайте дальше, пока мы подробно рассмотрим кучи, стеки, их различия и соответствующие приложения.
Что такое куча?
Куча для программистов обычно представляет собой специальную древовидную структуру данных, часто называемую «приоритетной очередью». Кучи, которые представляют собой полностью сбалансированную структуру двоичного дерева (напомним, что все уровни полного двоичного дерева заполнены, кроме последнего уровня) и следующие за свойством кучи, называются двоичными кучами.
Свойство кучи структурирует дерево таким образом, чтобы в корне размещалось максимальное или минимальное значение.
В Max Heap значение родительских узлов больше, чем дочерних узлов, а корень дерева содержит максимальное значение. В качестве альтернативы структура Min Heap имеет минимальное значение в качестве корневого, а каждый дочерний узел имеет большее значение, чем его родительский узел. Свойство кучи должно быть рекурсивно истинным для каждого узла в двоичном дереве.
Кучи обычно реализуются с помощью линейных массивов, причем первый элемент массива ( Arr [0] ) представляет корень. Для конкретного узла i вы можете получить дочерние узлы в Arr [(2 * i) + 1] и Arr [(2 * i) + 2] , аналогично родительский узел расположен в Arr [(i-1) / 2] index. Большинство языков, таких как Java и C ++, содержат библиотеки, которые предоставляют пользователям готовые к использованию минимальную и максимальную кучу.
Что такое стек?
Стеки – одна из первых структур данных, которым учат студентов, и их нельзя упускать из виду. Стек – это структура данных, которая ведет себя как любая реальная стопка (карты, тарелки и т. Д.). Стеки допускают операции только на одном конце, и в результате они имеют характеристику LIFO (Last-In-First-Out). Напротив, очереди имеют характеристику FIFO (First-In-First-Out) и позволяют выполнять операции на обоих концах.
Типичные операции со стеком состоят из push (вставка данных в верхнюю часть стека) и pop (удаление самого верхнего элемента данных). Вы можете реализовать стеки через указатели, массивы или даже связанные списки, в зависимости от ваших требований. C ++, C # и Java содержат библиотеки, в которых уже реализован стек, поэтому вы можете использовать их в любое время.
Кучи против стеков
Если вы дочитали до этого места, то имеете довольно хорошее представление о различиях между стеком и кучей. Стеки являются линейными и имеют характеристику LIFO, тогда как кучи имеют древовидную структуру и следуют свойству кучи. У них обоих разные приложения, которые мы обсудим в следующем разделе.
С точки зрения асимптотического анализа временной сложности, вы можете построить двоичную кучу за O (n) и извлечь минимальное или максимальное значение за O (1). Вставки и удаления могут быть выполнены за время O (log N). Напротив, вставка и удаление занимают в стеке время O (1).
Типичные области применения
По причинам, описанным выше, кучи очень эффективны при использовании в качестве очереди с приоритетом. Графические алгоритмы, такие как минимальное связующее дерево Прима и кратчайший путь Дейкстры, обычно используют кучи в качестве очереди с приоритетом. Еще одно важное применение куч – это эффективная сортировка массива всего за O (N logN) времени; этот метод сортировки известен как «Сортировка в куче».
У стека также есть множество важных приложений, таких как управление памятью и оценка выражений. Если вы столкнулись с проблемой кодирования с возвратом, было бы неплохо сэкономить время, используя стек.
Приоритет структур данных
Каждый успешный программист скажет вам, как важно хорошо разбираться в структурах данных. Это отличная идея – попытаться понять и освоиться с использованием различных структур данных по мере необходимости, поскольку это жизненно важная концепция для каждого программиста.