Реализация очереди приоритетов с использованием максимальной кучи и сбалансированной BST

Question

Сбалансированный BST и максимальная куча выполняют вставку и удаление O(logn). Однако поиск максимального значения в максимальной куче - O(1)это только O(logn)в сбалансированном BST.

Если мы удалим максимальное значение в максимальной куче, это потребуется, O(logn)потому что это операция удаления.

В сбалансированном BST удаление максимального элемента = поиск максимального значения + удаление; он равен logn + logn сокращается до O(logn). Таким образом, даже удаление максимального значения в сбалансированном BST O(logn).

Я читал, что одно такое приложение максимальной кучи является приоритетной очередью, и его основная цель - удалить максимальное значение для каждой операции удаления из очереди. Если удаление максимального элемента предназначено O(logn)как для максимальной кучи, так и для сбалансированного BST, у меня есть следующие вопросы

• Какова цель максимальной кучи в очереди с приоритетами только потому, что ее легко реализовать, а не использовать полностью сбалансированный BST с возможностью поиска?

• Поскольку нет расчета коэффициента балансировки, максимальную кучу можно назвать несбалансированным двоичным деревом?

• Каждый сбалансированный BST можно использовать в качестве очереди с приоритетом, и который также доступен для поиска, O(logn)однако поиск максимальной кучи является O(n)правильным?

Все временные сложности рассчитаны для наихудшего случая. Любая помощь приветствуется.

Answer 1

Какова цель максимальной кучи в очереди с приоритетами только потому, что ее легко реализовать, а не использовать полностью сбалансированный BST с возможностью поиска?

Некоторые преимущества кучи:

• Принимая во внимание несортированный массив ввода, кучи все еще может быть построена в O (N) времени , в то время как БСТ нуждается в O (NlogN) времени .

• Если исходный ввод представляет собой массив, тот же массив может служить кучей, что означает, что для него не требуется дополнительная память. Хотя можно было подумать о способах создания BST с использованием данных на месте в массиве, это было бы довольно странно (для примитивных типов) и увеличило бы накладные расходы на обработку. BST обычно создается с нуля, копируя данные в узлы по мере их создания.

  Интересный факт: отсортированный массив также является кучей, поэтому, если известно, что входные данные отсортированы, ничего не нужно делать для создания кучи.

• Куча может храниться в виде массива без необходимости хранения перекрестных ссылок , в то время как BST обычно состоит из узлов с левыми и правыми ссылками. Это имеет как минимум два последствия:

  • Память, используемая для BST, примерно в 3 раза больше, чем для кучи.
  • Хотя несколько операций имеют одинаковую временную сложность как для кучи, так и для BST, накладные расходы на адаптацию BST намного больше, поэтому фактическое время, затрачиваемое на эти операции, является (постоянным) фактором больше в случае BST.

Поскольку нет расчета коэффициента балансировки, максимальную кучу можно назвать несбалансированным двоичным деревом?

На самом деле куча - это полное двоичное дерево , поэтому оно всегда максимально сбалансировано: листья всегда будут располагаться на последнем или предпоследнем уровне. Самобалансирующийся BST (например, AVL, красно-черный, ...) не может превзойти этот высокий уровень балансировки, при котором у вас часто возникают листья на трех или даже более уровнях.

Каждый сбалансированный BST может использоваться в качестве очереди с приоритетом, и который также доступен для поиска в O (logn), однако максимальный поиск в куче правильный O (n)?

Да, это правда. Так что, если приложению нужна функция поиска, лучше использовать BST.

Answer 2

Какова цель максимальной кучи в очереди с приоритетами только потому, что ее легко реализовать, а не использовать полностью сбалансированный BST с возможностью поиска?

Неа. Максимальная куча подходит лучше, так как она тщательно оснащена для возврата следующего (с учетом приоритета) элемента как можно скорее, за время O (1). Это то, что вы хотите от простейшей очереди с приоритетами.

Поскольку нет расчета коэффициента балансировки, максимальную кучу можно назвать несбалансированным двоичным деревом?

Неа. Баланс тоже есть. Короче говоря, балансировка кучи выполняется операциями сдвига вверх или сдвиг вниз (замена вышедших из строя элементов).

Каждый сбалансированный BST может использоваться в качестве очереди с приоритетом, и который также доступен для поиска в O (logn), однако максимальный поиск в куче правильный O (n)?

Ага! Также можно использовать связанный список или массив. Просто это будет дороже с точки зрения O-нотации и намного медленнее на практике.