Heap
Garbage
children elements are smaller/bigger than parent
Types of Heaps
Min Heap : Highest priority items assigned the lowest value
Max Heap : Highest priority items assigned the highest value
Applications of Heap
Used to implement HeapSort
Used to implement PriorityQueue
Formulae's
left of element : (2*i+1)
right of element : (2*i+2)
parent of element : (i-1)/2
Binary Heap Implementation (Array)
import java.util.*;
import java.io.*;
import java.lang.*;
class Main {
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 static void main(String args[]) {
MinHeap h = new MinHeap(11);
}
}Binary Heap Insert (Array) : MinHeap
import java.util.*;
import java.io.*;
import java.lang.*;
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 static void main(String args[]) {
MinHeap h = new MinHeap(11);
h.insert(3);
h.insert(2);
h.insert(15);
h.insert(20);
}
}Binary Heap (Heapify and Extract) : MinHeap
Extract operation is super important
import java.util.*;
import java.io.*;
import java.lang.*;
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];
}
}
public static void main(String args[]) {
MinHeap h = new MinHeap(11);
h.insert(3);
h.insert(2);
h.insert(15);
h.insert(20);
System.out.print(h.extractMin());
}
}Binary Heap (Decrease Key | Delete)
import java.util.*;
import java.io.*;
import java.lang.*;
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());
}
}Binary Heap ( Build Heap ) IMPORTANT
import java.util.*;
import java.io.*;
import java.lang.*;
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 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);
}
}
// IMPORTANT
public void buildHeap() {
for (int i = (size - 2) / 2; i >= 0; i--)
minHeapify(i);
}
}
public static void main(String args[]) {
MinHeap h = new MinHeap(11);
}
}Heap Sort
import java.lang.*;
public class Main {
public void buildheap(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
}
public void sort(int arr[]) {
int n = arr.length;
buildheap(arr, n);
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;
int l = 2 * i + 1;
int r = 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);
}
}
static void printArray(int arr[]) {
int n = arr.length;
for (int i = 0; i < n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
public static void main(String args[]) {
int arr[] = {12, 11, 13, 5, 6, 7};
int n = arr.length;
Main ob = new Main();
ob.sort(arr);
System.out.println("Sorted array is");
printArray(arr);
}
}Priority Queue (Min Heap Edition)
// Java program to demonstrate working of
// PriorityQueue in Java
import java.util.*;
class Main {
public static void main(String args[]) {
// Creating empty priority queue
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
// Adding items to the pQueue using add()
pq.add(10);
pq.add(20);
pq.add(15);
// Printing the top element of PriorityQueue
System.out.println(pq.peek());
// Printing the top element and removing it
// from the PriorityQueue container
System.out.println(pq.poll());
// Printing the top element again
System.out.println(pq.peek());
}
}Priority Queue (Max Heap Edition)
// Java program to demonstrate working of
// PriorityQueue in Java
import java.util.*;
class Main {
public static void main(String args[]) {
// Creating empty priority queue
PriorityQueue<Integer> pq
= new PriorityQueue<Integer>(
Collections.reverseOrder());
// Adding items to the pQueue using add()
pq.add(10);
pq.add(20);
pq.add(15);
// Above PriorityQueue is stored as following
// 20
// / \
// 10 15
// Printing the top element of PriorityQueue
System.out.println(pq.peek());
// Printing the top element and removing it
// from the PriorityQueue container
System.out.println(pq.poll());
// Post poll() PriorityQueue looks like
// 15
// /
// 10
// Printing the top element again
System.out.println(pq.peek());
}
}K-Sorted Array
import java.util.*;
import java.io.*;
import java.lang.*;
class Main {
private static void sortK(int[] arr, int n, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for (int i = 0; i < k + 1; i++) {
pq.add(arr[i]);
}
int index = 0;
for (int i = k + 1; i < n; i++) {
arr[index++] = pq.peek();
pq.poll();
pq.add(arr[i]);
}
while (pq.isEmpty() == false) {
arr[index++] = pq.poll();
}
}
private static void printArray(int[] arr, int n) {
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
public static void main(String[] args) {
int k = 3;
int arr[] = {2, 6, 3, 12, 56, 8};
int n = arr.length;
sortK(arr, n, k);
System.out.println("Following is sorted array");
printArray(arr, n);
}
}Buy Maximum Items with the given sum
import java.util.*;
import java.io.*;
import java.lang.*;
class Main {
public static void main(String args[]) {
int n = 5;
int cost[] = new int[]{1, 12, 5, 111, 200};
int sum = 10;
PriorityQueue<Integer> pq = new PriorityQueue<Integer>();
int res = 0;
for (int i = 0; i < n; i++)
pq.add(cost[i]);
for (int i = 0; i < n; i++) {
if (pq.peek() <= sum) {
sum -= pq.poll();
res++;
} else {
break;
}
}
System.out.print(res);
}
}Kth Largest Element
import java.io.*;
import java.util.*;
class GFG {
public static void firstKElements(int arr[], int n, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < k; i++) {
minHeap.add(arr[i]);
}
for (int i = k; i < n; i++) {
if (minHeap.peek() > arr[i])
continue;
else {
minHeap.poll();
minHeap.add(arr[i]);
}
}
Iterator iterator = minHeap.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
public static void main(String[] args) {
int arr[] = {11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45};
int size = arr.length;
int k = 3;
firstKElements(arr, size, k);
}
}K Closet Element
import java.io.*;
import java.util.*;
class GFG {
public static void firstKElements(int arr[], int n, int k) {
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
for (int i = 0; i < k; i++) {
minHeap.add(arr[i]);
}
for (int i = k; i < n; i++) {
if (minHeap.peek() > arr[i])
continue;
else {
minHeap.poll();
minHeap.add(arr[i]);
}
}
Iterator iterator = minHeap.iterator();
while (iterator.hasNext()) {
System.out.print(iterator.next() + " ");
}
}
public static void main(String[] args) {
int arr[] = {11, 3, 2, 1, 15, 5, 4, 45, 88, 96, 50, 45};
int size = arr.length;
int k = 3;
firstKElements(arr, size, k);
}
}Merge K Sorted Arrays
import java.io.*;
import java.util.*;
class Triplet implements Comparable<Triplet> {
int val, aPos, vPos;
Triplet(int v, int ap, int vp) {
val = v;
aPos = ap;
vPos = vp;
}
public int compareTo(Triplet t) {
if (val <= t.val) return -1;
else return 1;
}
}
class GFG {
public static List<Integer> mergeArr(ArrayList<ArrayList<Integer>> arr) {
List<Integer> res = new ArrayList<Integer>();
PriorityQueue<Triplet> pq = new PriorityQueue<Triplet>();
for (int i = 0; i < arr.size(); i++)
pq.add(new Triplet(arr.get(i).get(0), i, 0));
while (pq.isEmpty() == false) {
Triplet curr = pq.poll();
res.add(curr.val);
int ap = curr.aPos;
int vp = curr.vPos;
if (vp + 1 < arr.get(ap).size()) {
pq.add(new Triplet(arr.get(ap).get(vp + 1), ap, vp + 1));
}
}
return res;
}
public static void main(String[] args) {
ArrayList<ArrayList<Integer>> arr = new ArrayList<ArrayList<Integer>>();
ArrayList<Integer> a1 = new ArrayList<Integer>();
a1.add(10);
a1.add(20);
a1.add(30);
arr.add(a1);
ArrayList<Integer> a2 = new ArrayList<Integer>();
a2.add(5);
a2.add(15);
arr.add(a2);
ArrayList<Integer> a3 = new ArrayList<Integer>();
a3.add(1);
a3.add(9);
a3.add(11);
a3.add(18);
arr.add(a3);
List<Integer> res = mergeArr(arr);
System.out.println("Merged array is ");
for (int x : res)
System.out.print(x + " ");
}
}Median of Stream
import java.io.*;
import java.util.*;
class Node {
double data;
Node left, right;
int lCount;
Node(double x)
{
data = x;
left = right = null;
lCount = 0;
}
}
class GFG{
public static void printMedians(int arr[],int n){
PriorityQueue<Integer> g=new PriorityQueue<Integer>();
PriorityQueue<Integer> s=new PriorityQueue<Integer>(Collections.reverseOrder());
s.add(arr[0]);
System.out.print(arr[0]+" ");
for(int i=1;i<n;i++){
int x=arr[i];
if(s.size()>g.size())
{
if(s.peek()>x){
g.add(s.poll());
s.add(x);
}else g.add(x);
System.out.print(((double)(s.peek()+g.peek())/2)+" ");
}else{
if(x<=s.peek()){
s.add(x);
}else{
g.add(x);
s.add(g.poll());
}
System.out.print(s.peek()+" ");
}
}
}
public static void main(String args[])
{
int keys[] = { 12, 15, 10, 5, 8, 7, 16};
printMedians(keys,7);
}
}Last updated