Поиск - это бинарная работа?

Question

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

Почему бы и нет? Двоичные кучи могут не отсортировать, но они заказаны, и полный график может найти какой -либо объект в $ O (n) $ времени, нет?

Страница неверна или я?

Answer 1

На самом деле это зависит от вашей точки зрения или уровня детализации.

А куча, или лучше Приоритетная очередь, поскольку абстрактная структура данных обычно поддерживает такие операции, как пустой, дополнение, Удалить мин. Анкет И обычно нет находка. Анкет Это структура данных, рассматриваемая как спецификация, исправляя набор операций и их поведение. Реализация неизвестна, это может быть связанное дерево или массив.

Однако страница Википедии связана с реализацией. Это даже ясно из названия двоичная куча. Анкет (Вы понимаете двоичную кучу, выглядя так, как будто это дерево, вы реализуете ее с помощью массива). В этой реализации легко можно увидеть, как запрограммировать вашу работу находка. Анкет Технически, это еще одна абстрактная структура данных (поскольку она имеет дополнительную операцию APRT от стандартных операций кучи).

На практике кучи (приоритетные очереди) часто используются для алгоритмов графика, таких как Dijkstra. Там важно, чтобы приоритеты, хранящиеся в куче, могли быть изменены (если мы найдем более короткий маршрут). Это возможно только в том случае, если мы сможем найти элемент в куче, чтобы мы могли настроить его приоритет (и изменить элемент в куче). Обычно это делается путем создания другой структуры поверх кучи, чтобы мы могли эффективно найти позиции, в которых хранятся элементы.

Answer 2

В двоичной куче значения действительно упорядочены, и операция поиска дегенератирует до сканирования массива, если значение/ключ равно> = последнее значение в массиве. Однако, если значение, которое вы ищете, близко к первому (т.е. Индекс, близкий к 0), то вы сможете остановиться рано и не сканировать массив в поисках значения, которого нет.

Например (C ++), такая реализация для вектора, которая удерживает двоичную кучу:

template <class Compare>
uint32_t SearchHeapImpl(const uint32_t idx, const T V, const Compare &cmp) const
{       
    if (slots[idx] == V)
        return idx;
     else if (cmp(slots[idx], V))
         return UINT32_MAX;

     const auto leftChild = 2 * idx + 1;

     if (leftChild >= nElements)
         return UINT32_MAX;

     const auto i = SearchHeapImpl(leftChild, V, cmp);

     if (i != UINT32_MAX)
         return i;

     const auto rightChild = leftChild + 1;

     return rightChild >= nElements ? UINT32_MAX : SearchHeapImpl(rightChild, V, cmp);
}

template<class Compare = std::greater<T>>
uint32_t SearchHeap(const T V, const Compare cmp = Compare()) const
{
    return nElements ? SearchHeapImpl(0, V, cmp) : UINT32_MAX;
}

будет прервать поиск рано, если cmp(slots[idx], V) == true

Как упоминали другие, такие структуры данных подходят для O (1) Peek, а O (log n) вставьте и удаляют операции. Список пропусков или двоичное дерево с самим собой (например, красные черные деревья), как правило, являются лучшей альтернативой, если вам нужна поиск O (log n) (вы обмениваете O (1) на Peek, для O (log n) для поиска). Конечно, они, как правило, более сложные, требуют большей памяти, и паттерны случайного доступа могут влиять на производительность из -за ударов в кэш и т. Д.