public void buildTree ( int [ ] vertexDegree ) { PriorityQueue < Node > pq = new PriorityQueue <> ( ) ; for ( int i = 0 ; i < vertexDegree . length ; i ++ ) pq . ( new Node ( i , vertexDegree [ i ] , null , null ) ) ; while ( pq . size ( ) > 1 ) { Node left = pq . remove ( ) ; Node right = pq . remove ( ) ; Node newNode = new Node ( - 1 , left . count + right . count , left , right ) ; pq . add ( newNode ) ; } //Eventually: only one node left -> full tree Node tree = pq . remove ( ) ; //Now: convert tree into binary codes. Traverse tree (preorder traversal) -> record path (left/right) -> code int [ ] innerNodePath = new int [ MAX_CODE_LENGTH ] ; traverse ( tree , 0L , ( byte ) 0 , - 1 , innerNodePath , 0 ) ; }
Build the Huffman tree given an array of vertex degrees