Binary Heap (Decrease Key, Delete)

PHOTO

Tue Feb 08 2022 15:29:22 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #heap #binaryheap #decreasekey #delete

import java.util.*;
import java.io.*;
  
class Test {
    
    public static class MinHeap{
        int arr[];
        int size;
        int capacity;
        
        MinHeap(int c){
        size = 0; 
        capacity = c; 
        arr = new int[c];
        }
    
        int left(int i) { return (2*i + 1); } 
        int right(int i) { return (2*i + 2); } 
        int parent(int i) { return (i-1)/2; } 
    
    
        public void insert(int x) 
        { 
            if (size == capacity)return;
            size++; 
            arr[size-1]=x; 
         
            for (int i=size-1;i!=0 && arr[parent(i)]>arr[i];) 
            { 
               int temp = arr[i]; 
                arr[i] = arr[parent(i)]; 
                arr[parent(i)] = temp; 
               i = parent(i); 
            } 
        }
    
        public void minHeapify(int i) 
        { 
            int lt = left(i); 
            int rt = right(i); 
            int smallest = i; 
            if (lt < size && arr[lt] < arr[i]) 
                smallest = lt; 
            if (rt < size && arr[rt] < arr[smallest]) 
                smallest = rt; 
            if (smallest != i) 
            { 
                int temp = arr[i]; 
                arr[i] = arr[smallest]; 
                arr[smallest] = temp; 
                minHeapify(smallest); 
            } 
        }
    
        public int extractMin() 
        { 
            if (size <= 0) 
                return Integer.MAX_VALUE; 
            if (size == 1) 
            { 
                size--; 
                return arr[0]; 
            }  
            int temp = arr[0]; 
            arr[0] = arr[size-1]; 
            arr[size-1] = temp;
            size--; 
            minHeapify(0); 
          
            return arr[size]; 
        }
    
        void decreaseKey(int i, int x) 
        { 
            arr[i] = x; 
            while (i != 0 && arr[parent(i)] > arr[i]) 
            { 
               int temp = arr[i]; 
               arr[i] = arr[parent(i)]; 
               arr[parent(i)] = temp; 
               i = parent(i); 
            } 
        }
    
        void deleteKey(int i) 
        { 
            decreaseKey(i, Integer.MIN_VALUE); 
            extractMin(); 
        }
    
    }
    
    public static void main(String args[]) 
    { 
        MinHeap h=new MinHeap(11);
        h.insert(3); 
        h.insert(2);
        h.deleteKey(0);
        h.insert(15);
        h.insert(20);
        System.out.println(h.extractMin());
        h.decreaseKey(2, 1);
        System.out.println(h.extractMin());
    } 
}

Output: 3 1

Save snippets that work from anywhere online with our extensions

Available in the Chrome Web Store

Get Firefox Add-on

Get VS Code extension

Comments

More like this

Heap

@Uttam

Binary Heap Implementation Binary Heap Insert Binary Heap (Heapify and Extract) Binary Heap (Decrease Key, Delete) Binary Heap (Build Heap) Heap Sort PriorityQueue in Java

#java #howto #interviewquestions #mobile

How to use Java Swing to create a button

import javax.swing.*;  
public class FirstSwingExample {  
public static void main(String[] args) {  
JFrame f=new JFrame();//creating instance of JFrame  
          
JButton b=new JButton("click");//creating instance of JButton  
b.setBounds(130,100,100, 40);//x axis, y axis, width, height  
          
f.add(b);//adding button in JFrame  
          
f.setSize(400,500);//400 width and 500 height  
f.setLayout(null);//using no layout managers  
f.setVisible(true);//making the frame visible  
}  
}

#java #java #arraylists #while-loops #equala

How to insert ArrayList into While-condition?

List<String> songList = new ArrayList<>();
songList.add("Some song"); //Repeat until satisfied

System.out.println("\n\tWelcome! Please choose a song!");
String songChoice = scan.nextLine();
while (!songList.contains(songChoice)) {
    //Do stuff when input is not a recognised song
}

#java #gfg #geeksforgeeks #lecture #recursion #rope cutting

Rope Cutting Problem

import java.io.*;
import java.util.*;

class GFG 
{
	static int maxCuts(int n, int a, int b, int c)
	{
		if(n == 0) return 0;
		if(n < 0)  return -1;

		int res = Math.max(maxCuts(n-a, a, b, c), 
		          Math.max(maxCuts(n-b, a, b, c), 
		          maxCuts(n-c, a, b, c)));

		if(res == -1)
			return -1;

		return res + 1; 
	}
  
    public static void main(String [] args) 
    {
    	int n = 5, a = 2, b = 1, c = 5;
    	
    	System.out.println(maxCuts(n, a, b, c));
    }
}

#java #gfg #geeksforgeeks #arrays #practice #frequencycount #frequencies #limitedrange

Frequencies of Limited Range Array Elements

class Solution{
    //Function to count the frequency of all elements from 1 to N in the array.
    public static void frequencyCount(int arr[], int N, int P)
    {
        //Decreasing all elements by 1 so that the elements
        //become in range from 0 to n-1.
        int maxi = Math.max(P,N);
        int count[] = new int[maxi+1];
        Arrays.fill(count, 0);
        for(int i=0;i<N;i++){
            count[arr[i]]++; 
        }
        
        for(int i=0;i<N;i++){
            arr[i] = count[i+1];
        }
    }
}

Print Nested Array in Java

String[][] deepArray = new String[][] {{"John", "Mary"}, {"Alice", "Bob"}};
System.out.println(Arrays.toString(deepArray));
//output: [[Ljava.lang.String;@106d69c, [Ljava.lang.String;@52e922]
System.out.println(Arrays.deepToString(deepArray));

How to efficiently iterate over each entry in a Java Map

Map<String, String> map = ...
for (Map.Entry<String, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + "/" + entry.getValue());
}

#java #interviewquestions #search

How to binary search in Java

import java.util.Stack;

/**
 * Java Program to implement a binary search tree. A binary search tree is a
 * sorted binary tree, where value of a node is greater than or equal to its
 * left the child and less than or equal to its right child.
 * 
 * @author WINDOWS 8
 *
 */
public class BST {

    private static class Node {
        private int data;
        private Node left, right;

        public Node(int value) {
            data = value;
            left = right = null;
        }
    }

    private Node root;

    public BST() {
        root = null;
    }

    public Node getRoot() {
        return root;
    }

    /**
     * Java function to check if binary tree is empty or not
     * Time Complexity of this solution is constant O(1) for
     * best, average and worst case. 
     * 
     * @return true if binary search tree is empty
     */
    public boolean isEmpty() {
        return null == root;
    }

    
    /**
     * Java function to return number of nodes in this binary search tree.
     * Time complexity of this method is O(n)
     * @return size of this binary search tree
     */
    public int size() {
        Node current = root;
        int size = 0;
        Stack<Node> stack = new Stack<Node>();
        while (!stack.isEmpty() || current != null) {
            if (current != null) {
                stack.push(current);
                current = current.left;
            } else {
                size++;
                current = stack.pop();
                current = current.right;
            }
        }
        return size;
    }


    /**
     * Java function to clear the binary search tree.
     * Time complexity of this method is O(1)
     */
    public void clear() {
        root = null;
    }

}

#java #java #2dchar array

How do you check a row in a 2D char array for a specific element and then count how many of that element are in the row? (Java)

private boolean oneQueenPerRow() {
    int foundQueens;
    for (int i = 0; i < board.length; i++) {
        foundQueens = 0;//each loop is a checked row
        for (int j = 0; j < board.length; j++) {
            if (board[i][j] == QUEEN)
                foundQueens++;
        }
        if (foundQueens > 1) return false;
    }
    return true;
}

Finding all classes implementing a specific interface

public <T> List<Class<? extends T>> findAllMatchingTypes(Class<T> toFind) {
    foundClasses = new ArrayList<Class<?>>();
    List<Class<? extends T>> returnedClasses = new ArrayList<Class<? extends T>>();
    this.toFind = toFind;
    walkClassPath();
    for (Class<?> clazz : foundClasses) {
        returnedClasses.add((Class<? extends T>) clazz);
    }
    return returnedClasses;
}

#java #mathematics #gfg #geeksforgeeks #quadraticequationroots

Quadratic Equation Roots

import java.io.*;
import java.util.*;

class Solution {
    public ArrayList<Integer> quadraticRoots(int a, int b, int c) {
        
       ArrayList<Integer> numbers = new ArrayList<Integer>();
       int d = (int) (Math.pow(b,2)-(4*a*c));
       int r1 = (int) Math.floor(((-1*b)+Math.sqrt(d))/(2*a));
       int r2 = (int) Math.floor(((-1*b)-Math.sqrt(d))/(2*a));
       if(d<0){
           numbers.add(-1);
       }
       else
       {
           numbers.add(Math.max(r1,r2));
           numbers.add(Math.min(r1,r2));
       }
       return numbers;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        while (T-- > 0) {
            int a, b, c;
            a = sc.nextInt();
            b = sc.nextInt();
            c = sc.nextInt();
            Solution obj = new Solution();
            ArrayList<Integer> ans = obj.quadraticRoots(a, b, c);
            if (ans.size() == 1 && ans.get(0) == -1)
                System.out.print("Imaginary");
            else
                for (Integer val : ans) System.out.print(val + " ");
            System.out.println();
        }
    }
}

#java #gfg #geeksforgeeks #recursion #possiblewordsfrom phone digits

Possible Words From Phone Digits

class Solution
{
    // String array to store keypad characters
    static String hash[] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    
    //Function to find list of all words possible by pressing given numbers.
    static ArrayList <String> possibleWords(int a[], int N)
    {
        String str = "";
        for(int i = 0; i < N; i++)
        str += a[i];
        ArrayList<String> res = possibleWordsUtil(str);
        //arranging all possible strings lexicographically.
        Collections.sort(res); 
        return res;
                    
    }
    
    //recursive function to return all possible words that can
    //be obtained by pressing input numbers.  
    static ArrayList<String> possibleWordsUtil(String str)
    {
        //if str is empty 
        if (str.length() == 0) { 
            ArrayList<String> baseRes = new ArrayList<>(); 
            baseRes.add(""); 
  
            //returning a list containing empty string.
            return baseRes; 
        } 
        
        //storing first character of str
        char ch = str.charAt(0); 
        //storing rest of the characters of str 
        String restStr = str.substring(1); 
  
        //getting all the combination by calling function recursively.
        ArrayList<String> prevRes = possibleWordsUtil(restStr); 
        ArrayList<String> Res = new ArrayList<>(); 
      
        String code = hash[ch - '0']; 
  
        for (String val : prevRes) { 
  
            for (int i = 0; i < code.length(); i++) { 
                Res.add(code.charAt(i) + val); 
            } 
        } 
        //returning the list.
        return Res; 
    }
}

#android #java #xml

Android LinearLayout gradient background

<?xml version="1.0" encoding="utf-8"?>
<shape xmlns:android="http://schemas.android.com/apk/res/android">
    <gradient
        android:angle="45"
        android:startColor="#ff00ff"
        android:endColor="#000000"/>
</shape>

> More steps

Its just print some message on console

for(int i = 0; i < 108; i++) {
System.out.println('Jai Shri Ram!');
}

Intent to Start New Activity in Android Studio

// IntendedActivity - the file you wish to open
// CurrentActivity - the file where this code is placed  

Intent intent = new Intent (this, IntendedActivity.class);
    CurrentActivity.this.startActivity(intent);

Insertion Sort in Java

 public void sort(int array[]) { 
     for (int i = 1; i < array.length; i++) { 
          int key = array[i]; 
          int j = i - 1; 
          while (j >= 0 && array[j] > key) { 
              array[j + 1] = array[j]; 
              j = j - 1; 
          } 
          array[j + 1] = key; 
      } 
 }

> More steps

Browse more snippets >>