Summary Heaps

Heaps

,Heap Implementation :
public class Heap {
int[] arr = new int[100];
int size;

public Heap() {
arr[0] = -1;
size = 0;
}

public boolean isEmpty() {
return size == 0;
}

public int size() {
return size;
}

//---------------------------------------------------------------------

public void insert(int val) {
size = size + 1;
int index = size;
arr[index] = val;

while (index > 1) {
int parent = index / 2;

if (arr[parent] < arr[index]) {
int temp = arr[parent];
arr[parent] = arr[index];
arr[index] = temp;

index = parent;
}

else {
return;
}
}
}

//---------------------------------------------------------------------



Insert : compare child to its parent.
Delete : compare parent to its child.

, public void delete() {
if (size == 0) {
System.out.println("Heap is Empty");
return;
}

//Step 1 : Put last element into first index :
arr[1] = arr[size];

//Step 2 : Remove last element :
size--;

//Step 3 : Take root node to its correct position :
int i = 1;

while (i < size) {
int leftIndex = 2 * i;
int rightIndex = 2 * i + 1;

if (leftIndex < size && arr[i] < arr[leftIndex]) {
int temp = arr[i];
arr[i] = arr[leftIndex];
arr[leftIndex] = temp;
i = leftIndex;
}

else if (rightIndex < size && arr[i] < arr[rightIndex]) {
int temp = arr[i];
arr[i] = arr[rightIndex];
arr[rightIndex] = temp;
i = rightIndex;
}

else {
return;
}
}
}
//---------------------------------------------------------------------

public void printMaxHeap() {
for (int i = 1; i <= size; i++) {
System.out.print(arr[i] + " ");
}
}


--------------------------------------------------------------------------------------------------------------------------------------
Heapify : convert an array into Heap.