public void BuildTree()

in src/ICSharpCode.SharpZipLib/Zip/Compression/DeflaterHuffman.cs [196:329]
92 lines of code
18 McCabe index (conditional complexity)

			public void BuildTree()
			{
				int numSymbols = freqs.Length;

				/* heap is a priority queue, sorted by frequency, least frequent
				* nodes first.  The heap is a binary tree, with the property, that
				* the parent node is smaller than both child nodes.  This assures
				* that the smallest node is the first parent.
				*
				* The binary tree is encoded in an array:  0 is root node and
				* the nodes 2*n+1, 2*n+2 are the child nodes of node n.
				*/
				int[] heap = new int[numSymbols];
				int heapLen = 0;
				int maxCode = 0;
				for (int n = 0; n < numSymbols; n++)
				{
					int freq = freqs[n];
					if (freq != 0)
					{
						// Insert n into heap
						int pos = heapLen++;
						int ppos;
						while (pos > 0 && freqs[heap[ppos = (pos - 1) / 2]] > freq)
						{
							heap[pos] = heap[ppos];
							pos = ppos;
						}
						heap[pos] = n;

						maxCode = n;
					}
				}

				/* We could encode a single literal with 0 bits but then we
				* don't see the literals.  Therefore we force at least two
				* literals to avoid this case.  We don't care about order in
				* this case, both literals get a 1 bit code.
				*/
				while (heapLen < 2)
				{
					int node = maxCode < 2 ? ++maxCode : 0;
					heap[heapLen++] = node;
				}

				numCodes = Math.Max(maxCode + 1, minNumCodes);

				int numLeafs = heapLen;
				int[] childs = new int[4 * heapLen - 2];
				int[] values = new int[2 * heapLen - 1];
				int numNodes = numLeafs;
				for (int i = 0; i < heapLen; i++)
				{
					int node = heap[i];
					childs[2 * i] = node;
					childs[2 * i + 1] = -1;
					values[i] = freqs[node] << 8;
					heap[i] = i;
				}

				/* Construct the Huffman tree by repeatedly combining the least two
				* frequent nodes.
				*/
				do
				{
					int first = heap[0];
					int last = heap[--heapLen];

					// Propagate the hole to the leafs of the heap
					int ppos = 0;
					int path = 1;

					while (path < heapLen)
					{
						if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]])
						{
							path++;
						}

						heap[ppos] = heap[path];
						ppos = path;
						path = path * 2 + 1;
					}

					/* Now propagate the last element down along path.  Normally
					* it shouldn't go too deep.
					*/
					int lastVal = values[last];
					while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal)
					{
						heap[path] = heap[ppos];
					}
					heap[path] = last;

					int second = heap[0];

					// Create a new node father of first and second
					last = numNodes++;
					childs[2 * last] = first;
					childs[2 * last + 1] = second;
					int mindepth = Math.Min(values[first] & 0xff, values[second] & 0xff);
					values[last] = lastVal = values[first] + values[second] - mindepth + 1;

					// Again, propagate the hole to the leafs
					ppos = 0;
					path = 1;

					while (path < heapLen)
					{
						if (path + 1 < heapLen && values[heap[path]] > values[heap[path + 1]])
						{
							path++;
						}

						heap[ppos] = heap[path];
						ppos = path;
						path = ppos * 2 + 1;
					}

					// Now propagate the new element down along path
					while ((path = ppos) > 0 && values[heap[ppos = (path - 1) / 2]] > lastVal)
					{
						heap[path] = heap[ppos];
					}
					heap[path] = last;
				} while (heapLen > 1);

				if (heap[0] != childs.Length / 2 - 1)
				{
					throw new SharpZipBaseException("Heap invariant violated");
				}

				BuildLength(childs);
			}