Binary Heap properties

 A Binary Heap is a Binary Tree with following properties.

1) It’s a complete tree (All levels are completely filled except possibly the last level and the last level has all keys as left as possible). This property of Binary Heap makes them suitable to be stored in an array.

2) A Binary Heap is either Min Heap or Max Heap. In a Min Binary Heap, the key at root must be minimum among all keys present in Binary Heap. The same property must be recursively true for all nodes in Binary Tree. Max Binary Heap is similar to MinHeap.

• Arr[(i-1)/2]	Returns the parent node
  Arr[(2*i)+1]	Returns the left child node
  Arr[(2*i)+2]	Returns the right child node

Arr[(n/2) .... (n-1)] => will contain the leaf nodes, if n is the length of the array or total number of nodes.

The traversal method use to achieve Array representation is Level Order


Source: geeks for geeks

Max & Min Heaps in Java

Part 1 provides a base class with functions common to max heap and min heap.

Part 2 below provides code for Min Heap construction, removal of an element and finding the kth smallest element from the heap.

Part 3 below provide code for Max heap construction, removal of an element and finding the kth largest element from the heap.

Part 1: Class with common functions of heap (get parent, printing etc)

import java.util.ArrayList;
public class Heap {

 ArrayList heap = new ArrayList(); 
 
 int parentIndex(int index) {
  return (index-1)/2;
 } 
 int getParent(int index)  {
  return heap.get(parentIndex(index));
 }
 int getLeftIndex(int index) {
  return (2*index + 1);
 }
 int getRightIndex(int index) {
  return (2*index + 2);
 }
 boolean validIndex(int index){
  return (index>= 0 && index< heap.size()) ? true: false;
 }
 void swap(int index1, int index2)  {
  int temp = heap.get(index1);
  heap.set(index1, heap.get(index2));
  heap.set(index2, temp);
 }
 
 void printHeap(){
  System.out.println(heap);
 }
}

Part 2: Min Heap & Getting kth smallest element

public class MinHeap extends Heap{

 int minHeapify(int index) {
  while(index!= 0 && getParent(index) > heap.get(index)){
   swap(parentIndex(index), index);
   index = parentIndex(index);
  }
  return index;
 }

 void insert(int[] input) {
  int index=heap.size() -1;
  for(int i=0; i< input.length; i++){
   heap.add(input[i]); index++;
   minHeapify(index);
  }
 }

 void siftDown(int pos)
 {
  int minIndex, rightIndex;
  while(validIndex(getLeftIndex(pos)))
  {
   minIndex = getLeftIndex(pos);
   rightIndex = getRightIndex(pos);
   if(validIndex(rightIndex) && heap.get(rightIndex) < heap.get(minIndex))
   {
    minIndex = rightIndex;
   }
   if(heap.get(pos) > heap.get(minIndex))
   {
    swap(pos, minIndex);
    pos = minIndex;
   }
   else break;
  }
 }

 boolean remove(int pos)
 {
  if(!validIndex(pos)) return false;
  if(pos == (heap.size()-1)) {
   heap.remove(pos);
   return true;
  }
  swap(pos, heap.size() -1);
  heap.remove(heap.size()-1);
  pos = minHeapify(pos);
  siftDown(pos);
  return true;
 }
 
 int getKthMin(int k)
 {
  if(k > heap.size()) return -1;
  if(k == 1) return heap.get(0);
  remove(0);
  return getKthMin(k-1);
 }

 public static void main(String[] args) {

  int[] input = {4,6,10,9,8,1,0};
  MinHeap obj = new MinHeap();
  obj.insert(input);
  obj.printHeap();
//  obj.remove(6);
  System.out.println(obj.getKthMin(4));
 }

Part 3: Max heap & get the kth largest element

public class MinHeap extends Heap{
 int minHeapify(int index)
 {
  while(index!=0 && getParent(index) > heap.get(index))
  {
   swap(parentIndex(index), index);
   index = parentIndex(index);
  }
  return index;
 }

 void insert(int[] input)
 {
  int index=heap.size() -1;
  for(int i=0; i< input.length; i++)
  {
   heap.add(input[i]); index++;
   minHeapify(index);
  }
 }

 void siftDown(int pos)
 {
  int minIndex, rightIndex;
  while(validIndex(getLeftIndex(pos)))
  {
   minIndex = getLeftIndex(pos);
   rightIndex = getRightIndex(pos);
   if(validIndex(rightIndex) && heap.get(rightIndex) < heap.get(minIndex))
   {
    minIndex = rightIndex;
   }
   if(heap.get(pos) > heap.get(minIndex))
   {
    swap(pos, minIndex);
    pos = minIndex;
   }
   else break;
  }
 }

 boolean remove(int pos)
 {
  if(!validIndex(pos)) return false;
  if(pos == (heap.size()-1)) {
   heap.remove(pos);
   return true;
  }
  swap(pos, heap.size() -1);
  heap.remove(heap.size()-1);
  pos = minHeapify(pos);
  siftDown(pos);
  return true;
 }
 
 int getKthMin(int k)
 {
  if(k > heap.size()) return -1;
  if(k == 1) return heap.get(0);
  remove(0);
  return getKthMin(k-1);
 }

 public static void main(String[] args) {

  int[] input = {4,6,10,9,8,1,0};
  MinHeap obj = new MinHeap();
  obj.insert(input);
  obj.printHeap();
//  obj.remove(6);
  System.out.println(obj.getKthMin(4));
 }