Weighted Path Length Calculation

The weighted path length (WPL) of a binary tree is defined as the sum of the products of each leaf node's weight and its depth. To minimize the WPL, we construct a Huffman tree. The most efficient approach ivnolves using a min-priority queue to repeatedly merge the two smallest weights:

#include <queue>
#include <vector>
#include <iostream>

int calculateMinimalWPL(int count) {
   std::priority_queue<int, std::vector<int>, std::greater<int>> minHeap;
   for (int i = 0; i < count; ++i) {
       int weight;
       std::cin >> weight;
       minHeap.push(weight);
   }

   int totalCost = 0;
   while (minHeap.size() > 1) {
       int first = minHeap.top(); minHeap.pop();
       int second = minHeap.top(); minHeap.pop();
       int combined = first + second;
       totalCost += combined;
       minHeap.push(combined);
   }
   return totalCost;
}

Huffman Tree Construction and Prefix Coding

To generate variable-length prefix codes, we must build the Huffman tree structure explicitly. This involves creating internal nodes and traversing the resulting tree to assign '0' for left-child transitions and '1' for right-child transitions.

struct HuffmanNode {
   char character;
   int frequency;
   HuffmanNode *left, *right;
};

struct NodeComparator {
   bool operator()(HuffmanNode* a, HuffmanNode* b) {
       if (a->frequency != b->frequency) return a->frequency > b->frequency;
       return a->character > b->character;
   }
};

void generateCodes(HuffmanNode* node, std::string path, std::map<char, std::string>& results) {
   if (!node->left && !node->right) {
       results[node->character] = path;
       return;
   }
   if (node->left) generateCodes(node->left, path + "0", results);
   if (node->right) generateCodes(node->right, path + "1", results);
}

When building the tree, maintain a std::priority_queue of node pointers. In each iteration, extract the two nodes with the lowest frequencies, create a parent node with a frequency equal to the sum of its children, and re-insert the parenet into the queue untill only the root remains.