构造霍夫曼编码

class HuffmanTreeNode(val str: String) {
    //权重
    var weight = 0
    var left: HuffmanTreeNode? = null
    var right: HuffmanTreeNode? = null
    var parent: HuffmanTreeNode? = null

    fun setWeight(w: Int): HuffmanTreeNode {
        weight = w
        return this
    }
}

/**
 * 构造霍夫曼树
 *
 * @param list 节点列表
 * @return 霍夫曼节点
 */
fun buildHuffmanTree(list: List<HuffmanTreeNode>): HuffmanTreeNode? {
    if (list.isEmpty())
        return null
    if (list.size == 1) {
        return list[0]
    }
    //构建小顶堆
    var array: Array<HuffmanTreeNode> = Array(list.size) { i -> list[i] }
    buildMinHeap(array)

    var size = array.size
    while (size > 1) {
        //取出最小的节点
        var min1 = getMinWeightNode(array, size)
        //取出最小的节点
        var min2 = getMinWeightNode(array, size - 1)
        //构造新的节点
        var newNode = HuffmanTreeNode("").setWeight(min1.weight + min2.weight)
        newNode.left = min1
        newNode.right = min2
        min1.parent = newNode
        min2.parent = newNode
        size--
        if (size == 1) {
            return newNode
        }
        //新的节点插入小顶堆
        insertNode(array, size - 1, newNode)
    }
    return null
}

/**
 * 根据权重构造小顶堆
 */
fun buildMinHeap(array: Array<HuffmanTreeNode>) {
    for (i in array.size / 2 downTo 0) {
        var min = i
        while (min < array.size && (min * 2 + 1) < array.size) {
            var tmp = min
            var left = min * 2 + 1
            var right = left + 1
            if (left < array.size && array[min].weight > array[left].weight) {
                min = left
            }
            if (right < array.size && array[min].weight > array[right].weight) {
                min = right
            }
            if (tmp == min)
                break
            else {
                var t = array[tmp]
                array[tmp] = array[min]
                array[min] = t
            }
        }
    }
}

/**
 * 取出权重值最小的元素，即小顶堆堆顶元素，剩余的元素会重新堆化
 *
 * @param array 小顶堆数组
 * @param size 当前小顶堆数组元素的个数
 *
 * @return 最小的元素
 */
fun getMinWeightNode(array: Array<HuffmanTreeNode>, size: Int): HuffmanTreeNode {
    var top = array[0]
    array[0] = array[size - 1]
    var i = 0
    while (i < size - 1) {
        var tmp = i
        var left = i * 2 + 1
        var right = left + 1
        if (left < size - 1 && array[i].weight > array[left].weight) {
            i = left
        }
        if (right < size - 1 && array[i].weight > array[right].weight) {
            i = right
        }
        if (tmp == i)
            break
        else {
            var t = array[tmp]
            array[tmp] = array[i]
            array[i] = t
        }
    }
    return top
}

/**
 * @param array 小顶堆数组
 * @param size 当前小顶堆数组元素个数
 * @param node 要插入的节点
 *
 * @return 插入节点后小顶堆元素个数
 */
fun insertNode(array: Array<HuffmanTreeNode>, size: Int, node: HuffmanTreeNode): Int {
    array[size] = node
    var i = size
    while (i > 0) {
        var parent = (i - 1) / 2;
        if (array[parent].weight > array[i].weight) {
            var tmp = array[parent];
            array[parent] = array[i];
            array[i] = tmp;
            i = parent;
        } else {
            break;
        }
    }
    return size + 1
}

//获取霍夫曼编码
fun getHuffmanCode(node: HuffmanTreeNode): String {
    var stack = Stack<String>()
    var curr = node
    while (curr.parent != null) {
        var p = curr.parent!!
        if (p.left == curr) {
            stack.push("0")
        } else {
            stack.push("1")
        }
        curr = p
    }
    var sb = StringBuilder()
    while (stack.isNotEmpty()) {
        sb.append(stack.pop())
    }
    return sb.toString()
}

fun main() {

    var a = HuffmanTreeNode("a").setWeight(450)
    var b = HuffmanTreeNode("b").setWeight(350)
    var c = HuffmanTreeNode("c").setWeight(90)
    var d = HuffmanTreeNode("d").setWeight(60)
    var e = HuffmanTreeNode("e").setWeight(30)
    var f = HuffmanTreeNode("f").setWeight(20)

    val nodeList = listOf(a, b, c, d, e, f)
    //构造霍夫曼树
    var root = buildHuffmanTree(nodeList)

    var map = mutableMapOf<String, String>()
    root?.let {
        map.put(a.str, getHuffmanCode(a))
        map.put(b.str, getHuffmanCode(b))
        map.put(c.str, getHuffmanCode(c))
        map.put(d.str, getHuffmanCode(d))
        map.put(e.str, getHuffmanCode(e))
        map.put(f.str, getHuffmanCode(f))
    }

    for (entry in map) {
        println("${entry.key}: ${entry.value}")
    }
}

最终结果如下：

a: 0
b: 11
c: 100
d: 1010
e: 10111
f: 10110