Какая польза от структуры данных Heap?

Question

Я работаю над некоторыми домашними заданиями, связанными с кучами, и понимаю, как они структурированы.Куча должна иметь каждый узел, удовлетворяющий свойству кучи,

свойство max-heap таково, что для каждого узла i, кроме корня, Heap [Parent (i)]> = Heap [i]

Таким образом, в каждом узле более высокие узлы имеют более высокие номера, более низкие узлы имеют более низкие номера.Это я поняла.Но я не вижу использования кучи, кроме как просто получить самые большие n чисел в списке.Я не вижу простого способа поиска определенного значения и возврата узла или поиска n-го наименьшего числа (в max-heap).И то, и другое относительно просто в бинарном дереве поиска.

Почему бы вам не использовать простое бинарное дерево поиска?Или, что еще лучше, сбалансированное бинарное дерево поиска?

РЕДАКТИРОВАТЬ: я должен отметить, что это не ищет ответа на проблему домашней работы.Фактическая проблема с домашней работой заключалась в написании псевдокода для параллельной p-heap для функций insert () и extractMax ().И я уже ответил на них.Они просто заставили меня понять, что я на самом деле не понимаю Кучи.

Answer 1

В структуре данных кучи много приложений.

• Heapsort : Один из лучших методов сортировки на месте и без квадратичных наихудших сценариев.
• Алгоритмы выбора : Поиск минимального, максимального, минимального и максимального, медианного или даже k-го наибольшего элемента может быть выполнен за линейное время (часто постоянное время) с использованием куч. [4 ]
• Алгоритмы графа : При использовании кучи в качестве внутренних структур данных обхода время выполнения будет сокращено на полиномиальный порядок. Примерами таких проблем являются алгоритм минимального связующего дерева Прима и задача Дейкстры по кратчайшему пути.

Полные и почти полные двоичные кучи могут быть представлены очень экономно, используя только массив. Первый (или последний) элемент будет содержать корень. Следующие два элемента массива содержат его дочерние элементы. Следующие четыре содержат четыре дочерних элемента двух дочерних узлов и т. Д. Таким образом, дочерние элементы узла в позиции n будут находиться в позициях 2n и 2n + 1 в массиве на основе одного, или 2n + 1 и 2n + 2 в массив с нуля. Это позволяет перемещаться вверх или вниз по дереву, выполняя простые вычисления индекса. Балансировка кучи осуществляется путем замены элементов, которые вышли из строя. Поскольку мы можем построить кучу из массива, не требуя дополнительной памяти (например, для узлов), для сортировки массива на месте можно использовать heapsort.

Еще одно преимущество куч в сравнении с деревьями в некоторых приложениях заключается в том, что построение куч может быть выполнено за линейное время с использованием алгоритма Тарьяна.

Ссылка: http://en.wikipedia.org/wiki/Heap_%28data_structure%29

Answer 2

Из-за отсутствия указателей (кучи обычно используют структуру данных на основе массива), операции, как правило, выполняются быстрее, чем для двоичного дерева.Кроме того, некоторые более сложные кучи (например, биномиальные) могут быть эффективно объединены, что нелегко сделать для двоичного дерева.Также имеется информация, доступная по этому вопросу SO .