fork download
copy 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class MaxHeap {
  9.     int capacity;
  10.     int size;
  11.     int arr[];
  12.  
  13.     MaxHeap(int capacity) {
  14.         this.capacity = capacity;
  15.         size = 0;
  16.         this.arr = new int[capacity];
  17.     }
  18.  
  19.     int parent(int i) {
  20.         return (i - 1) / 2;
  21.     }
  22.  
  23.     int left(int i) {
  24.         return 2 * i + 1;
  25.     }
  26.  
  27.     int right(int i) {
  28.         return 2 * i + 2;
  29.     }
  30.  
  31.     void insert(int ele) {
  32.         if (size == capacity) {
  33.             System.out.println("Heap overflow");
  34.             return;
  35.         }
  36.         arr[size] = ele;
  37.         int k = size;
  38.         size++;
  39.         while (k != 0 && arr[k] > arr[parent(k)]) {
  40.             int temp = arr[parent(k)];
  41.             arr[parent(k)] = arr[k];
  42.             arr[k] = temp;
  43.             k = parent(k);
  44.         }
  45.     }
  46.  
  47.     void heapify(int i) {
  48.         int largest = i;
  49.         int l = left(i);
  50.         int r = right(i);
  51.  
  52.         if (l < size && arr[l] > arr[largest]) {
  53.             largest = l;
  54.         }
  55.         if (r < size && arr[r] > arr[largest]) {
  56.             largest = r;
  57.         }
  58.         if (largest != i) {
  59.             int temp = arr[i];
  60.             arr[i] = arr[largest];
  61.             arr[largest] = temp;
  62.             heapify(largest);
  63.         }
  64.     }
  65.  
  66.     int deleteMax() {
  67.         if (size <= 0) {
  68.             System.out.println("Heap is empty");
  69.             return -1;
  70.         }
  71.         if (size == 1) {
  72.             size--;
  73.             return arr[0];
  74.         }
  75.         int root = arr[0];
  76.         arr[0] = arr[size - 1];
  77.         size--;
  78.         heapify(0);
  79.         return root;
  80.     }
  81.  
  82.     int getMax() {
  83.         return arr[0];
  84.     }
  85.  
  86.     public static void main(String[] args) throws java.lang.Exception {
  87.         MaxHeap h = new MaxHeap(20);
  88.         h.insert(4);
  89.         h.insert(1);
  90.         h.insert(2);
  91.         h.insert(6);
  92.         h.insert(7);
  93.         h.insert(3);
  94.         h.insert(8);
  95.         h.insert(5);
  96.         System.out.println("Max value is " + h.getMax());
  97.         h.insert(99);
  98.         System.out.println("Max value is " + h.getMax());
  99.         System.out.println("Deleted max value: " + h.deleteMax());
  100.         System.out.println("Max value after deletion is " + h.getMax());
  101.     }
  102. }
  103.  
Success #stdin #stdout 0.11s 55768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Max value is 8
Max value is 99
Deleted max value: 99
Max value after deletion is 8
https://ideone.com/v55fKz
language:
Java (HotSpot 12)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!