Name: Muhammad Bilal
Roll no: FA21-BCS-110
DSA Lab Task
Submitted to
Sir Jazib E Nazar
Comsats University Islamabad,
Abbottabad Campus.
Max Heap
public class heap {
private int[] heap;
private int size;
private int capacity;
heap(int capacity) {
this.capacity = capacity;
this.heap = new int[capacity];
this.size = 0;
int getParentIndex(int index) {
return (index - 1) / 2;
int getLeftChildIndex(int index) {
return (2 * index) + 1;
int getRightChildIndex(int index) {
return (2 * index) + 2;
void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
void heapifyUp(int index) {
int parentIndex = getParentIndex(index);
while (index > 0 && heap[index] > heap[parentIndex]) {
swap(index, parentIndex);
index = parentIndex;
parentIndex = getParentIndex(index);
void heapifyDown(int index) {
int maxIndex = index;
int leftChildIndex = getLeftChildIndex(index);
int rightChildIndex = getRightChildIndex(index);
if (leftChildIndex < size && heap[leftChildIndex] > heap[maxIndex]) {
maxIndex = leftChildIndex;
if (rightChildIndex < size && heap[rightChildIndex] > heap[maxIndex]) {
maxIndex = rightChildIndex;
if (index != maxIndex) {
swap(index, maxIndex);
heapifyDown(maxIndex);
void insert(int value) {
if (size == capacity) {
System.out.println("Heap is full. Cannot insert more elements.");
return;
}
heap[size] = value;
size++;
heapifyUp(size - 1);
void buildMaxHeap(int[] array) {
if (array.length > capacity) {
System.out.println("Input array exceeds heap capacity.");
return;
size = array.length;
for (int i = 0; i < size; i++) {
heap[i] = array[i];
for (int i = (size / 2) - 1; i >= 0; i--) {
heapifyDown(i);
void printHeap() {
for (int i = 0; i < size; i++) {
System.out.print(heap[i] + " ");
System.out.println();
public static void main(String[] args) {
heap heap=new heap(10);
heap.insert(4);
heap.insert(10);
heap.insert(3);
heap.insert(5);
heap.insert(1);
System.out.println("Max Heap:");
heap.printHeap();
Min Heap
public class heap {
private int[] heap;
private int size;
private int capacity;
public heap(int capacity) {
this.capacity = capacity;
this.heap = new int[capacity];
this.size = 0;
private int getParentIndex(int index) {
return (index - 1) / 2;
private int getLeftChildIndex(int index) {
return (2 * index) + 1;
private int getRightChildIndex(int index) {
return (2 * index) + 2;
private void swap(int i, int j) {
int temp = heap[i];
heap[i] = heap[j];
heap[j] = temp;
private void heapifyUp(int index) {
int parentIndex = getParentIndex(index);
while (index > 0 && heap[index] < heap[parentIndex]) {
swap(index, parentIndex);
index = parentIndex;
parentIndex = getParentIndex(index);
private void heapifyDown(int index) {
int minIndex = index;
int leftChildIndex = getLeftChildIndex(index);
int rightChildIndex = getRightChildIndex(index);
if (leftChildIndex < size && heap[leftChildIndex] < heap[minIndex]) {
minIndex = leftChildIndex;
if (rightChildIndex < size && heap[rightChildIndex] < heap[minIndex]) {
minIndex = rightChildIndex;
if (index != minIndex) {
swap(index, minIndex);
heapifyDown(minIndex);
public void insert(int value) {
if (size == capacity) {
System.out.println("Heap is full. Cannot insert more elements.");
return;
heap[size] = value;
size++;
heapifyUp(size - 1);
public void buildMinHeap(int[] array) {
if (array.length > capacity) {
System.out.println("Input array exceeds heap capacity.");
return;
size = array.length;
for (int i = 0; i < size; i++) {
heap[i] = array[i];
for (int i = (size / 2) - 1; i >= 0; i--) {
heapifyDown(i);
public void printHeap() {
for (int i = 0; i < size; i++) {
System.out.print(heap[i] + " ");
System.out.println();
public static void main(String[] args) {
heap heap = new heap(10);
heap.insert(4);
heap.insert(10);
heap.insert(3);
heap.insert(5);
heap.insert(1);
System.out.println("Min Heap:");
heap.printHeap();
AVL
public class avl {
class Node {
int value;
Node left;
Node right;
int height;
Node(int value) {
this.value = value;
height = 1;
Node root;
int height(Node node) {
if (node == null) {
return 0;
return node.height;
int max(int a, int b) {
return (a > b) ? a : b;
Node rotateLeft(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = max(height(x.left), height(x.right)) + 1;
y.height = max(height(y.left), height(y.right)) + 1;
return y;
Node rotateRight(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = max(height(y.left), height(y.right)) + 1;
x.height = max(height(x.left), height(x.right)) + 1;
return x;
Node insert(Node node, int value) {
if (node == null) {
return new Node(value);
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
} else {
return node; // Duplicate values are not allowed in this implementation
node.height = max(height(node.left), height(node.right)) + 1;
int balance = getBalance(node);
// Left Left case
if (balance > 1 && value < node.left.value) {
return rotateRight(node);
}
// Right Right case
if (balance < -1 && value > node.right.value) {
return rotateLeft(node);
// Left Right case
if (balance > 1 && value > node.left.value) {
node.left = rotateLeft(node.left);
return rotateRight(node);
// Right Left case
if (balance < -1 && value < node.right.value) {
node.right = rotateRight(node.right);
return rotateLeft(node);
return node;
int getBalance(Node node) {
if (node == null) {
return 0;
return height(node.left) - height(node.right);
void preOrder(Node node) {
if (node != null) {
// Perform any operation here
System.out.print(node.value + " ");
preOrder(node.left);
preOrder(node.right);
public static void main(String[] args) {
avl tree = new avl();
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
System.out.println("Preorder traversal of constructed AVL tree:");
tree.preOrder(tree.root);
