Algorithm Introduction Example - Huffman

/ **

* Introduction to Algorithms, Second Edition

* 16.3 HUFFMAN CODES

*

* @Author Potato Dad

*

* /

Import java.util.list;

Public class huffman {

Static Class Node Implements iPriorityQueueElement {

Node left; // left subpost

Node Right; // Right child node

Integer f; // frequency

CHAR C; // character

Public node () {}

Public Node (CHAR C, INTEGER F) {

THIS.C = C;

THIS.F = F;

}

Public integer getKey () {

Return F;

}

}

Public Static Node Encode (list nodes) {

INT n = nodes.size ();

/ / Generate the minimum priority queue according to frequency

MinpriorityQueue queue = new minpriorityQueue (n);

For (Node Node: nodes) {

Queue.insert (node);

}

For (int i = 0; i

Node node = new node ();

Node x = queue.extractmin (); // Take the first two elements of the queue

Node y = queue.extractmin ();

Node.Left = x; // will take two elements as the child node of the new node

Node.right = y;

Node.f = x.f y.f; // The frequency of the new node is the sum of the sub-node frequency.

Queue.Insert (node); // Insert into the queue

}

Return queue.extractmin ();

}

}

/ **

* Introduction to Algorithms, Second Edition

* 6.5 min-priority queue

*

* @Author Potato Dad

*

* /

Import java.util.emptystackexception;

Public class minpriorityQueue , t extends ipriorityQueueElement > {

T [] array;

INT Heapsize;

/ **

* Constructor

* @Param size initial array size

* /

@Suppresswarnings ("unchecked")

Public minPriorityQueue (int size) {

Array = (t []) New ipriorityQueueElement [size];

}

/ **

* Get the minimum of current HEAP

*

* @return minimum

* /

Public t minimum () {

Return array [0];

}

/ **

* Get the minimum of the current HEAP and remove the minimum from the HEAP

* @return minimum

* /

Public t extractmin () {

Heapsize <1) {

Throw new emptystackexception ();

}

T min = array [0];

Array [0] = array [Heapsize - 1]; Heapsize -;

Minheapify (0);

Return min;

}

/ **

* Insert an element

* @Param E

* /

@Suppresswarnings ("unchecked")

Public void INSERT (T E) {

IF (Heapsize == array.length) {

T [] NEWARRAY = (t []) new ipriorityQueueElement [array.length * 2];

System.Arraycopy (Array, 0, Newarray, 0, Array.Length);

Array = NEWARRAY;

}

INT i = Heapsize ;

Array [i] = e;

INT P = Parent (i); // Father's node index

While (i> 0 && array [p] .GetKey (). Compareto (array [i] .getKey ())> 0) {

T temp = array [i];

Array [i] = array [p];

Array [P] = TEMP;

i = P;

P = Parent (i);

}

}

/ **

* Rearborne in the MAX HEAP rules

*

* @Param I

* Element index

* /

Private vid minheapify (int i) {

INT L = LEFT (i);

INT R = Right (i);

INT smallest; // The current node / left sub-node / maximum index in the right sub-node

IF (l

Smallst = L;

} else {

Smallst = i;

}

IF (R

Smallst = R;

}

IF (smallest! = i) {

// If the maximum is not the current node, exchange

T temp = array [i];

Array [i] = array [smallest];

Array [smallest] = TEMP;

// Remissive call until the current node is larger than its sub-node

Minheapiff (smallest);

}

}

/ **

* Calculate the index of the parent node of the element of the node index

*

* @Param I

* Current index

* @Return's index of the parent node

* /

Private Int Parent (int i) {

Return (i 1) / 2 - 1;

}

/ **

* Calculate the index of the left sub-node of the element of the node index

*

* @Param I

* Current index

* @Return's index of the left sub-node

* /

Private int LEFT (INT i) {

RETURN 2 * i 1;

}

/ **

* Calculate the index of the right sub-node of the element of the node index

*

* @Param I

* Current index

* @Return's index of the right child

* /

Private Int Right (INT I) {

RETURN 2 * i 2;

}

}

Public interface ipriorityQueueElement > {keytype getKey ();

}

Import java.util.arraylist;

Import java.util.list;

Import junit.framework.testcase;

Public Class Huffmantest Extends Testcase {

Public void testEncode () {

List c = new arraylist ();

C.ADD (New Huffman.Node ('A', 45));

C.ADD (New Huffman.Node ('B', 13));

C.Add (New Huffman.Node ('C', 12));

C.Add (New Huffman.Node ('D', 16));

C.ADD (New Huffman.Node ('E', 9));

C.ADD (New Huffman.Node ('F', 5));

Huffman.node root = huffman.encode (c);

askERTEQUALS (100, root.f.intvalue ());

Assertequals (45, root.left.f.intValue ());

Assertequals ('a', root.left.c);

Assertequals (55, Root.right.f.intValue ());

Assertequals ('c', root.right.Left.Left.c);

Assertequals ('b', root.right.Light.right.c);

Assertequals ('f', root.right.right.right.Light.L);

Assertequals ('e', root.right.right.right.right.Right.c);

Assertequals ('d', root.right.right.right.c);

}

}