Comment on page

# Heapify

## Min Heap

PriorityQueue<Integer> q = new PriorityQueue<Integer>();
class MinHeap {
int[] harr; // Array of elements in heap
int heap_size; // Current number of elements in min heap
int capacity; // maximum possible size of min heap
// Constructor: Builds a heap from
// a given array a[] of given size
public MinHeap(int a[], int size)
{
heap_size = size;
capacity = size;
harr = a;
int i = (heap_size - 1) / 2;
while (i >= 0) {
MinHeapify(i);
i--;
}
}
// A recursive method to heapify a subtree
// with the root at given index
// This method assumes that the subtrees
void MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i) {
swap(i, smallest);
MinHeapify(smallest);
}
}
int parent(int i) { return (i - 1) / 2; }
// to get index of left child of node at index i
int left(int i) { return (2 * i + 1); }
// to get index of right child of node at index i
int right(int i) { return (2 * i + 2); }
// Method to remove minimum element (or root) from min heap
int extractMin()
{
if (heap_size <= 0)
return Integer.MAX_VALUE;
if (heap_size == 1) {
heap_size--;
return harr[0];
}
// Store the minimum value, and remove it from heap
int root = harr[0];
harr[0] = harr[heap_size - 1];
heap_size--;
MinHeapify(0);
return root;
}
// Inserts a new key 'k'
void insertKey(int k)
{
if (heap_size == capacity) {
System.out.println("Overflow: Could not insertKey");
return;
}
// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = k;
// Fix the min heap property if it is violated
while (i != 0 && harr[parent(i)] > harr[i]) {
swap(i, parent(i));
i = parent(i);
}
}
// A utility function to check
// if size of heap is 1 or not
boolean isSizeOne()
{
return (heap_size == 1);
}
// A utility function to swap two elements
void swap(int x, int y)
{
int temp = harr[x];
harr[x] = harr[y];
harr[y] = temp;
}
}

## Max Heap

PriorityQueue<Integer> q = new PriorityQueue<Integer>(Collections.reverseOrder());