哈夫曼树

Mr.Hdd大约 4 分钟...

「哈夫曼树 Huffman Tree」

「哈夫曼树」也称「最优二叉树」，在含有 $n$ 个带权叶结点的二叉树中，其中带权路径长度 ( WPL ) 最小的二叉树就是哈夫曼树。

哈夫曼树相关术语

结点的权值 (weight)：有某种现实含义的数值 (如: 表示结点的重要性)
结点的「带权路径长度 weighted path length」(WPL)：从树的根结点到该结点的路径长度 (经过的边数) 与该结点上权值的乘积
树的带权路径长度：树中所有叶结点的带权路径长度之和：

WPL = \sum_{k=1}^{n}w_k \ l_k

其中， $w_k$ 为第 $k$ 个叶子结点的权值， $l_k$ 为从根结点到第 $k$ 个叶子结点的路径长度（经过的边数）.

相关信息

从上图中可以看出，当叶子结点权值越大并且距离根结点越近时，可以使整颗树的 WPL 更小，这也符合哈夫曼树的定义.

计算 WPL 时可使用「小根堆(优先队列)」来实现：

use std::collections::BinaryHeap;
use std::cmp::Reverse;
/**
 * v: 初始各个结点的值
 * return : wpl 
 */
fn cal_wpl(v: Vec<usize>) -> usize {
  let mut heap = BinaryHeap::<Reverse<usize>>::new();
  // 初始化小根堆
  for i in v { heap.push(Reverse(i)); }
  let mut wpl = 0;
  // 每次选择堆中最小的两个元素
  while heap.len() > 1 {
    let x = heap.pop().unwrap_or(Reverse(0));
    let y = heap.pop().unwrap_or(Reverse(0));
    wpl = wpl + x.0 + y.0;
    heap.push(Reverse(x.0 + y.0));   // 将合并后的值加入堆中
  }
  wpl
}
fn main() {
  let v: Vec<usize> = vec![1, 3, 4, 5];
  let wpl = cal_wpl(v);
  println!("{}", wpl);
}

import java.util.Arrays;
import java.util.PriorityQueue;
public class Huffman {
  public static void main(String[] args) {
    Integer a[] = {1, 3, 4, 5};
    // 定义小根堆 PriorityQueue 默认是小根堆
    PriorityQueue<Integer> heap = new PriorityQueue<>();
    heap.addAll(Arrays.asList(a));
    Integer wpl = 0;
    // 每次选择堆中最小的两个元素
    while (heap.size() > 1) {
      Integer x = heap.poll();
      Integer y = heap.poll();
      wpl += x + y;
      heap.add(x + y);   // 将合并后的值加入堆中
    }
    System.out.println(wpl);
  }
}

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int cal_wpl(vector<int> a) {
  // 定义小根堆
  priority_queue<int, vector<int>, greater<int>> heap;
  // 初始化小根堆
  for(auto v: a) { heap.push(v);}
  int wpl = 0;
  // 每次选择堆中最小的两个元素
  while ( heap.size() > 1) {
    int x = heap.top();
    heap.pop();
    int y = heap.top();
    heap.pop();
    wpl += x + y;
    heap.push(x + y); // 将合并后的值加入堆中
  }
  return wpl;
}
int main() {
  vector<int> a = {1, 3, 4, 5};
  int wpl = cal_wpl(a);
  cout << wpl << endl;
  return 0;
}