Изменение значения элемента кучи в C

Question

Я реализовал мин кучу в C.

Моя куча это массив структур. Я расположил элементы в куче в соответствии со значением длины элемента в структуре. В моей программе я должен динамически изменять "длину" некоторых членов. После изменения этого значения моя куча была восстановлена. Я нахожу трудности в реконструкции части этого.

Мой код:

typedef struct edge{

int source;
int dest;
int length;
}edge_st;

typedef struct heap{

 edge_st* edge[100];
 int size;

 }heap;

Код для перенастройки выглядит следующим образом:

void modifyHeap(heap* h, int ref, int newval)
{
    int i;
    for(i=0; i<h->size; i++)
    {
        if(h->edge[i]->source == ref)
        {
            if(h->edge[i]->length==INT_MAX)
            {
                h->edge[i]->length = 0;
            }
            h->edge[i]->length = h->edge[i]->length+newval;
            break;
        }
    }

    heapify(h,0,h->size);

}

Я занимаюсь поиском структуры со ссылкой и изменением ее длины. После изменения я попытался снова выполнить heapify, но он не работает, потому что измененный элемент не может быть непосредственным потомком root(0). Если я сделаю

    heapify(h,i,h->size);

это также не работает, так как для меня не может быть детей.

Есть ли другой выход из этой проблемы?

Answer 1

После того, как вы изменили значение узла, вам нужно всплыть или всплыть.

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

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

Это операция во время регистрации.

Обратите внимание, что эти операции те же, что вам нужны для добавления узла в кучу и для удаления min. Чтобы добавить узел, вы помещаете его внизу и всплываете, пока он не достигнет нужного места. Чтобы удалить мин, вы вынимаете корневой узел и заменяете его последним, а затем всплывает, пока он не достигнет нужного места.

Смотрите источник всех знаний по этой теме.