Huffman Tree

Source code: src/pydsadoc/_tree/huffman.py

class MinHeap(*args, **kwargs)

Implementation of the minimum heap with sequential list.

heapify(arr: list[HNode], /) → None

Make heap from list in a more efficient way.

It’s also called Floyd Algorithm, which is quicker than pushing items one by one. Time complexity is \(O(n)\).

heappop() → HNode

Remove and return smallest item from the heap.

Time complexity is \(O(\log n)\).

heappush(obj: HNode, /) → None

Push object into the heap, maintaining the heap invariant.

Time complexity is \(O(\log n)\).

class Huffman(freq: dict[str, int], /)

The implementation of the Huffman Tree.

encode() → dict[str, str]

Encode the input freq.

property wpl: int

Return attribute self.wpl.

The Priority Queue

The Huffman Tree can be built in an optimal way by using priority queue. The priority queue is implemented with minimum heap here, namely the class MinHeap described above.