Поиск наименьшего элемента двоичной максимальной кучи, хранящейся в массиве Ahnentafel

Question

У меня есть бинарная максимальная куча (наибольший элемент в верхней части), и мне нужно держать ее в постоянном размере (например, 20 элементов), избавляясь от самый маленький элемент каждый раз, когда я добираюсь до 20 элементов. Бинарная куча хранится в массиве с дочерними узлами i при 2 * i и 2 * i + 1 (i на основе нуля). В любой момент куча имеет элементы «n_elements», между 0 и 20. Например, массив [16,14,10,8,7,9,3,2,4] будет действительной максимальной бинарной кучей, с 16, имеющих детей 14 и 10, 14, имеющих детей 8 и 7 ...

Чтобы найти наименьший элемент, кажется, что в общем случае мне нужно пересечь массив из n_elements/2 в n_elements: наименьший элемент не обязательно последний в массиве.

Итак, с помощью всего этого массива кажется, что любая попытка найти/удалить наименьший elt не менее O (n). Это верно?

Answer 1

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

Если вы создаете эту структуру данных кучи самостоятельно, вы можете сохранить отдельный указатель на расположение самого маленького элемента в массиве. Поэтому всякий раз, когда новый элемент добавляется в кучу, проверьте, меньше ли новый элемент. Если да, обновите указатель и т. Д. Тогда поиск наименьшего элемента будет O(1).

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

Если вам требуется более быстрое удаление, вам также необходимо сохранить минимальную кучу всех элементов. В этом случае удаление будет O(log(n)). Вставка займет 2 раза, потому что вам нужно вставить две кучи, и она также займет 2x пространство.

Кстати, если у вас есть только 20 элементов в любой момент времени, это не будет иметь большого значения (если это не проблема с домашней работой, или вы просто делаете это для удовольствия). Это было бы действительно важно, только если вы планируете масштабировать его до тысяч значений.

Answer 2

Существует структура данных minmax heap: http://en.wikipedia.org/wiki/Min-max_heap. Конечно, это код довольно сложный, но с двумя отдельными кучами мы должны использовать много дополнительного пространства (для второй кучи, для поддержания сопоставления один к одному) и выполнять работу дважды.

Answer 3

Для любой заданной допустимой Max Heap минимум будет только для листовых узлов. Следующий вопрос - как найти листовые узлы кучи в массиве?. Если мы внимательно наблюдаем за последним узлом массива, это будет последний листовой узел. Получить родительский узел листа по формуле

parent node index = (leaf Node Index)/2 

Начать линейный поиск по индексу (parent node index +1) к индексу узла последнего листа получить минимальное значение в этом диапазоне.

FindMinInMaxHeap(Heap heap) 
    startIndex = heap->Array[heap->lastIndex/2] 
    if startIndex == 0 
      return heap->Array[startIndex] 
    Minimum = heap->Array[startIndex + 1] 
    for count from startIndex+2 to heap->lastIndex 
      if(heap->Array[count] < Minimum) 
       Minimum := heap->Array[count] 
    print Minimum