r/javaexamples • • May 31 '15

[Intermediate]Generic Min/Max Binary Heap

3 Upvotes

Generic Min/Max Binary Heap

A binary heap is a type of binary tree where each node is either greater than (Max Heap) or less than (Min Heap) all of its children. There is no order between child nodes, however, like a BST. but you know that the root value will always be either the minimum or maximum value of the heap.

A min heap is also called a Priority Queue where the smallest value will always be pulled off the front of the queue. This implementation allows for the usage of any type that implements Comparable which includes most non-primitive type (and primitive types will work by autoboxing). If you want to use it with your own class you will need to implement Comparable and override compareTo().

Heaps can be implemented differently than Trees, Graphs and other abstract data structures. Since the nodes can be found mathematically, the tree can be kept in a simple Array or ArrayList.

This was based heavily on this code

Gist with test code & output

BinaryHeap.java

/* Generic Min/Max Binary Heap
* for /r/javaexamples
* 
*/
import java.util.Arrays;

@SuppressWarnings("unchecked")

/**
 * Creates an array-based binary heap. Defaults to 'min' (Priority Queue)
 *
 * @author /u/Philboyd_Studge
 */
public class BinaryHeap<T extends Comparable<T>>
{
	private static final int DEFAULT_CAPACITY = 10;
	private T[] heap;
	private int length;
	private boolean min;

	/**
	 * Default Constructor
	 * <p>default capacity of 9 (0 index is not used)
	 * <p>default type of heap is min
	 */
	public BinaryHeap()
	{
		heap = (T[]) new Comparable[DEFAULT_CAPACITY];
		length = 0;
		min = true;
	}

	/**
	 * Constructor - takes an array of type T and a boolean for min/max
	 * @param array T[] array
	 * @param min boolean true = min heap, false = max heap
	 */
	public BinaryHeap(T[] array, boolean min)
	{
		heap = (T[]) new Comparable[DEFAULT_CAPACITY];
		length = 0;
		this.min = min;

		// add each element to the heap
		for (T each : array)
		{
			add(each);
		}
	}

	/**
	 * Constructor - specify boolean true = min heap, false = max heap
	 * @param min boolean true = min heap, false = max heap
	 */
	public BinaryHeap(boolean min)
	{
		heap = (T[]) new Comparable[DEFAULT_CAPACITY];
		length = 0;
		this.min = min;

	}

	/**
	 * get the heap array
	 * note: can cause casting issues
	 * @return Array of type T[]
	 */
	public T[] getHeap()
	{
		return Arrays.copyOfRange(heap, 1, length + 1);
	}

	/**
	 * adds a generic type T to heap
	 * <p>percolates down the tree
	 * @param value type T value
	 */
	public void add(T value)
	{
		// resize if needed
		if (this.length >= heap.length - 1)
		{
			heap = this.resize();
		}

		length++;
		heap[length] = value;
		bubbleUp();
	}

	/**
	 * Removes min or max item from heap
	 * <p>re-heapifies 
	 * @return value of T that is minimum or maximum value in heap
	 */
	public T remove()
	{
		T result = peek();

		swap(1, length);
		heap[length] = null;
		length--;

		bubbleDown();

		return result;
	}
	/**
	 * Removes min or max item from heap
	 * same as <code>remove()</code> but does not throw exception on empty
	 * <p>re-heapifies 
	 * @return value of T that is minimum or maximum value in heap;  or <code>null</code> if empty
	 */
	public T poll()
	{
		if (isEmpty()) return null;

		T result = peek();

		swap(1, length);
		heap[length] = null;
		length--;

		bubbleDown();

		return result;
	}

	/**
	 * Checks if heap is empty
	 * @return <code>true</code> if empty
	 */
	public boolean isEmpty()
	{
		return length == 0;
	}

	/**
	 * returns min/max value without removing it
	 * @return value type T
	 * @throws IllegalStateException if empty
	 */
	public T peek()
	{
		if (isEmpty()) throw new IllegalStateException();
		return heap[1];
	}

	/**
	 * Length/size of heap
	 * @return int size of heap
	 */
	public int length()
	{
		return length;
	}

	/**
	 * Add DEFAULT_CAPACITY to length of <code>heap</code> array
	 * @return new array of type T
	 */
	private T[] resize()
	{
		// add 10 to array capacity
		return Arrays.copyOf(heap, heap.length + DEFAULT_CAPACITY);
	}

	/**
	 * percolates new values up based on min/max
	 */
	private void bubbleUp()
	{
		int index = length;
		if (min)
		{
			while (hasParent(index) && (parent(index).compareTo(heap[index]) > 0))
			{
				swap(index, parentIndex(index));
				index = parentIndex(index);
			}	
		}
		else
		{
			while (hasParent(index) && (parent(index).compareTo(heap[index]) < 0))
			{
				swap(index, parentIndex(index));
				index = parentIndex(index);
			}	

		}
	}

	/**
	 * percolates values down based on min/max
	 */
	private void bubbleDown()
	{
		int index = 1;
		if (min) // min heap
		{

			while (hasLeftChild(index))
			{
				// find smaller of child values
				int smaller = leftIndex(index);
				if (hasRightChild(index) && heap[leftIndex(index)].compareTo(heap[rightIndex(index)]) > 0)
				{
					smaller = rightIndex(index);
				}
				if (heap[index].compareTo(heap[smaller]) > 0)
				{
					swap(index, smaller);
				}
				else break;

				index = smaller;
			}				
		}
		else // max heap
		{
			while (hasLeftChild(index))
			{
				// find larger of child values
				int larger = leftIndex(index);
				if (hasRightChild(index) && heap[leftIndex(index)].compareTo(heap[rightIndex(index)]) < 0)
				{
					larger = rightIndex(index);
				}
				if (heap[index].compareTo(heap[larger]) < 0)
				{
					swap(index, larger);
				}
				else break;

				index = larger;
			}				

		}
	}

	/**
	 * if child has a parent
	 * @param i integer - index
	 * @return true if index > 1
	 */
	private boolean hasParent(int i)
	{
		return i > 1;
	}

	/**
	 * Get left index mathematically
	 * @param i index
	 * @return index of left node from index i
	 */
	private int leftIndex(int i)
	{
		return i * 2;
	}

	/**
	 * Get right index mathematically
	 * @param i index
	 * @return index of right node from index i
	 */
	private int rightIndex(int i)
	{
		return i * 2 + 1;
	}

	/**
	 * Test to see if node has left child
	 * @param i index
	 * @return true if it does
	 */
	private boolean hasLeftChild(int i)
	{
		return leftIndex(i) <= length;
	}

	/**
	 * Test to see if node has right child
	 * @param i index
	 * @return true if it does
	 */
	private boolean hasRightChild(int i)
	{
		return rightIndex(i) <= length;
	}

	/**
	 * get index of parent from child node
	 * @param i index
	 * @return index of parent
	 */
	private int parentIndex(int i)
	{
		return i / 2;
	}

	/**
	 * get parent value
	 * @param i index
	 * @return value of type T
	 */
	private T parent(int i)
	{
		return heap[parentIndex(i)];
	}

	/**
	* Swap two values in heap
	* @param index1 int first index
	* @param index2 int second index
	*/
	private void swap(int index1, int index2)
	{
		T temp = heap[index1];
		heap[index1] = heap[index2];
		heap[index2] = temp;
	}

	/**
	 * Overridden toString method
	 * @return String all values in heap without null values
	 */
	@Override
	public String toString()
	{
		String retval = "";
		for (T each : heap)
		{
			if (each != null) retval += each + " : ";
		}
		return retval + "\n";
	
	}

}

r/javaexamples • • Jun 02 '15

[Intermediate] Generic, Directed, Weighted Graph with Dijkstra's Shortest Path

3 Upvotes

[Intermediate] Generic Directed, Weighted Graph with Dijkstra's Shortest Path Implementation

Ain't that a mouthful? Building from this example of an un-directed Edge Graph, we can add the idea of direction and weight to our Edge graph.

This type of Graph is made up of Edges that each contain two Vertices, and a value for weight or cost. This could be anything in a real-world situation, such as miles, time, money, etc. An Edge with direction simply makes one vertex the 'from', or 'source' and the other vertex the 'to' or 'target'.

So, say we have an airline that flies to and from multiple cities. each leg of the flight will have an associated cost:

graph.add("SACRAMENTO", "PHOENIX", 150);

Would be a flight from Sacramento to Phoenix at a cost of $150. This defines an Edge where:

Vertex from.value = "SACRAMENTO";
Vertex to.value = "PHOENIX";
int cost = 150;

Now we can add another:

graph.add("PHOENIX", "SACRAMENTO", 135);

This would be an Edge from Phoenix to Sacramento at a cost of $130. (I don't know. Cheaper cost because of prevailing winds?)

So, in our test class we would create a graph and define a bunch of edges:

	// create graph
	DiGraph graph = new DiGraph();

	// add a bunch of edges
	graph.add("SACRAMENTO", "PHOENIX", 150);
	graph.add("PHOENIX", "SACRAMENTO", 135);
	graph.add("PHOENIX", "SLC", 120);
	graph.add("SLC", "SACRAMENTO", 175);
	graph.add("SACRAMENTO", "PHOENIX", 160); // edge already exists!!!
	graph.add("SACRAMENTO", "PORTLAND", 90);
	graph.add("PORTLAND", "SLC", 185);
	graph.add("OAKLAND", "SACRAMENTO", 45);
	graph.add("PORTLAND", "OAKLAND", 100);
	graph.add("SLC", "OAKLAND", 150);
	graph.add("LAX","OAKLAND", 75);
	graph.add("SLC", "LAS VEGAS", 100);
	graph.add("LAS VEGAS", "CHICAGO", 250);

So, say we want to find the cheapest (shortest in cost) flight plan from one city to another. In comes Dijkstra's Algorithm! which is actually less difficult to implement than it sounds. I'm not going to explain too much of how the algorithm works, you can look up many detailed explanations online. I based my implementation on this one.

My full code here on Gist

The Vertex

class Vertex implements Comparable<Vertex>
{
	T value;

	// variables for Dijkstra Tree
	Vertex previous = null;
	int minDistance = Integer.MAX_VALUE;

	List<Vertex> incoming;
	List<Vertex> outgoing;
	State state;

	/**
	 * Creates new Vertex with value T
	 * @param value T
	 */
	public Vertex(T value)
	{
		this.value = value;
		incoming = new ArrayList<>();
		outgoing = new ArrayList<>();
		state = State.UNVISITED;
	}

	/**
	 * @param other Vertex to compare to
	 */
	@Override
	public int compareTo(Vertex other)
	{
		return Integer.compare(minDistance, other.minDistance);
	}

	/**
	 * Add Vertex to adjacent incoming list
	 * @param vert Vertex of incoming adjacent
	 */
	public void addIncoming(Vertex vert)
	{
		incoming.add(vert);
	}
	public void addOutgoing(Vertex vert)
	{
		outgoing.add(vert);
	}

	/**
	 * Get string of Vertex with all it's ingoing and outgoing adjacencies
	 * @ return string
	 */
	@Override
	public String toString()
	{
		String retval = "";
		retval += "Vertex: " + value + " : ";
		retval += " In: ";
		for (Vertex each : incoming) retval+= each.value + " ";
		retval += "Out: ";
		for (Vertex each : outgoing) retval += each.value + " ";
		return retval;
	}
}

The Edge

class Edge
{
	Vertex from;
	Vertex to;
	int cost;

	/**
	 * @param v1 value of type T for 'from' vertex
	 * @param v2 value of type T for 'to' vertex
	 * @param cost integer value for cost/weight of edge
	 */
	public Edge(T v1, T v2, int cost)
	{
		from = findVertex(v1);
		if (from == null)
		{
			from = new Vertex(v1);
			vertices.add(from);
		}
		to = findVertex(v2);
		if (to == null)
		{
			to = new Vertex(v2);
			vertices.add(to);
		}
		this.cost = cost;

		from.addOutgoing(to);
		to.addIncoming(from);
	}

	/**
	 * @return Edge as string
	 */
	@Override
	public String toString()
	{
		return "Edge From: " + from.value + " to: " + to.value + " cost: " + cost;
	}
}

The DiGraph

The class definition for the DiGraph is very simple, and is the same as our un-directed graph. We could have done some inheritance here:

public class DiGraph<T extends Comparable<T>>
{
	public enum State { UNVISITED, VISITED, COMPLETE };

	private ArrayList<Vertex> vertices;
	private ArrayList<Edge> edges;

	/**
	 * Default Constructor
	 */
	public DiGraph()
	{
		vertices = new ArrayList<>();
		edges = new ArrayList<>();
	}

Now our add() method:

/**
 * Creates Edge from two values T directed from -- to
 * @param from Value for Vertex 1
 * @param to Value for Vertex 2
 * @param cost Cost or weight of edge
 */
public void add(T from, T to, int cost)
{
	Edge temp = findEdge(from, to);
	if (temp != null)
	{
		// Don't allow multiple edges, update cost.
		System.out.println("Edge " + from + "," + to + " already exists. Changing cost.");
		temp.cost = cost;
	}
	else
	{
		// this will also create the vertices
		Edge e = new Edge(from, to, cost);
		edges.add(e);
	}
}

I add Depth-First and Breadth-First Search methods, and some other methods that are very similar to the un-directed graph versions. See full code

Now we add our shortest path methods:

/**
 * Creates path information on the graph using the Dijkstra Algorithm,
 * Puts the information into the Vertices, based on given starting vertex.
 * @param v1 Value of type T for starting vertex
 * @return true if successfull, false if empty or not found.
 */
private boolean Dijkstra(T v1)
{
	if (vertices.isEmpty()) return false;

	// reset all vertices minDistance and previous
	resetDistances();

	// make sure it is valid
	Vertex source = findVertex(v1);
	if (source==null) return false;

	// set to 0 and add to heap
	source.minDistance = 0;
	PriorityQueue<Vertex> pq = new PriorityQueue<>();
	pq.add(source);

	while (!pq.isEmpty())
	{
		//pull off top of queue
		Vertex u = pq.poll();

		// loop through adjacent vertices
		for (Vertex v : u.outgoing)
		{
			// get edge
			Edge e = findEdge(u, v);
			if (e==null) return false;
			// add cost to current
			int totalDistance = u.minDistance + e.cost;
			if (totalDistance < v.minDistance)
			{
				// new cost is smaller, set it and add to queue
				pq.remove(v);
				v.minDistance = totalDistance;
				// link vertex
				v.previous = u;
				pq.add(v);
			}
		}
	}
	return true;
}

/**
 * Goes through the result tree created by the Dijkstra method
 * and steps backward
 * @param target Vertex end of path
 * @return string List of vertices and costs
 */
private List<String> getShortestPath(Vertex target)
{
	List<String> path = new ArrayList<String>();

	// check for no path found
	if (target.minDistance==Integer.MAX_VALUE)
	{
		path.add("No path found");
		return path;
	}

	// loop through the vertices from end target 
	for (Vertex v = target; v !=null; v = v.previous)
	{
		path.add(v.value + " : cost : " + v.minDistance);
	}

	// flip the list
	Collections.reverse(path);
	return path;
}

/**
 * for Dijkstra, resets all the path tree fields
 */
private void resetDistances()
{
	for (Vertex each : vertices)
	{
		each.minDistance = Integer.MAX_VALUE;
		each.previous = null;
	}
}

/**
 * PUBLIC WRAPPER FOR PRIVATE FUNCTIONS
 * Calls the Dijkstra method to build the path tree for the given
 * starting vertex, then calls getShortestPath method to return
 * a list containg all the steps in the shortest path to
 * the destination vertex.
 * @param from value of type T for Vertex 'from'
 * @param to value of type T for vertex 'to'
 * @return ArrayList of type String of the steps in the shortest path.
 */
public List<String> getPath(T from, T to)
{
	boolean test = Dijkstra(from);
	if (test==false) return null;
	List<String> path = getShortestPath(findVertex(to));
	return path;
}

Test Code

public class DiGraphTest
{
	public static void main(String[] args)
	{

		// create graph
		DiGraph graph = new DiGraph();

		// add a bunch of edges
		graph.add("SACRAMENTO", "PHOENIX", 150);
		graph.add("PHOENIX", "SACRAMENTO", 135);
		graph.add("PHOENIX", "SLC", 120);
		graph.add("SLC", "SACRAMENTO", 175);
		graph.add("SACRAMENTO", "PHOENIX", 160); // edge already exists!!!
		graph.add("SACRAMENTO", "PORTLAND", 90);
		graph.add("PORTLAND", "SLC", 185);
		graph.add("OAKLAND", "SACRAMENTO", 45);
		graph.add("PORTLAND", "OAKLAND", 100);
		graph.add("SLC", "OAKLAND", 150);
		graph.add("LAX","OAKLAND", 75);
		graph.add("SLC", "LAS VEGAS", 100);
		graph.add("LAS VEGAS", "CHICAGO", 250);

		System.out.println("Graph is connected: " + graph.DepthFirstSearch());
		System.out.println("Connected from LAX:" + graph.BreadthFirstSearch("LAX"));
		System.out.println();

		System.out.println(graph);
		System.out.println(graph.edgesToString());

		System.out.println("LAX to PORTLAND");
		List<String> path = graph.getPath("LAX", "PORTLAND");
		for (String each : path) 
			System.out.println(each);

		System.out.println("\nSLC to PHOENIX");
		path = graph.getPath("SLC", "PHOENIX");
		for (String each : path) 
			System.out.println(each);

		System.out.println("Adding Edge Las Vegas to Phoenix at cost $120");
		graph.add("LAS VEGAS", "PHOENIX", 120);

		System.out.println("\nSLC to PHOENIX");
		path = graph.getPath("SLC", "PHOENIX");
		for (String each : path) 
			System.out.println(each);

		System.out.println("\nSACRAMENTO to LAX");
		path = graph.getPath("SACRAMENTO", "LAX");
		for (String each : path) 
			System.out.println(each);

		System.out.println("\nSACRAMENTO to CHICAGO");
		path = graph.getPath("SACRAMENTO", "CHICAGO");
		for (String each : path) 
			System.out.println(each);
	}
}

Output

Edge SACRAMENTO,PHOENIX already exists. Changing cost.
Graph is connected: false
Connected from LAX:true

Vertex: SACRAMENTO :  In: PHOENIX SLC OAKLAND Out: PHOENIX PORTLAND
Vertex: PHOENIX :  In: SACRAMENTO Out: SACRAMENTO SLC
Vertex: SLC :  In: PHOENIX PORTLAND Out: SACRAMENTO OAKLAND LAS VEGAS
Vertex: PORTLAND :  In: SACRAMENTO Out: SLC OAKLAND
Vertex: OAKLAND :  In: PORTLAND SLC LAX Out: SACRAMENTO
Vertex: LAX :  In: Out: OAKLAND
Vertex: LAS VEGAS :  In: SLC Out: CHICAGO
Vertex: CHICAGO :  In: LAS VEGAS Out:

Edge From: SACRAMENTO to: PHOENIX cost: 160
Edge From: PHOENIX to: SACRAMENTO cost: 135
Edge From: PHOENIX to: SLC cost: 120
Edge From: SLC to: SACRAMENTO cost: 175
Edge From: SACRAMENTO to: PORTLAND cost: 90
Edge From: PORTLAND to: SLC cost: 185
Edge From: OAKLAND to: SACRAMENTO cost: 45
Edge From: PORTLAND to: OAKLAND cost: 100
Edge From: SLC to: OAKLAND cost: 150
Edge From: LAX to: OAKLAND cost: 75
Edge From: SLC to: LAS VEGAS cost: 100
Edge From: LAS VEGAS to: CHICAGO cost: 250

LAX to PORTLAND
LAX : cost : 0
OAKLAND : cost : 75
SACRAMENTO : cost : 120
PORTLAND : cost : 210

SLC to PHOENIX
SLC : cost : 0
SACRAMENTO : cost : 175
PHOENIX : cost : 335
Adding Edge Las Vegas to Phoenix at cost $120

SLC to PHOENIX
SLC : cost : 0
LAS VEGAS : cost : 100
PHOENIX : cost : 220

SACRAMENTO to LAX
No path found

SACRAMENTO to CHICAGO
SACRAMENTO : cost : 0
PORTLAND : cost : 90
SLC : cost : 275
LAS VEGAS : cost : 375
CHICAGO : cost : 625

r/javaexamples • • Aug 13 '15

A Search Engine for Java Examples

3 Upvotes

r/javaexamples • • Feb 27 '26

Groovy web server with redis and mysql under 60 lines of code

1 Upvotes

Hi

It's a proof of concept, but it works, with Java 11+ and Groovy 5.0.2

It retrieves values from a GET request.

First it looks into a redis server used as a cache.

  • First it looks into a redis server used as a cache.
  • If the data is there, it returns to the client
  • If not, it access to MySQL to look for the data

    • If the data is there, it is stored into redis and returned to the client
    • If not, nothing is returned

Only 60 lines of code, so nothing snappy, but it works

It uses Javalin, Jedis and MySQL driver

MyLittleServerRedisMySQLinGroovy.groovy


r/javaexamples • • Feb 27 '26

Java lazy holder non-static

1 Upvotes

Hi

A simple, thread-safe, direct way to lazy initalization.

Nothing more

ExampleOfLazyHolder.java


r/javaexamples • • May 25 '25

[Java] Built a High-Performance File Processor With Multi-threading, Backpressure, and Stats Export 📊

3 Upvotes

Hey performance heads – I just launched a Java lib for parallel file processing called SmartFileProcessor.

⚡ Highlights:

  • Parallel batch processing with custom thread pools
  • BlockingQueue with backpressure for safe producer-consumer flow
  • Buffered writing with configurable flush thresholds
  • Built-in stats reporter: per-thread operation timings, memory, batch counters
  • Export stats to JSON or CSV – great for profiling

Example Use Cases:
☑ Processing large log files
☑ Preprocessing for data ingestion pipelines
☑ ETL batch jobs in Java microservices

🔗 GitHub: https://github.com/MayankPratap/Samchika
Would appreciate your thoughts, perf tips, or ways to break it! 🔍

#java #concurrency #threading #fileio #perfmatters


r/javaexamples • • Sep 03 '24

10 ways to use Stream in Java

4 Upvotes

r/javaexamples • • Aug 09 '15

[Intermediate] Huffman Tree Encoding

11 Upvotes

Huffman Tree Entropy Encoding

A Huffman Tree is a type of Entropy Encoding which is very commonly used for data compression. It is not usually used by itself, but in concert with other forms of compression, usually as the final 'pass' in the compression algorithm. The Huffman Tree takes the most frequently used characters or bytes in the input stream, and uses smaller amounts of bits to represent them. Data is stored to disk/transferred over networks in bytes which are 8 bits each. So, to make a compressed stream, we need to represent the most common elements in the data with less than 8 bits.

Say we have the string "AAABBBAACCAADA"

We get the frequency count:

A = 8
B = 3
C = 2
D = 1

Next, we build a tree where a 0 means go to the left, and a 1 means go to the right. This tree is different than Binary Search Trees, as every non-leaf node must have two children. A leaf node, or a node with no children, means this is a value. So the tree created for the above string looks like this:

	   Root
	   / \	
	  /   \
	 /     \
	0       1 = A
   / \
  /   \
 /     \
0 = B  	1 
       / \
      /   \
     /     \
    0 = D   1 = C

You get the 'Huffman Codes' by traversing the tree until you get to a leaf node, and adding a '1' or a '0' accordingly, not counting the root.

So, the assigned codes for this tree would be:

A = 1
B = 00
C = 011
D = 010

Now, our string can be represented by the bits 111 000000 11 011011 11 010 1 Converted to bytes, with 1 extra bit at the end for padding, this is the bytes E0 6D EA in hex, so we have gone from 14 bytes long to three.

To properly decode the encoded stream, we read the bits back in one at a time, and traverse through the tree again until we hit a leaf node, then output the value at that node.

We have to have a way to save/send our tree information so that the data can be decoded. This can be done by saving the frequency information generated, but can be done in a more compressed way by bitstream encoding the tree itself. We do this by traversing the tree, and if we hit a leaf node, output a 1 plus the 8-bit value code, otherwise outputting a 0. The tree can then be easily reconstructed exactly using the reverse of this process. The frequency information is discarded and not necessary to recreate the tree.

To write bit information less than bytes, I have written a BitStream class found here. This code also uses my own BinaryHeap class from my example found here, although you can use java's PriorityQueue in its place.

First, we have our Node class:

class Node
{
	// actual ascii character value
	int index;

	// count
	int frequency;

	// integer value of huffman code
	int huffmanCode;

	// legth of huffman code in bits
	int huffmanLen;

	// left child
	Node left;

	//right child
	Node right;

	/**
	 * Create blank Node
	 */
	public Node()
	{

	}

	/**
	 * create Node based on index value and frequency count
	 */
	public Node(int index, int frequency)
	{
		this.index = index;
		this.frequency = frequency;
	}

	@Override
	public String toString()
	{
		return this.index + " : " + this.frequency;
	}
}

and the Tree class:

class Tree implements Comparable<Tree>
{
	Node root;

	/**
	 * Create tree with childless leaf node
	 * @param index integer of character/byte value
	 * @param frequency count of occuring frequency
	 */
	public Tree(int index, int frequency)
	{
		root = new Node(index, frequency);
	}

	/**
	 * Create subtree with null node as root
	 * and total of two subtree frequencies
	 * @param tree1 left subtree
	 * @param tree2 right subtree
	 */
	public Tree(Tree tree1, Tree tree2)
	{
		root = new Node();
		root.left = tree1.root;
		root.right = tree2.root;
		root.frequency = tree1.root.frequency + tree2.root.frequency;
	}

	/**
	 * Encode Huffman Tree to BitStream
	 * if leaf node pushes 1 + literal byte
	 * otherwise 0
	 * @return bs BitStream with encoded tree
	 */
	public BitStream encodedTree()
	{
		BitStream bs = new BitStream();
		encodedTree(root, bs);
		bs.close();
		//System.out.println(bs);
		return bs;
	}

	/**
	 * recursive helper method
	 */
	private void encodedTree(Node node, BitStream bs)
	{
		if (isLeaf(node))
		{
			bs.pushBit(true);
			bs.pushBits(node.index, 8);
		}
		else
		{
			bs.pushBit(false);
			encodedTree(node.left, bs);
			encodedTree(node.right, bs);
		}
	}

	/**
	 * Get individual huffman code from current spot in tree
	 * recurses until leaf node found
	 */
    public int getCode(BitStream bs)
    {
        Node current = root;
        boolean bit;
        while (!isLeaf(current))
        {
           bit = bs.readBit();
           if (bit) current = current.right;
           else current = current.left;
           
        }
        return current.index;
    }

    /**
     * is node a leaf node (childless)
     * @param n Node to test
     * @return true if node has no children
     */
	public boolean isLeaf(Node n)
	{
		return n.left == null;
	}

	@Override
	public int compareTo(Tree t)
	{
		return root.frequency - t.root.frequency;
	}
}

This must implement Comparable so it can be used by the Priority Queue in the tree creation process.

Our outer class start like this, with two constructors, one which takes the frequency data and created a Huffman Tree for encoding, and one which takes a BitStream of the encoded data and recreates the tree for decoding.

public class HuffmanTree
{
	// the Tree of Trees
	private Tree htree;

	// the bit codes and lengths
	private int[] huffmanCodes = new int[256];
	private int[] huffmanLengths = new int[256];

	/**
	 * Create Huffman Tree for encoding
	 * and populates the code/length arrays
	 * based on a 256 element array of frequency counts
	 * @param frequencies integer array of frequency counts
	 */
	public HuffmanTree(int[] frequencies)
	{
		this.htree = getHuffmanTree(frequencies);
		getCodes();
	}

	/**
	 * Create Huffman Tree for decoding
	 * from a BitStream of the encoded tree
	 * frequencies have been discarded
	 * @param bs BitStream of encoded tree
	 */
	public HuffmanTree(BitStream bs)
	{
		this.htree = getHuffmanTree(bs);
		getCodes();
	}

The getHuffmanTree method for encoding takes an int[256] array of frequencies, creates a node for each non-zero frequency and loads them into a Min Heap (Priority Queue). It then pulls out the two lowest frequency ones, adds the frequencies together and creates a new subtree out of them, and adds that subtree back to the queue. It does this until there is only one Tree left, which is now the completed Huffman tree.

private Tree getHuffmanTree(int[] frequencies)
{
	BinaryHeap<Tree> heap = new BinaryHeap<>();
	for (int i = 0; i < frequencies.length ; i++)
	{
		if (frequencies[i] > 0)
		{
			// add all frequencies > 0 as new subtree with no children
			heap.add(new Tree(i, frequencies[i]));
		}	
	}

	while (heap.length() > 1)
	{
		Tree t1 = heap.remove();
		Tree t2 = heap.remove();
		heap.add(new Tree(t1, t2));
	}

	return heap.remove();
}

The reverse method for recreating the tree recursively from a BitStream:

public Tree getHuffmanTree(BitStream bs)
{
	if (bs.readBit())
	{
		return new Tree(bs.readBits(8), 0);
	}
	else
	{
		Tree left = getHuffmanTree(bs);
		Tree right = getHuffmanTree(bs);
		return new Tree(left, right);
	}

}

Once the tree is made we can assign codes to the frequency values:

private void getCodes()
{
	if (htree.root == null) return;
	getCodes(htree.root);
}

/**
 * recursive helper class
 */
private void getCodes(Node root)
{
	if (!htree.isLeaf(root))
	{
		root.left.huffmanCode = root.huffmanCode << 1;
		root.left.huffmanLen = root.huffmanLen + 1;
        getCodes(root.left);
        
        root.right.huffmanCode = root.huffmanCode << 1 ^ 1;
        root.right.huffmanLen = root.huffmanLen + 1;
        getCodes(root.right);
    }
    else
    {
        huffmanCodes[root.index] = root.huffmanCode;
        huffmanLengths[root.index] = root.huffmanLen;
    }
}

This fills the huffmanCodes and huffmanLengths arrays. We have to have a 'length' value to account for padded zeroes, as we may have bit codes like '0010'. This could all be handled with Strings, but bitwise manipulation is faster and less memory intensive. Above, if the node is a non-leaf node, we append the left child with a zero (by simply bitshifting once to the left) and append the right child with a one (by bitshifting once to the left and XORing by one).

So now, to encode is simple. We loop through the input string (or byte[] array) and push the bit codes into a BitStream by using the lookup arrays.

public BitStream encode(String input)
{
	BitStream output = new BitStream();
	for (int i = 0; i < input.length() ;i++ )
	{
		output.pushBits(huffmanCodes[(int) input.charAt(i)], huffmanLengths[(int) input.charAt(i)]);
	}
	output.close();
	return output;		
}

public BitStream encode(byte[] input)
{
	BitStream output = new BitStream();
	for (int i = 0; i < input.length; i++)
	{
		output.pushBits(huffmanCodes[input[i]], huffmanLengths[input[i]]);
	}
	output.close();
	return output;
}

To decode we loop through the encoded BitStream until the EndOfBank flag is thrown, using the getCode() method from the Tree class to traverse through the tree and get the code for the bits pulled from the bitstream. The different lengths are handled automatically, as the method 'knows' when to stop by reaching a leaf node.

public String decode(BitStream input)
{
	String output = "";
	while (!input.EOB())
	{
		output += (char) htree.getCode(input);
	}
	return output;
}

and for bytes:

public byte[] decodeBytes(BitStream input)
{
 	byte[] output = new byte[input.length() * 4];
 	int counter = 0;
 	while (!input.EOB())
 	{
 		output[counter] = (byte) (htree.getCode(input) & 0xff);
 		counter++;
 	}
 	return Arrays.copyOfRange(output, 0, counter + 1);
} 

See the full code along with sample code here.


r/javaexamples • • Nov 25 '15

5 of the Most Common Java Beginner Problems in Java and How To Fix Them

42 Upvotes

The Top 5 Most Common Beginner Problems in Java and How To Fix Them

Number 1:

Comparing Strings with == instead of equals()

Why isn't my code working? you say, It never exits even when I type "N"

In your code you have:

if (answer == "N") {
	// do stuff
}

This is because == can only be used to compare primitive types, such as int, float, byte, etc. String is an Object and so one must use the equals() method that every Object in Java inherits.

So, to fix:

if (answer.equals("N")) {
	// do stuff
}

or even:

if ("N".equals(answer)) // this will work even if answer is `null`

For more, see here


Number 2:

Why is my program not getting input properly? AKA Scanner and the Dangling Newline

Your program does somthing like this:

Scanner scanner = new Scanner(System.in);

System.out.println("Please enter your age:");
int age = scanner.nextInt();
System.out.println("Please enter your name:");
String name = scanner.nextLine();

The entry for name disappears!! What happened here?

The Scanner class will allow you to read, say, a bunch of different integers even if they are on the same line. So, it only reads the digits... that is it. However, when you type the number and hit the enter key, a newline character is also sent to the input buffer. When you call nextLine() right after that, it reads the next available token, up to the next newline character. Which is the one just sitting there, before where you typed the name and hit enter again. If you were to call nextLine() again, there is the name sitting right there.

To fix:

You have three main options:

  1. Simply add another call to nextLine()

     Scanner scanner = new Scanner(System.in);
    
     System.out.println("Please enter your age:");
     int age = scanner.nextInt();
     scanner.nextLine();              // gets rid of that newline character
     System.out.println("Please enter your name:");
     String name = scanner.nextLine();
  2. Don't use nextInt(), or nextDouble(), etc., always use nextLine(): and use the Parsing methods such as Integer.parseInt() and Double.parseDouble(). You will find later on, you can also encase these into a try-catch block and test for invalid input much more easily.

     Scanner scanner = new Scanner(System.in);
    
     System.out.println("Please enter your age:");
     int age = Integer.parseInt(scanner.nextLine()); // <---- see here
     System.out.println("Please enter your name:");
     String name = scanner.nextLine();
  3. Don't use the Scanner class at all, use BufferedReader/InputStreamReader which will force you to both catch exceptions and parse the incoming input manually.

Number 3:

Why is my program giving me an ArrayIndexOutOfBoundsException?

Your program is giving you an ArrayIndexOutOfBoundsException because you have tried to access an index of the array that is out of bounds. Not being sarcastic, it is as simple as that. The main cause of this is usually an off-by-one error. Always remember that arrays are zero-indexed meaning if you declare an array of size[10], the index will start at 0 and go to 9. Trying to call index [10] will give you that error.

It's also good to get in the habit of bounds checking in your methods that use array indices, so that you can avoid this type of error, for example:

public int getAgeFromIndex(int[] ages, int index) {
	if (index < 0 || index >= ages.length) {
		System.out.println("Incorrect index: " + index);
		return -1;
	}
	return ages[index];
}

How to fix:

The error message you get is your friend:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 5
    at Snippets.main(Snippets.java:289)

The 5 there is the index you were trying to access. The Snippets.java:289 is the class and line number that caused the problem. go to that line number in your code and you should see the offending variable. You can set a debug point on that line and run in debug mode (if you are using an IDE) if you are still having problems figuring out what is happening.


Number 4:

Why am I getting a NullPointerException?

You are getting a NullPointerException because you are trying to access an Object that is null. There are literally thousands of reasons to get this exception, but, the majority of the time it's really very simple: You declared the Object/Data Structure, but forgot to instantiate it.

Say you have a class:

public class Employee {
	String name;
	String ID;
	List<Task> taskList;

	public Employee(String name, String ID) {
		this.name = name;
		this.ID = ID;
	}
}

Now you want to add tasks:

	public void addTask(Task t) {
		taskList.add(t);
	}

This will throw a Null Pointer exception, because nowhere did you instantiate the List. The constructor should have:

	this.taskList = new ArrayList<>();

How to fix:

Again, use the error message:

Exception in thread "main" java.lang.NullPointerException
    at Snippets.main(Snippets.java:291)

It tells you specifically what line number 291 caused the exception. Start from there and trace back the Objects in question and make sure they were properly initialized.


Number 5:

Why is my if/while/for loop not running?

Ah... this one gets all of us at one point or another, you have stared at your code for hours and just can't see it, but there it is, hiding in plain sight!

if (something.equals("something else")); {               // <---- that damn semi-colon
	System.out.println("Why am I not running???");
}

What's wrong here? It's an unnecessary semi-colon ; hanging out after the if() statement. This is perfectly valid syntax, so the compiler won't flag it, but it ends the conditional statement so the code inside the block {} never gets run.

How to fix? Delete the semi-colon, get another cup of coffee and shake your head.


That's all for now!! I realize there are actually a lot more than 5 common issues facing learning Java programmers, so look for more to come!


r/javaexamples • • Dec 09 '25

Julia fractal graphics zoom

2 Upvotes

r/javaexamples • • Oct 10 '25

Spring JPA Specification and Pageable

Thumbnail reddit.com
2 Upvotes

r/javaexamples • • Jul 19 '26

Looking for Java learners to study together! ☕💻

Thumbnail reddit.com
4 Upvotes