基于最小堆的Huffman压缩实现：堆索引计算相关疑问

Hey there! Let's break down these two key questions about your Huffman coding heap implementation—they’re all about how binary heaps are structured and manipulated when stored as arrays, which is super foundational here. First, let’s format your code for clarity:

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; 
}

1) Why are left/right child indices 2*idx+1 and 2*idx+2 in minHeapify? #

This is the standard indexing rule for 0-indexed arrays storing a binary heap. Binary heaps are complete binary trees, and we store their nodes in the array using level-order traversal (top to bottom, left to right).

If your heap used 1-indexed arrays (starting counting at 1), the left child of index idx would be 2*idx and the right child 2*idx+1. But since your code uses a 0-indexed array (the root is at index 0), we adjust those formulas by adding 1 to shift everything over:

• Left child: 2*idx + 1
• Right child: 2*idx + 2

For example:

• Root node (index 0) has left child at 1, right at 2
• Node at index 1 has left child at 3, right at 4
• Node at index 2 has left child at 5, right at 6

This ensures the array perfectly maps to the structure of the complete binary tree, letting minHeapify correctly find and compare a node's children to maintain the min-heap property.

2) Why check minHeapNode->freq < minHeap->array[(i-1)/2]->freq, and what does (i-1)/2 do? #

The expression (i-1)/2 is the inverse of the child indexing rule—it calculates the index of the parent node for the current node at index i. Let's verify with examples:

• If i=1 (left child of root), parent index is (1-1)/2 = 0
• If i=2 (right child of root), parent index is (2-1)/2 = 0 (integer division truncates to 0)
• If i=3 (left child of node 1), parent index is (3-1)/2 = 1

Now, the logic in insertMinHeap is called "heap bubbling up" or "percolating up":

1. We first add the new node to the end of the array (hence i = minHeap->size - 1, since we just incremented the size)
2. We then check if this new node has a smaller frequency than its parent (since this is a min-heap, parents must be smaller than children)
3. If it does, we move the parent down to the current node's position, then update i to the parent's index and repeat the check
4. We stop when the new node is either at the root (i=0) or its parent is smaller than it, then place the new node in the correct position

That conditional check ensures we only swap when necessary, maintaining the min-heap property as we insert the new element.

内容的提问来源于stack exchange，提问作者Nikola Stoilov