Data Structures in pictures
Tuesday, August 1, 2023
Monday, July 31, 2023
Hashing
Hashing
Hash function
Hash function: h(key) = key % table_size
Table size: 5
Keys: 9, 7, 13, 11, 5, 8, 15
Hash table:
index | bucket
-------|--------
0 | []
1 | [9]
2 | [7]
3 | [11, 13]
4 | [5, 8, 15]
As you can see, the keys are hashed into the hash table using the hash function h(key) = key % table_size. The keys are then stored in linked lists in the hash table. The linked lists are used to store the keys that have the same hash value.
For example, the key 9 has a hash value of 1, so it is stored in the first bucket of the hash table. The keys 7 and 13 also have a hash value of 1, so they are stored in the same bucket.
The keys 5, 8, and 15 have a hash value of 4, so they are stored in the same bucket.
Difference between processing using hash function and hashtable (using separate chaining)
- Processing using hash function: In this approach, the keys are hashed into the hash table using the hash function. The keys are then stored in the hash table at the index of their hash value. This approach is simple and efficient, but it can lead to collisions, which occur when two or more keys have the same hash value.
- Hashtable (using separate chaining): In this approach, the keys are hashed into the hash table using the hash function. The keys are then stored in linked lists in the hash table. The linked lists are used to store the keys that have the same hash value. This approach does not suffer from collisions, but it is more complex and less efficient than the processing using hash function approach.
differences between the two approaches:
Thursday, July 20, 2023
Huffman coding-lossless data compression algorithm
- Huffman coding is a lossless data compression algorithm that assigns variable-length codes to input characters based on their frequency of occurrence.
- The most frequent characters are assigned the shortest codes, and the least frequent characters are assigned the longest codes.
- Huffman coding works by creating a binary tree of the characters, where the leaves of the tree represent the characters and the internal nodes represent the frequencies of the characters.
- The codes for the characters are then generated by traversing the tree from the root to the leaf node for the corresponding character.
- Huffman coding is a very efficient data compression algorithm, and it is often used to compress text files.
Here is an example of how Huffman coding works:
- Let's say we have the following string of characters: "abcabc".
- The frequencies of the characters in the string are: "a" = 2, "b" = 2, and "c" = 2.
- The binary tree for the characters would be as follows:
0
/ \
1 1
/ \ / \
0 0 1
- The codes for the characters would be: "a" = "0", "b" = "10", and "c" = "11".
===============
How Huffman Coding works?
Suppose the string below is to be sent over a network.
Each character occupies 8 bits. There are a total of 15 characters in the above string. Thus, a total of 8 * 15 = 120 bits are required to send this string.
Using the Huffman Coding technique, we can compress the string to a smaller size.
Huffman coding first creates a tree using the frequencies of the character and then generates code for each character.
Once the data is encoded, it has to be decoded. Decoding is done using the same tree.
Huffman Coding prevents any ambiguity in the decoding process using the concept of prefix code ie. a code associated with a character should not be present in the prefix of any other code. The tree created above helps in maintaining the property.
Huffman coding is done with the help of the following steps.
- Calculate the frequency of each character in the string.
- Sort the characters in increasing order of the frequency. These are stored in a priority queue Q.
- Make each unique character as a leaf node.
- Create an empty node z. Assign the minimum frequency to the left child of z and assign the second minimum frequency to the right child of z. Set the value of the z as the sum of the above two minimum frequencies.
- Remove these two minimum frequencies from Q and add the sum into the list of frequencies (* denote the internal nodes in the figure above).
- Insert node z into the tree.
- Repeat steps 3 to 5 for all the characters.
- For each non-leaf node, assign 0 to the left edge and 1 to the right edge.
For sending the above string over a network, we have to send the tree as well as the above compressed-code. The total size is given by the table below.
| Character | Frequency | Code | Size |
|---|---|---|---|
| A | 5 | 11 | 5*2 = 10 |
| B | 1 | 100 | 1*3 = 3 |
| C | 6 | 0 | 6*1 = 6 |
| D | 3 | 101 | 3*3 = 9 |
| 4 * 8 = 32 bits | 15 bits | 28 bits |
Without encoding, the total size of the string was 120 bits. After encoding the size is reduced to 32 + 15 + 28 = 75.
Decoding the code
For decoding the code, we can take the code and traverse through the tree to find the character.
Let 101 is to be decoded, we can traverse from the root as in the figure below.
Java Example
// Huffman Coding in Java
import java.util.PriorityQueue;
import java.util.Comparator;
class HuffmanNode {
int item;
char c;
HuffmanNode left;
HuffmanNode right;
}
// For comparing the nodes
class ImplementComparator implements Comparator<HuffmanNode> {
public int compare(HuffmanNode x, HuffmanNode y) {
return x.item - y.item;
}
}
// IMplementing the huffman algorithm
public class Huffman {
public static void printCode(HuffmanNode root, String s) {
if (root.left == null && root.right == null && Character.isLetter(root.c)) {
System.out.println(root.c + " | " + s);
return;
}
printCode(root.left, s + "0");
printCode(root.right, s + "1");
}
public static void main(String[] args) {
int n = 4;
char[] charArray = { 'A', 'B', 'C', 'D' };
int[] charfreq = { 5, 1, 6, 3 };
PriorityQueue<HuffmanNode> q = new PriorityQueue<HuffmanNode>(n, new ImplementComparator());
for (int i = 0; i < n; i++) {
HuffmanNode hn = new HuffmanNode();
hn.c = charArray[i];
hn.item = charfreq[i];
hn.left = null;
hn.right = null;
q.add(hn);
}
HuffmanNode root = null;
while (q.size() > 1) {
HuffmanNode x = q.peek();
q.poll();
HuffmanNode y = q.peek();
q.poll();
HuffmanNode f = new HuffmanNode();
f.item = x.item + y.item;
f.c = '-';
f.left = x;
f.right = y;
root = f;
q.add(f);
}
System.out.println(" Char | Huffman code ");
System.out.println("--------------------");
printCode(root, "");
}
}
// Huffman Coding in Java
import java.util.PriorityQueue;
import java.util.Comparator;
class HuffmanNode {
int item;
char c;
HuffmanNode left;
HuffmanNode right;
}
// For comparing the nodes
class ImplementComparator implements Comparator<HuffmanNode> {
public int compare(HuffmanNode x, HuffmanNode y) {
return x.item - y.item;
}
}
// IMplementing the huffman algorithm
public class Huffman {
public static void printCode(HuffmanNode root, String s) {
if (root.left == null && root.right == null && Character.isLetter(root.c)) {
System.out.println(root.c + " | " + s);
return;
}
printCode(root.left, s + "0");
printCode(root.right, s + "1");
}
public static void main(String[] args) {
int n = 4;
char[] charArray = { 'A', 'B', 'C', 'D' };
int[] charfreq = { 5, 1, 6, 3 };
PriorityQueue<HuffmanNode> q = new PriorityQueue<HuffmanNode>(n, new ImplementComparator());
for (int i = 0; i < n; i++) {
HuffmanNode hn = new HuffmanNode();
hn.c = charArray[i];
hn.item = charfreq[i];
hn.left = null;
hn.right = null;
q.add(hn);
}
HuffmanNode root = null;
while (q.size() > 1) {
HuffmanNode x = q.peek();
q.poll();
HuffmanNode y = q.peek();
q.poll();
HuffmanNode f = new HuffmanNode();
f.item = x.item + y.item;
f.c = '-';
f.left = x;
f.right = y;
root = f;
q.add(f);
}
System.out.println(" Char | Huffman code ");
System.out.println("--------------------");
printCode(root, "");
}
}
=============
Source programiz , Google
Dijkstra's algorithm with a graph
Dijkstra's algorithm with a graph
A
/ \
B C
/ \ / \
D E F
The weight of each edge is shown next to the edge. The goal is to find the shortest path from A to all other vertices.
Here are the steps on how to apply Dijkstra's algorithm on this graph:
- Initialize the distance of all vertices to infinity except A, which is initialized to 0.
Vertex | Distance from A
------- | --------
A | 0
B | INF
C | INF
D | INF
E | INF
F | INF
- Create a set of visited vertices and initialize it to be empty.
Visited vertices = {}
- Add A to the visited vertices set.
Visited vertices = {A}
- For each unvisited neighbor of A, calculate the tentative distance to that neighbor as the distance to A plus the weight of the edge between A and that neighbor.
Vertex | Distance from A
------- | --------
B | 2 (0 + 2)
C | 3 (0 + 3)
- If the tentative distance is less than the current distance to that neighbor, update the current distance to that neighbor.
Vertex | Distance from A
------- | --------
B | 2
C | 3
- Repeat steps 4 and 5 for all unvisited neighbors of A.
Vertex | Distance from A
------- | --------
B | 2
C | 3
D | 4 (2 + 2)
- Remove A from the unvisited vertices set.
Visited vertices = {B, C}
- Repeat steps 3 to 7 until all vertices have been visited.
Vertex | Distance from A
------- | --------
B | 2
C | 3
D | 4
E | 5 (4 + 1)
F | 6 (4 + 2)
The shortest path from A to each vertex is as follows:
- A to B: A-B
- A to C: A-C
- A to D: A-B-D
- A to E: A-B-D-E
- A to F: A-B-D-F
Tuesday, July 18, 2023
Java programs
OBJECT-ORIENTED CONCEPTS
This program
demonstrates the following object-oriented concepts:
- Classes: Classes
are the blueprints for objects. They define the attributes and methods of
an object.
- Objects: Objects
are instances of classes. They have the attributes and methods defined by
their class.
- Constructors: Constructors are special methods that are used
to initialize objects.
- Methods: Methods
are the actions that an object can perform.
- Inheritance: Inheritance is the ability of one class to
inherit the attributes and methods of another class.
- Polymorphism: Polymorphism is the ability of an object to take
on different forms.
// This program demonstrates the object-oriented concepts
class Person {
// The `name`
attribute is a string
String name;
// The `age`
attribute is an integer
int age;
// The `Person` constructor takes the name and age of the person as parameters
Person(String
name, int age) {
// The `this` keyword refers to the current object
this.name =
name;
this.age =
age;
}
// The `greet()` method
prints a greeting message
void greet() {
System.out.println("Hello, my name is " + name);
}
// The `getAge()`
method returns the age of the person
int getAge() {
return age;
}
// The `main()` method
is the entry point of the program
static void
main(String[] args) {
// Create two
objects of the `Person` class
Person
person1 = new Person("John Doe", 30);
Person
person2 = new Person("Jane Doe", 25);
// Call the
`greet()` method on each object
person1.greet();
person2.greet();
// Print the age
of each object
System.out.println("The age of person1 is: " +
person1.getAge());
System.out.println("The age of person2 is: " +
person2.getAge());
}
}
//Java program to perform all array operations
// This program first declares an array of
integers and then prints the array. It then finds the sum, average, maximum,
and minimum of the elements in the array. The program then sorts the array in
ascending order and reverses the array. Finally, the program prints the sorted
and reversed arrays.
import java.util.Arrays;
public class ArrayOperations {
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
// Print the array
System.out.println("The array is: " + Arrays.toString(arr));
// Find the sum of the elements in the array
int sum = 0;
for (int i = 0; i < arr.length; i++) {
sum += arr[i];
}
System.out.println("The sum of the elements in the array is: "
+ sum);
// Find the average of the elements in the array
double average = sum / arr.length;
System.out.println("The average of the elements in the array is:
" + average);
// Find the maximum element in the array
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
System.out.println("The maximum element in the array is: " +
max);
// Find the minimum element in the array
int min = arr[0];
for (int i = 1; i < arr.length; i++) {
if (arr[i] < min) {
min = arr[i];
}
}
System.out.println("The minimum element in the array is: " +
min);
// Sort the array in ascending order
Arrays.sort(arr);
System.out.println("The sorted array is: " +
Arrays.toString(arr));
// Reverse the array
int[] reversedArr = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
reversedArr[arr.length - 1 - i] = arr[i];
}
System.out.println("The reversed array is: " +
Arrays.toString(reversedArr));
}
}
Java program to perform all linked list operations.
This
program first declares a linked list of integers and then adds elements to the
linked list. It then prints the linked list, finds the size of the linked list,
finds the first element in the linked list, finds the last element in the
linked list, and removes the first element from the linked list. Finally, the
program removes the last element from the linked list and prints the linked
list again.
import java.util.LinkedList;
public class LinkedListOperations {
public static void main(String[] args) {
LinkedList<Integer> linkedList = new LinkedList<Integer>();
// Add elements to the linked list
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
linkedList.add(5);
// Print the linked list
System.out.println("The linked list is: " + linkedList);
// Find the size of the linked list
int size = linkedList.size();
System.out.println("The size of the linked list is: " + size);
// Find the first element in the linked list
Integer firstElement = linkedList.getFirst();
System.out.println("The first element in the linked list is: "
+ firstElement);
// Find the last element in the linked list
Integer lastElement = linkedList.getLast();
System.out.println("The last element in the linked list is: "
+ lastElement);
// Remove the first element from the linked list
linkedList.removeFirst();
System.out.println("The linked list after removing the first
element is: " + linkedList);
// Remove the last element from the linked list
linkedList.removeLast();
System.out.println("The linked list after removing the last element
is: " + linkedList);
}
}
Java program to create a singly linked list
class Node {
int data;
Node next;
Node(int data) {
this.data = data;
this.next = null;
}
}
class LinkedList {
Node head;
LinkedList() {
this.head = null;
}
void addNode(int data)
{
Node newNode = new
Node(data);
if (this.head == null) {
this.head = newNode;
} else {
Node currentNode =
this.head;
while
(currentNode.next != null) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
}
}
void printList() {
Node currentNode =
this.head;
while (currentNode !=
null) {
System.out.println(currentNode.data);
currentNode =
currentNode.next;
}
}
public static void
main(String[] args) {
LinkedList list = new
LinkedList();
list.addNode(1);
list.addNode(2);
list.addNode(3);
list.printList();
}
}
This program creates a
singly linked list and adds three nodes to it. The nodes contain the data 1, 2,
and 3. The program then prints the list, which should print the following
output:
1
2
3
Java program to create a doubly linked list
// A doubly linked list node
class Node {
int data;
Node prev;
Node next;
// Constructor
Node(int data) {
this.data = data;
this.prev = null;
this.next = null;
}
}
// A doubly linked list
class DoublyLinkedList {
// Head of the list
Node head;
// Tail of the list
Node tail;
// Constructor
DoublyLinkedList() {
this.head = null;
this.tail = null;
}
// Add a node to the list
void addNode(int data) {
// Create a new node
Node newNode = new Node(data);
// If the list is empty, make the new
node the head and tail
if (this.head == null) {
this.head = newNode;
this.tail = newNode;
} else {
// Otherwise, add the new node
after the tail
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
}
// Print the list
void printList() {
// Start at the head of the list
Node currentNode = this.head;
// Print the data in each node
while (currentNode != null) {
System.out.println(currentNode.data);
currentNode = currentNode.next;
}
}
public static void main(String[] args) {
// Create a doubly linked list
DoublyLinkedList list = new DoublyLinkedList();
// Add three nodes to the list
list.addNode(1);
list.addNode(2);
list.addNode(3);
// Print the list
list.printList();
}
}
This
program creates a doubly linked list and adds three nodes to it. The nodes
contain the data 1, 2, and 3. The program then prints the list, which should
print the following output:
123
Java program to create a circular linked list
// A node in a circular linked list
class Node {
int data;
Node next;
// Constructor
Node(int data) {
this.data = data;
this.next = null;
}
}
// A circular linked list
class CircularLinkedList {
// The head of the list
Node head;
// Constructor
CircularLinkedList() {
this.head = null;
}
// Add a node to the list
void addNode(int data) {
// Create a new node
Node newNode = new Node(data);
// If the list is empty, make the new
node the head and tail
if (this.head == null) {
this.head = newNode;
newNode.next = this.head;
} else {
// Otherwise, find the tail of the
list and add the new node after it
Node currentNode = this.head;
while (currentNode.next !=
this.head) {
currentNode = currentNode.next;
}
currentNode.next = newNode;
newNode.next = this.head;
}
}
// Print the list
void printList() {
// Start at the head of the list
Node currentNode = this.head;
// Print the data in each node
do {
System.out.println(currentNode.data);
currentNode = currentNode.next;
} while (currentNode != this.head);
}
public static void main(String[] args) {
// Create a circular linked list
CircularLinkedList list = new CircularLinkedList();
// Add three nodes to the list
list.addNode(1);
list.addNode(2);
list.addNode(3);
// Print the list
list.printList();
}
}
The do-while loop in
the printList() method
ensures that we print the data in all the nodes in the list, even the last
node, which points back to the head.
Java program to perform stack and queue operations.
This program first declares a stack and a queue
of integers. It then pushes and enqueues elements into the stack and queue,
respectively. The program then prints the stack and queue, pops and dequeues
elements from the stack and queue, respectively, and checks if the stack and
queue are empty.
import java.util.Stack;
import java.util.Queue;
public class StackQueueOperations {
public static void main(String[] args) {
// Create a stack
Stack<Integer> stack = new Stack<Integer>();
// Push elements onto the stack
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
// Print the stack
System.out.println("The stack is: " + stack);
// Pop elements from the stack
Integer poppedElement = stack.pop();
System.out.println("The popped element is: " + poppedElement);
poppedElement = stack.pop();
System.out.println("The popped element is: " + poppedElement);
// Check if the stack is empty
boolean isEmpty = stack.isEmpty();
System.out.println("The stack is empty: " + isEmpty);
// Create a queue
Queue<Integer> queue = new LinkedList<Integer>();
// Enqueue elements into the queue
queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
// Print the queue
System.out.println("The
queue is: " + queue);
// Dequeue elements from the queue
Integer dequeuedElement =
queue.remove();
System.out.println("The dequeued element is: " +
dequeuedElement);
dequeuedElement =
queue.remove();
System.out.println("The
dequeued element is: " + dequeuedElement);
// Check if the queue is empty
isEmpty = queue.isEmpty();
System.out.println("The queue is empty: " + isEmpty);
}
}
Java program to perform priority queue operations.
This
program first declares a priority queue of integers. It then adds elements to
the priority queue, prints the priority queue, removes the element with the
highest priority, and checks if the priority queue is empty.
import
java.util.PriorityQueue;
public class PriorityQueueOperations {
public static void main(String[] args) {
// Create a priority queue
PriorityQueue<Integer> priorityQueue = new
PriorityQueue<Integer>();
// Add elements to the priority queue
priorityQueue.add(10);
priorityQueue.add(5);
priorityQueue.add(1);
priorityQueue.add(7);
priorityQueue.add(3);
// Print the priority queue
System.out.println("The priority queue is: " +
priorityQueue);
// Remove the element with the highest priority
Integer highestPriorityElement = priorityQueue.poll();
System.out.println("The element with the highest
priority is: " + highestPriorityElement);
// Check if the priority queue is empty
boolean isEmpty = priorityQueue.isEmpty();
System.out.println("The priority queue is empty: "
+ isEmpty);
}
}
Java program to reverse a linked list
public class
Linked_List {
static Node head;
static class Node {
int data;
Node next;
Node (int value) {
data = value;
next = null;
}
}
// display the list
static void printList(Node node) {
System.out.print("\n[");
//start from the beginning
while(node != null) {
System.out.print(" " +
node.data + " ");
node = node.next;
}
System.out.print("]");
}
static Node reverseList(Node head) {
Node prev = null;
Node cur = head;
Node temp = null;
while (cur != null) {
temp = cur.next;
cur.next = prev;
prev = cur;
cur = temp;
}
head = prev;
return head;
}
public static void main(String args[]) {
Linked_List list = new Linked_List();
list.head = new Node(33);
list.head.next = new Node(50);
list.head.next.next = new Node(44);
list.head.next.next.next = new Node(22);
list.head.next.next.next.next = new
Node(12);
System.out.println("Linked List:
");
// print list
list.printList(head);
head = list.reverseList(head);
System.out.println("\nReversed
linked list ");
list.printList(head);
}
}
================
create a doubly linked list and print all the nodes present
in the list.
public class DoublyLinkedList {
//Represent a node of the doubly linked
list
class Node{
int data;
Node previous;
Node
next;
public Node(int data) {
this.data
= data;
}
}
//Represent the
head and tail of the doubly linked list
Node head, tail =
null;
//addNode() will
add a node to the list
public void
addNode(int data) {
//Create a new
node
Node newNode =
new Node(data);
//If list is
empty
if(head ==
null) {
//Both
head and tail will point to newNode
head =
tail = newNode;
//head's
previous will point to null
head.previous = null;
//tail's
next will point to null, as it is the last node of the list
tail.next
= null;
}
else {
//newNode
will be added after tail such that tail's next will point to newNode
tail.next
= newNode;
//newNode's previous will point to tail
newNode.previous = tail;
//newNode will become new tail
tail =
newNode;
//As it is last node, tail's next will point
to null
tail.next
= null;
}
}
//display() will
print out the nodes of the list
public void
display() {
//Node current
will point to head
Node current =
head;
if(head ==
null) {
System.out.println("List is empty");
return;
}
System.out.println("Nodes of doubly linked list: ");
while(current
!= null) {
//Prints
each node by incrementing the pointer.
System.out.print(current.data + " ");
current =
current.next;
}
}
public static void
main(String[] args) {
DoublyLinkedList dList = new DoublyLinkedList();
//Add nodes to
the list
dList.addNode(1);
dList.addNode(2);
dList.addNode(3);
dList.addNode(4);
dList.addNode(5);
//Displays the
nodes present in the list
dList.display();
}
}
==========================
Try Linked List here
https://www.w3schools.com/java/java_linkedlist.asp
==============
Java program that uses the Hashtable class:
import java.util.Hashtable;
public class HashtableDemo {
public static void main(String[] args) {
// Create a hashtable.
Hashtable<Integer, String> hashtable = new Hashtable<>();
// Add elements to the hashtable.
hashtable.put(1, "One");
hashtable.put(2, "Two");
hashtable.put(3, "Three");
// Get an element from the hashtable.
String value = hashtable.get(2);
System.out.println("The value for key 2 is: " + value);
// Iterate through the hashtable.
for (Integer key : hashtable.keySet()) {
String value1 = hashtable.get(key);
System.out.println("The value for key " + key + " is: " + value1);
}
}
}==================================================
Java program to implement Dijkstra's algorithm
import
java.util.*;
public
class Dijkstra {
static class Node {
int vertex;
int distance;
Node(int vertex, int distance) {
this.vertex = vertex;
this.distance = distance;
}
}
public static void main(String[] args) {
// Create a graph
Map<Integer, List<Node>>
graph = new HashMap<>();
graph.put(0, Arrays.asList(new Node(1,
10), new Node(2, 5)));
graph.put(1, Arrays.asList(new Node(2,
3)));
graph.put(2, Arrays.asList());
// Initialize the distances
int[] distances = new int[3];
Arrays.fill(distances,
Integer.MAX_VALUE);
// Set the distance of the source
vertex to 0
distances[0] = 0;
// Create a priority queue to store the
vertices
PriorityQueue<Node> pq = new
PriorityQueue<>((n1, n2) -> n1.distance - n2.distance);
pq.add(new Node(0, 0));
// While the priority queue is not
empty
while (!pq.isEmpty()) {
// Get the vertex with the minimum
distance
Node currentVertex = pq.poll();
// For each neighbor of the current
vertex
for (Node neighbor :
graph.get(currentVertex.vertex)) {
// If the distance to the
neighbor is less than the current distance
if (distances[neighbor.vertex]
> currentVertex.distance + neighbor.distance) {
// Update the distance to the
neighbor
distances[neighbor.vertex]
= currentVertex.distance + neighbor.distance;
// Add the neighbor to the
priority queue
pq.add(new
Node(neighbor.vertex, distances[neighbor.vertex]));
}
}
}
// Print the distances
System.out.println(Arrays.toString(distances));
}
}
The above program first creates a graph. The graph is a map of vertices to lists of neighbors. Each neighbor has a distance
associated with it.
The program then initializes the distances to all vertices to infinity. The
distance of the source vertex is set to 0.
The program then creates a priority queue to store the vertices. The priority queue
is sorted by the distance of each vertex.
The program then iterates through the priority queue. For each vertex in the
priority queue, the program iterates through its neighbors. If the distance to
a neighbor is less than the current distance, the program updates the distance
to the neighbor. The program then adds the neighbor to the priority queue. The
program continues iterating through the priority queue until the priority queue
is empty.
Finally, the program prints the distances.
Java program to implement static Huffman coding:
import
java.util.*;
public
class HuffmanCoding {
static class Node implements
Comparable<Node> {
int frequency;
char character;
Node left;
Node right;
Node(int frequency, char character) {
this.frequency = frequency;
this.character = character;
this.left = null;
this.right = null;
}
@Override
public int compareTo(Node other) {
return this.frequency -
other.frequency;
}
}
public static void main(String[] args) {
// Create a map of characters to
frequencies
Map<Character, Integer>
frequencies = new HashMap<>();
for (char c = 'a'; c <= 'z'; c++) {
frequencies.put(c, 0);
}
// Read the input text and update the
frequencies
Scanner scanner = new
Scanner(System.in);
while (scanner.hasNext()) {
char c = scanner.next().charAt(0);
frequencies.put(c,
frequencies.get(c) + 1);
}
// Create a priority queue to store the
nodes
PriorityQueue<Node> pq = new
PriorityQueue<>();
for (Character c :
frequencies.keySet()) {
Node node = new
Node(frequencies.get(c), c);
pq.add(node);
}
// While the priority queue is not empty
while (pq.size() > 1) {
// Get the two nodes with the
minimum frequencies
Node left = pq.poll();
Node right = pq.poll();
// Create a new node with the sum
of the frequencies of the two nodes
Node parent = new
Node(left.frequency + right.frequency, '\0');
// Add the new node to the priority
queue
parent.left = left;
parent.right = right;
pq.add(parent);
}
// Get the root of the Huffman tree
Node root = pq.poll();
// Create a map of characters to codes
Map<Character, String> codes =
new HashMap<>();
traverse(root, "", codes);
// Print the codes
for (Character c :
frequencies.keySet()) {
System.out.println(c + ":
" + codes.get(c));
}
}
private static void traverse(Node node,
String code, Map<Character, String> codes) {
if (node.character != '\0') {
codes.put(node.character, code);
} else {
traverse(node.left, code +
"0", codes);
traverse(node.right, code +
"1", codes);
}
}
}
The above program first creates a map of characters to frequencies. The program
then reads the input text and updates the frequencies.
The program then creates a priority queue to store the nodes. The priority queue is
sorted by the frequency of each node.
The program then iterates through the priority queue. For each node in the priority
queue, the program creates a new node with the sum of the frequencies of the
two nodes. The program then adds the new node to the priority queue.
The program continues iterating through the priority queue until the priority queue
is empty.
The program then gets the root of the Huffman tree and creates a map of characters
to codes. The program traverses the Huffman tree and stores the codes for each
character in the map. Finally, the program prints the codes.
===================
Subscribe to:
Posts (Atom)
-
PHP VS Python: PHP is based on object-oriented programming whereas Python is both object-oriented and procedure-oriented programming 1 . ...
-
4G and 5G are the two most recent generations of cellular network technology. 5G is the successor to 4G, and it offers a number of signific...
-
PHP VS Java PHP VS Java PHP is a server-side scripting language that is used to generate dynamic web page...
