// ----------------------------------------------------------------------------
// Program: VerticalOrder(Ascending)
//Vertical order
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
public TreeNode(int val) {
this.val = val;
this.left = this.right = null;
}
}
public class Main {
static TreeNode buildTrees(String st[])
{
if(st[0]=="N" || st.length==0)
return null;
TreeNode root= new TreeNode(Integer.parseInt(st[0]));
Queue Q=new LinkedList();
Q.add(root);
int i=1;
while(!Q.isEmpty() && i=st.length)
break;
current_value=st[i];
if(!current_value.equals("N"))
{
int element=Integer.parseInt(current_value);
current_element.right=new TreeNode(element);
Q.add(current_element.right);
}
i++;
}return root;}
static Map>> mymap = new TreeMap<>();
public static void solve(TreeNode curr, int col, int row) {
if (curr == null)
return;
mymap.computeIfAbsent(col, k -> new TreeMap<>()).computeIfAbsent(row, k -> new TreeSet<>()).add(curr.val);
solve(curr.left, col - 1, row + 1);
solve(curr.right, col + 1, row + 1);
}
public static void printMap() {
for (Map.Entry>> colEntry : mymap.entrySet()) {
for (Map.Entry> rowEntry : colEntry.getValue().entrySet()) {
System.out.print("Column: " + colEntry.getKey() + ", Row: " + rowEntry.getKey() + " -> Values: ");
for (int value : rowEntry.getValue()) {
System.out.print(value + " ");
}
System.out.println();
}
}
}
public static void main(String[] args) {
// Example usage:
Scanner sc=new Scanner(System.in);
String st[]=sc.nextLine().split(" ");
TreeNode root= buildTrees(st);
solve(root, 0, 0);
printMap();
}
}
INPUT
1 2 6 N 7 3 N 4 N N 5 N N 8
OUTPUT:
Column: -1, Row: 1 -> Values: 2
Column: -1, Row: 3 -> Values: 4
Column: 0, Row: 0 -> Values: 1
Column: 0, Row: 2 -> Values: 3 7
Column: 0, Row: 4 -> Values: 8
Column: 1, Row: 1 -> Values: 6
Column: 1, Row: 3 -> Values: 5
// ----------------------------------------------------------------------------
// Program: Right View of Binary tree
package dsaPack;
class Node {
Node left;
Node right;
int data;
}
class BinaryTree {
int maxLevel;
public void rightViewOfTree(Node node, int level) {
if(node == null) {
return;
}
if(level >= maxLevel) {
System.out.print(node.data + " ");
maxLevel++;
}
rightViewOfTree(node.right, level + 1);
rightViewOfTree(node.left, level + 1);
}
public Node createNewNode(int val) {
Node newNode = new Node();
newNode.data = val;
newNode.left = null;
newNode.right = null;
return newNode;
}
}
public class RightView {
public static void main(String[] args) {
BinaryTree a = new BinaryTree();
Node root = a.createNewNode(2);
root.left = a.createNewNode(7);
root.right = a.createNewNode(5);
root.left.left = a.createNewNode(3);
root.left.right = a.createNewNode(6);
root.left.right.left = a.createNewNode(5);
root.left.right.right = a.createNewNode(11);
root.right.right = a.createNewNode(9);
root.right.right.left = a.createNewNode(4);
a.rightViewOfTree(root, 0);
}
}
// ----------------------------------------------------------------------------
// Program: BFS & DFS
BFS & DFS
BFS
import java.util.*;
public class BFS {
int V;
LinkedList adj[];
BFS(int v)
{
V = v;
adj = new LinkedList[v];
for(int i=0;i queue = new LinkedList();
visited[s] = true;
queue.add(s);
while(queue.size()!=0)
{
s = queue.poll();
System.out.print(s + " ");
Iterator i = adj[s].listIterator();
while(i.hasNext())
{
int n = i.next();
if(visited[n] == false)
{
visited[n] = true;
queue.add(n);
}
}
}
}
public static void main(String[] args)
{
Scanner s = new Scanner(System.in);
int n = s.nextInt();
BFS graph = new BFS(n);
int v,e;
while(true) {
v = s.nextInt();
e = s.nextInt();
if (v == -1 && e == -1) {
break;
}
addEdges(v, e);
}
int S = s.nextInt();
System.out.print("BFS: " );
graph.bFS(S);
}
}
DFS
import java.util.*;
public class DFS {
int V;
LinkedList adj[];
DFS(int v)
{
V = v;
adj = new LinkedList[V];
for(int i=0;i i = adj[s].listIterator();
while(i.hasNext())
{
int n = i.next();
if(visited[n]==false)
dFSrec(n,visited);
}
}
void dFS(int s)
{
boolean visited[] = new boolean[V];
dFSrec(s,visited);
}
public static void main(String[] args)
{
Scanner s = new Scanner(System.in);
int n = s.nextInt();
DFS graph = new DFS(n);
int v,e;
while(true)
{
v = s.nextInt();
e = s.nextInt();
if(v == -1 && e == -1)
break;
graph.addEdges(v,e);
}
int S = s.nextInt();
System.out.print("DFS : ");
graph.dFS(S);
}
}
// ----------------------------------------------------------------------------
// Program: VERTICAL ORDER_NORMAL TRAVERSAL)
//VERTICAL ORDER
import java.util.*;
public class Main{
static TreeMap> map= new TreeMap<>();
static class TreeNode {
int data;
TreeNode left=null,right=null;
TreeNode(int d){
data=d;
}
}
static TreeNode buildTrees(String st[])
{
if(st[0]=="N" || st.length==0)
return null;
TreeNode root= new TreeNode(Integer.parseInt(st[0]));
Queue Q=new LinkedList();
Q.add(root);
int i=1;
while(!Q.isEmpty() && i=st.length)
break;
current_value=st[i];
if(!current_value.equals("N"))
{
int element=Integer.parseInt(current_value);
current_element.right=new TreeNode(element);
Q.add(current_element.right);
}
i++;
}return root;}
static LinkedList key=new LinkedList<>();
static void MapOrder(TreeNode crt,int x){
if(crt==null)
return;
MapOrder(crt.left,x-1);
LinkedList t= map.get(x);
if(t==null){
t= new LinkedList<>();
t.add(crt.data);
key.add(x);
}
else
t.add(crt.data);
map.put(x,t);
MapOrder(crt.right,x+1);
}
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
String st[]=sc.nextLine().split(" ");
TreeNode root= buildTrees(st);
MapOrder(root,0);
key.sort(Comparator.naturalOrder());
while(key.peek()!=null)
System.out.println(map.get(key.remove()));
}
}
// ----------------------------------------------------------------------------
// Program: Dials Alg_Pgm
//Dial's Alg
import java.util.*;
public class Graph {
static final int INF = Integer.MAX_VALUE;
private int V; // No. of vertices
// In a weighted graph, we need to store vertex
// and weight pair for every edge
private ArrayList > adj;
public Graph(int v) // Constructor
{
this.V = v;
this.adj = new ArrayList >();
for (int i = 0; i < v; i++)
this.adj.add(new ArrayList());
}
// function to Add an edge to graph
// Adds edge between u and v of weight w
public void AddEdge(int u, int v, int w)
{
adj.get(u).add(new Tuple(v, w));
adj.get(v).add(new Tuple(u, w));
}
// Prints shortest paths from src to all other vertices.
// W is the maximum weight of an edge
public void shortestPath(int src, int W)
{
int[] dist = new int[V];
Arrays.fill(dist, INF);
ArrayList[] B = new ArrayList[W * V + 1];
for (int i = 0; i < W * V + 1; i++)
B[i] = new ArrayList();
B[0].add(src);
dist[src] = 0;
int idx = 0;
while (true) {
// Go sequentially through buckets till one
// non-empty bucket is found
while (B[idx].size() == 0 && idx < W * V)
idx++;
// If all buckets are empty, we are done.
if (idx == W * V)
break;
// Take top vertex from bucket and pop it
int u = B[idx].get(0);
B[idx].remove(0);
// Process all adjacents of extracted vertex 'u'
// and update their distances if required.
for (Tuple i : adj.get(u)) {
int v = i.v;
int weight = i.w;
int du = dist[u];
int dv = dist[v];
// If there is shorted path to v through u.
if (dv > du + weight) {
// updating the distance
dist[v] = du + weight;
dv = dist[v];
// pushing vertex v into updated
// distance's bucket
B[dv].add(0, v);
}
}
}
// Print shortest distances stored in dist[]
System.out.println("Vertex Distance from Source");
for (int i = 0; i < V; ++i)
System.out.println(i + "\t\t" + dist[i]);
}
static class Tuple {
int v, w;
Tuple(int v, int w)
{
this.v = v;
this.w = w;
}
}
public static void main(String[] args)
{
// create the graph given in above figure
int V = 6;
Graph g = new Graph(V);
// making above shown graph
g.AddEdge(0, 1, 4);
g.AddEdge(0, 2, 2);
g.AddEdge(2, 1, 1);
g.AddEdge(1, 4, 2);
g.AddEdge(2, 3, 4);
g.AddEdge(4, 3, 3);
g.AddEdge(2, 4, 4);
g.AddEdge(4, 5, 3);
g.AddEdge(3, 5, 1);
// maximum weighted edge - 4
g.shortestPath(0, 4);
}
}
// ----------------------------------------------------------------------------
// Program: Binomial heap_code_1
class BinomialHeapNode {
int key, degree;
BinomialHeapNode parent;
BinomialHeapNode sibling;
BinomialHeapNode child;
public BinomialHeapNode(int k)
{
key = k;
degree = 0;
parent = null;
sibling = null;
child = null;
}
public BinomialHeapNode reverse(BinomialHeapNode sibl)
{
BinomialHeapNode ret;
if (sibling != null)
ret = sibling.reverse(this);
else
ret = this;
sibling = sibl;
return ret;
}
public BinomialHeapNode findMinNode()
{
BinomialHeapNode x = this, y = this;
int min = x.key;
while (x != null) {
if (x.key < min) {
y = x;
min = x.key;
}
x = x.sibling;
}
return y;
}
public BinomialHeapNode findANodeWithKey(int value)
{
BinomialHeapNode temp = this, node = null;
while (temp != null) {
if (temp.key == value) {
node = temp;
break;
}
if (temp.child == null)
temp = temp.sibling;
else {
node = temp.child.findANodeWithKey(value);
if (node == null)
temp = temp.sibling;
else
break;
}
}
return node;
}
public int getSize()
{
return (1 + ((child == null) ? 0 : child.getSize())
+ ((sibling == null) ? 0 : sibling.getSize()));
}
}
class BinomialHeap {
private BinomialHeapNode Nodes;
private int size;
public BinomialHeap()
{
Nodes = null;
size = 0;
}
public boolean isEmpty() { return Nodes == null; }
public int getSize() { return size; }
public void makeEmpty()
{
Nodes = null;
size = 0;
}
public void insert(int value)
{
if (value > 0) {
BinomialHeapNode temp
= new BinomialHeapNode(value);
if (Nodes == null) {
Nodes = temp;
size = 1;
}
else {
unionNodes(temp);
size++;
}
}
}
private void merge(BinomialHeapNode binHeap)
{
BinomialHeapNode temp1 = Nodes, temp2 = binHeap;
while ((temp1 != null) && (temp2 != null)) {
if (temp1.degree == temp2.degree) {
BinomialHeapNode tmp = temp2;
temp2 = temp2.sibling;
tmp.sibling = temp1.sibling;
temp1.sibling = tmp;
//atha temp1 la add paniyachu la adutha element polam vanga.
temp1 = tmp.sibling;
}
else {
if (temp1.degree < temp2.degree) {
if ((temp1.sibling == null)|| (temp1.sibling.degree > temp2.degree)) {
BinomialHeapNode tmp = temp2;
temp2 = temp2.sibling;
tmp.sibling = temp1.sibling;
temp1.sibling = tmp;
temp1 = tmp.sibling;
}
else {
temp1 = temp1.sibling;
}
}
else {
BinomialHeapNode tmp = temp1;
temp1 = temp2;
temp2 = temp2.sibling;
temp1.sibling = tmp;
if (tmp == Nodes) {
Nodes = temp1;
}
}
}
}
if (temp1 == null) {
temp1 = Nodes;
while (temp1.sibling != null) {
temp1 = temp1.sibling;
}
temp1.sibling = temp2;
}
}
private void unionNodes(BinomialHeapNode binHeap)
{
merge(binHeap);
BinomialHeapNode prevTemp = null, temp = Nodes,
nextTemp = Nodes.sibling;
while (nextTemp != null) {
if ((temp.degree != nextTemp.degree) || ((nextTemp.sibling != null)&& (nextTemp.sibling.degree == temp.degree))) {
prevTemp = temp;
temp = nextTemp;
}
else {
if (temp.key <= nextTemp.key) {
temp.sibling = nextTemp.sibling;
nextTemp.parent = temp;
nextTemp.sibling = temp.child;
temp.child = nextTemp;
temp.degree++;
}
else {
if (prevTemp == null) {
Nodes = nextTemp;
}
else {
prevTemp.sibling = nextTemp;
}
temp.parent = nextTemp;
temp.sibling = nextTemp.child;
nextTemp.child = temp;
nextTemp.degree++;
temp = nextTemp;
}
}
nextTemp = temp.sibling;
}
}
public int findMinimum()
{
return Nodes.findMinNode().key;
}
public void delete(int value)
{
if ((Nodes != null) && (Nodes.findANodeWithKey(value) != null)) {
decreaseKeyValue(value, Integer.MIN_VALUE);
extractMin();
}
}
public void decreaseKeyValue(int old_value,
int new_value)
{
BinomialHeapNode temp
= Nodes.findANodeWithKey(old_value);
if (temp == null)
return;
temp.key = new_value;
BinomialHeapNode tempParent = temp.parent;
while ((tempParent != null)
&& (temp.key < tempParent.key)) {
int z = temp.key;
temp.key = tempParent.key;
tempParent.key = z;
temp = tempParent;
tempParent = tempParent.parent;
}
}
public int extractMin()
{
if (Nodes == null)
return -1;
BinomialHeapNode temp = Nodes, prevTemp = null;
BinomialHeapNode minNode = Nodes.findMinNode();
while (temp.key != minNode.key) {
prevTemp = temp;
temp = temp.sibling;
}
if (prevTemp == null) {
Nodes = temp.sibling;
}
else {
prevTemp.sibling = temp.sibling;
}
temp = temp.child;
BinomialHeapNode fakeNode = temp;
while (temp != null) {
temp.parent = null;
temp = temp.sibling;
}
if ((Nodes == null) && (fakeNode == null)) {
size = 0;
}
else {
if ((Nodes == null) && (fakeNode != null)) {
Nodes = fakeNode.reverse(null);
size = Nodes.getSize();
}
else {
if ((Nodes != null) && (fakeNode == null)) {
size = Nodes.getSize();
}
else {
unionNodes(fakeNode.reverse(null));
size = Nodes.getSize();
}
}
}
return minNode.key;
}
public void displayHeap()
{
System.out.print("\nHeap : ");
displayHeapHelper(Nodes);
System.out.println("\n");
}
private void displayHeapHelper(BinomialHeapNode r)
{
if (r != null) {
displayHeapHelper(r.child);
System.out.print(r.key + " ");
displayHeapHelper(r.sibling);
}
}
}
public class binomheap {
public static void main(String[] args)
{
BinomialHeap binHeap = new BinomialHeap();
binHeap.insert(12);
binHeap.insert(8);
binHeap.insert(5);
binHeap.insert(15);
binHeap.insert(7);
binHeap.insert(2);
binHeap.insert(9);
System.out.println("Size of the binomial heap is "+ binHeap.getSize());
binHeap.displayHeap();
binHeap.delete(15);
binHeap.delete(8);
System.out.println("Size of the binomial heap is "+ binHeap.getSize());
binHeap.displayHeap();
binHeap.makeEmpty();
System.out.println(binHeap.isEmpty());
}
}
// ----------------------------------------------------------------------------
// Program: RecoverBst1_Tree_Using STACK
// Recover BST using STACK
//You are given the root of a binary search tree (BST),
//where the values of exactly two nodes of the tree were swapped by mistake.
//Recover the tree with out changing its structure.
import java.io.*;
import java.util.*;
class TreeNode
{
int data;
TreeNode right;
TreeNode left;
TreeNode(int data)
{
this.data=data;
this.left=null;
this.right=null;
}
}
public class Main
{
static TreeNode build(String st[])
{
if(st[0]=="N" || st.length==0)
return null;
TreeNode root= new TreeNode(Integer.parseInt(st[0]));
Queue Q=new LinkedList();
Q.add(root);
int i=1;
while(!Q.isEmpty() && i=st.length)
break;
current_value=st[i];
if(!current_value.equals("N"))
{
int element=Integer.parseInt(current_value);
current_element.right=new TreeNode(element);
Q.add(current_element.right);
}
i++;
}return root;}
static void recoverTree(TreeNode root)
{
Stack stack = new Stack();
TreeNode current=root;
TreeNode processed=null;
TreeNode[] swapp=new TreeNode[2];
while(!stack.isEmpty() || current!=null)
{
while(current!=null)
{
stack.push(current);
current=current.left;
}
current=stack.pop();
if(processed!=null && processed.data > current.data)
{
if(swapp[0]==null)
{
swapp[0]=processed;
swapp[1]=current;
}
else
{
swapp[1]=current;
break;
}
}
processed=current;
current=current.right;
}
int t=swapp[0].data;
swapp[0].data=swapp[1].data;
swapp[1].data=t;
}
public static void inorder(TreeNode temp)
{
if(temp==null)
return;
inorder(temp.left);
System.out.print(temp.data+" ");
inorder(temp.right);
}
public static void main(String[] args)
{
Scanner sc= new Scanner(System.in);
String st[]=sc.nextLine().split(" ");
if(st[0].equals("N"))
{
System.out.println("0");
return;
}
TreeNode root=build(st);
inorder(root);
recoverTree(root);
System.out.println("\nAfter Recovery");
inorder(root);
}
}
// ----------------------------------------------------------------------------
// Program: Left view of Binary Tree
//Left view of Binary Tree
https://www.youtube.com/watch?v=YkUvqoo1-jw&t=6s
class Node {
Node left;
Node right;
int data;
}
class BinaryTree {
int maxLevel;
public void leftViewOfTree(Node node, int level) {
if(node == null) {
return;
}
if(level >= maxLevel) {
System.out.print(node.data + " ");
maxLevel++;
}
leftViewOfTree(node.left, level + 1);
leftViewOfTree(node.right, level + 1);
}
public Node createNewNode(int val) {
Node newNode = new Node();
newNode.data = val;
newNode.left = null;
newNode.right = null;
return newNode;
}
}
public class Main {
public static void main(String[] args) {
BinaryTree a = new BinaryTree();
Node root = a.createNewNode(2);
root.left = a.createNewNode(7);
root.right = a.createNewNode(5);
root.left.left = a.createNewNode(3);
root.left.right = a.createNewNode(6);
root.left.right.left = a.createNewNode(5);
root.left.right.right = a.createNewNode(11);
root.right.right = a.createNewNode(9);
root.right.right.left = a.createNewNode(4);
a.leftViewOfTree(root, 0);
}
}
// ----------------------------------------------------------------------------
// Program: BOTTOM VIEW
//BOTTOM VIEW
import java.util.*;
import java.util.Map.Entry;
class Node {
int data,hd;
Node left, right;
public Node(int data){
this.data = data;
left = right = null;
this.hd = Integer. MAX_VALUE;
}
}
class Main {
static Node root;
private List path1 = new ArrayList<>();
private List path2 = new ArrayList<>();
static Node build(String s[]){
if(s[0]=="N"||s.length==0)
return null;
Node root=new Node(Integer.parseInt(s[0]));
Queue q=new LinkedList();
q.add(root);
int i=1;
while(!q.isEmpty() && i= s.length)
break;
cval = s[i];
if(!cval.equals("N")){
int h=Integer.parseInt(cval);
curr.right=new Node(h);
q.add(curr.right);
}
i++;
}
return root;
}
static void bottomview(Node root){
if (root == null)
return;
int hd = 0;
Map map = new TreeMap<>();
Queue queue = new LinkedList();
root.hd = hd;
queue.add(root);
while (!queue.isEmpty()){
Node temp = queue.remove();
hd = temp.hd;
map.put(hd, temp.data);
if (temp.left != null){
temp.left.hd = hd-1;
queue.add(temp.left);
}
if (temp.right != null)
{
temp.right.hd = hd+1;
queue.add(temp.right);
}
}
Set> set = map.entrySet();
Iterator> iterator = set.iterator();
while (iterator.hasNext()){
Map.Entry me = iterator.next();
System.out.print(me.getValue()+" ");
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int i;
Main ob = new Main();
String s[]=sc.nextLine().split(" ");
root = build(s);
ob.bottomview(root);
}
}
// ----------------------------------------------------------------------------
// Program: Topological Sort
//Topological Sort
import java.util.*;
public class TopologicalSort {
// Function to perform DFS and topological sorting
static void
topologicalSortUtil(int v, List > adj,
boolean[] visited,
Stack stack)
{
// Mark the current node as visited
visited[v] = true;
// Recur for all adjacent vertices
for (int i : adj.get(v)) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, stack);7
}
// Push current vertex to stack which stores the
// result
stack.push(v);
}
// Function to perform Topological Sort
static void topologicalSort(List > adj,
int V)
{
// Stack to store the result
Stack stack = new Stack<>();
boolean[] visited = new boolean[V];
// Call the recursive helper function to store
// Topological Sort starting from all vertices one
// by one
for (int i = 0; i < V; i++) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, stack);
}
// Print contents of stack
System.out.print(
"Topological sorting of the graph: ");
while (!stack.isEmpty()) {
System.out.print(stack.pop() + " ");
}
}
// Driver code
public static void main(String[] args)
{
// Number of nodes
int V =5;
// Edges
List > edges = new ArrayList<>();
edges.add(Arrays.asList(0, 1));
edges.add(Arrays.asList(0, 2));
edges.add(Arrays.asList(2, 4));
edges.add(Arrays.asList(4, 1));
edges.add(Arrays.asList(4, 3));
edges.add(Arrays.asList(1, 3));
// Graph represented as an adjacency list
List > adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (List i : edges) {
adj.get(i.get(0)).add(i.get(1));
}
topologicalSort(adj, V);
}
}
// ----------------------------------------------------------------------------
// Program: K-ary Heap
import java.util.ArrayList;
public class Main {
private static int n;
private static ArrayList arl = new ArrayList();
public static int getMax() {
if (isEmpty()) {
return Integer.MIN_VALUE;
}
return arl.get(0);
}
public static boolean isEmpty() {
return (arl.size() == 0);
}
public static void insert(int value) {
arl.add(value);
int childrenIndex = arl.size() - 1;
int parentIndex = (childrenIndex - 1) / n;
while (parentIndex >= 0 && arl.get(childrenIndex) > arl.get(parentIndex)) {
int temp = arl.get(childrenIndex);
arl.set(childrenIndex, arl.get(parentIndex));
arl.set(parentIndex, temp);
childrenIndex = parentIndex;
parentIndex = (childrenIndex - 1) / n;
} }
public static void removeMax() {
arl.set(0, arl.get(arl.size() - 1));
arl.remove(arl.size() - 1);
int parentIndex = 0;
while (true) {
int largestValueIndex = parentIndex;
for (int i = n * parentIndex + 1; i <= (n * parentIndex + n) && i < arl.size(); i++) {
if (arl.get(largestValueIndex) < arl.get(i)) {
largestValueIndex = i;
}
}
if (largestValueIndex == parentIndex) {
break;
}
else {
int temp = arl.get(parentIndex);
arl.set(parentIndex, arl.get(largestValueIndex));
arl.set(largestValueIndex, temp);
parentIndex = largestValueIndex;
}
}
}
public static void main(String[] args) {
n=3;
ArrayList arr = new ArrayList();
arr.add(4);
arr.add(5);
arr.add(6);
arr.add(7);
arr.add(8);
arr.add(9);
arr.add(10);
for (int i = 0; i < arr.size(); i++) {
insert(arr.get(i));
}
System.out.println("Get Top element " + getMax());
System.out.println(arl);
removeMax();
System.out.println("The maximum Element in the heap is: " + getMax());
}
}
// ----------------------------------------------------------------------------
// Program: heap sort
Sample Input 1
5
78 45 12 65 98
Sample Output 1
12 45 65 78 98
import java.util.Scanner;
class HeapSort
{
public void sort(int arr[])
{
int n = arr.length;
for (int i = n / 2 - 1; i >= 0; i--)
{
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--)
{
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2 * i + 1; // left = 2*i + 1
int r = 2 * i + 2; // right = 2*i + 2
if (l < n && arr[l] > arr[largest])
{
largest = l;
}
if (r < n && arr[r] > arr[largest])
{
largest = r;
}
if (largest != i)
{
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
heapify(arr, n, largest);
}
}
void printArray(int arr[])
{
int n = arr.length;
for (int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();
}
}
class Main
{
public static void main(String args[])
{
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int arr[] = new int[n];
for(int i=0;i < n;i++)
{
arr[i] = sc.nextInt();
}
HeapSort ob = new HeapSort();
ob.sort(arr);
ob.printArray(arr);
}
}