Почему дочерние узлы имеют 2 * i + 1 и 2 * i + 2? - PullRequest
Новая
       22

Почему дочерние узлы имеют 2 * i + 1 и 2 * i + 2?

2 голосов
/ 08 ноября 2019

В настоящее время я пытаюсь реализовать алгоритм сжатия Хаффмана с использованием очереди приоритетов (Min Heap). Я нашел ресурс в Интернете, который мог бы помочь мне, хотя есть фрагмент кода, который я не понимаю, и, к сожалению, я не нахожу никаких обязательных объяснений по этому поводу.

1) В функции minHeapify почему осталось/ право равно 2 * idx + 1/2 * idx +2?

2) В функции insertMinHeap, почему мы тестируем, если `Node-> Frequency array [(i-1) /2]. Какова цель (i-1) / 2?

Любые объяснения приветствуются. Цените свое время. 

void minHeapify(struct MinHeap* minHeap, int idx) 

{ 

    int smallest = idx; 
    int left = 2 * idx + 1; 
    int right = 2 * idx + 2; 

    if (left < minHeap->size && minHeap->array[left]-> 
freq < minHeap->array[smallest]->freq) //
        smallest = left; 

    if (right < minHeap->size && minHeap->array[right]-> 
freq < minHeap->array[smallest]->freq) 
        smallest = right; 

    if (smallest != idx) { 
        swapMinHeapNode(&minHeap->array[smallest], 
                        &minHeap->array[idx]); 
        minHeapify(minHeap, smallest); 
    } 
} 

void insertMinHeap(struct MinHeap* minHeap, 
                   struct MinHeapNode* minHeapNode) 

{ 

    ++minHeap->size; 
    int i = minHeap->size - 1; 

    while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) { 

        minHeap->array[i] = minHeap->array[(i - 1) / 2]; 
        i = (i - 1) / 2; 
    } 

    minHeap->array[i] = minHeapNode; 
}
...