Найти все ключи, меньшие, чем x в массиве min-heap

Question

Может ли кто-нибудь описать алгоритм, который найдет все ключи, меньшие, чем x, в реализации массива мини-кучи. Я хочу, чтобы время работы было как минимум O (k), где k - количество сообщенных ключей.

Я уже немного почесываю голову.

Answer 1

Существует простой рекурсивный алгоритм для дерева мин-кучи:

void smaller_than(Node *node, int x) 
{ 
    if (node->value >= x) 
    { 
     /* Skip this node and its descendants, as they are all >= x . */ 
     return; 
    } 

    printf("%d\n", node->value); 

    if (node->left != NULL) 
     smaller_than(node->left, x); 
    if (node->right != NULL) 
     smaller_than(node->right, x); 
} 

Если корень поддерева имеет значение, которое больше или равно к x, то, по определению мини-кучи, все его потомки также будут иметь значения, большие или равные x. Алгоритм не должен исследовать глубже, чем предметы, пересекающие его, следовательно, это O (k).

Конечно, это пустяк перевод этого к алгоритму массива:

#define ROOT  0 
#define LEFT(pos) ((pos)*2 + 1) 
#define RIGHT(pos) ((pos)*2 + 2) 

void smaller_than(int x, int pos, int heap[], int count) 
{ 
    /* Make sure item exists */ 
    if (pos >= count) 
     return; 

    if (heap[pos] >= x) 
    { 
     /* Skip this node and its descendants, as they are all >= x . */ 
     return; 
    } 

    printf("%d\n", heap[pos]); 

    smaller_than(x, LEFT(pos), heap, count); 
    smaller_than(x, RIGHT(pos), heap, count); 
} 

Answer 2

Чтобы получить время работы «по крайней мере», что-то не так сложно, я предполагаю, что вы имеете в виду «самое большее».

К сожалению, мини-куча не очень хороша в поиске чего-либо другого, кроме наименьшего значения.

Вы можете сделать вначале глубину сканирования дерева в виде кучи и завершить каждую ветвь, где вы достигли X. Это будет O (k), но сложнее.

Чтобы найти все Y, где Y < = X, вы можете также сканировать весь массив, это будет O (n), но с гораздо меньшими накладными расходами.

Выбор зависит от отношения п/к

Answer 3

Реализация, как массив не имеет значения, вы можете сделать сверху вниз дерево-поиска. Вместо того, чтобы использовать «классические» указатели, вам нужно вычислить соответствующие индексы дочерних узлов.

С этой целью вы можете найти рекурсивный поиск сверху и остановить рекурсию на каждой ветви, где текущий узел больше, чем x. Это, в общем, отсекает множество ценностей, которые вам не нужно проверять.

С k значениями возврата O (k) является, очевидно, вашим лучшим случаем. Если ваш верхний узел равен < = x, вы сразу начинаете получать результаты. Если его больше, вы сделали - результат пуст.

Оттуда вы получаете результаты полностью вниз по поддереву, пока не нажмете ветви со значениями> x. Вам нужно сделать не более 2 * k Проверки, чтобы обрезать эти ветви, так что это выглядит как O (k) в целом для меня.