Binary Heap Max Heap using Array Representation

helloprogrammin...
www.tutsstore.com/
www.skillsincod...

[@krushpatel5545]

beautiful work Ripon - keep it up !!

[@techteach9577]

good tutorial...understandable one...well done :)

[@NewBlueTrue]

I don’t understand how int child = pos - 1. Shouldn’t it be ( int child = (2 * pos) + 1) ) ?

[@NewBlueTrue]

Never mind. Since this is insertion, you are calling the last index of the heap which you can use (pos - 1) or (size - 1), if you change your variable.

[@AmanSingh-pf1kb]

one more thing,
Heap is a form of binary tree ie. it has levels.
root level i. first level = 1 node => 2^0 +1 = 1 total node of BT
second level = 2 nodes => 2^1 + 1 = 3 total node Of BT
third level = 4 nodes => 2^2 + 1 = 5 total nodes
:
:
n level = 2^n + 1 total nodes of BT
get one more variable "level" and initialize it to 0.
capacity = 1+ (int) Math.pow(2, level);
while increasing capacity, increment Level first. ie. level++
Another version of previous code is :
package Heap;
import java.util.*;
public class Heap {
private int[] heap;
private int capacity;
private int position;
private int level;
public Heap() {
position = 0;
level = 0;
capacity = 1 + (int) Math.pow(2, level);
heap = new int[capacity];
}
public void insert(int value) {
if ((position) == capacity) {
level++;
capacity = 1 + (int) Math.pow(2, level);
// System.out.println("---------"+capacity+"-------------");
int[] newHeap = heap.clone();
this.heap = new int[capacity];
for (int i = 0; i < newHeap.length; i++) {
this.heap[i] = newHeap[i];
}
add(value);
} else
add(value);
}
private void add(int value) {
heap[position++] = value;
int child = position - 1;
int parent = (child - 1) / 2;
while (heap[parent] < heap[child] && parent >= 0) {
int temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
child = parent;
parent = child / 2;
}
}
public void traverse() {
for (int a : heap)
System.out.println(a);
}
}

[@AmanSingh-pf1kb]

Your code has lots of mistake.
First of all, Parent = (Child -1)/2
Second, position starts with 0
third, condition in while loop supposed to be Parent >= 0
Following is complete corrected code of your implementation.
public class Heap {
private int[] heap ;
private int capacity;
private int position;
public Heap(){
position = 0;
capacity = 10;
heap = new int[capacity];
}
public void insert(int value){
if(position == capacity){
return;
} else {
heap[position++] = value;
int child = position -1;
int parent = (child-1) /2;
while(heap[parent] < heap[child] && parent >= 0){
int temp = heap[parent];
heap[parent] = heap[child];
heap[child] = temp;
child = parent;
parent = child/2;
}
}
}
public void traverse(){
for(int a : heap)
System.out.println(a);
}

}

[@AmanSingh-pf1kb]

I think you've missed my updated version of *this* code, which I've already posted in comment section the same day. And Yes, *this* code fails, but this is the *corrected* version of code of *this video*. Below you will find another implementation of Heap and you are free to test it, and do let me know whether it fails or not. :)

[@abednegosteven-4423]

how to remove/deletion element sir ?

[@carlosjacobfield-sierra3759]

public int denqueue() {
if (pos == capacity) {
}
int returnVal = theHeap[1];
theHeap[1] = theHeap[pos - 1];
theHeap[pos - 1] = 0;
int curIndex = 1;
int child1 = (curIndex * 2);
int child2 = (curIndex * 2) + 1;
boolean isTrue = true;
pos--;
while (isTrue) {
if (child1 > pos - 1) {
isTrue = false;
}
else if (child2 > pos - 1) {
if (theHeap[child1] > theHeap[curIndex]) {
int tmp = theHeap[curIndex];
theHeap[curIndex] = theHeap[child1];
theHeap[child1] = tmp;
}
isTrue = false;
}
// What child is bigger
else if (theHeap[child1] < theHeap[pos]
&& theHeap[child2] < theHeap[pos]) {
isTrue = false;
} else if (theHeap[child1] > theHeap[child2]) {
int tmp = theHeap[curIndex];
theHeap[curIndex] = theHeap[child1];
theHeap[child1] = tmp;
curIndex = child1;
child1 = (curIndex * 2);
child2 = (curIndex * 2) + 1;
} else if (theHeap[child1] < theHeap[child2]) {
int tmp = theHeap[curIndex];
theHeap[curIndex] = theHeap[child2];
theHeap[child2] = tmp;
curIndex = child2;
child1 = (curIndex * 2);
child2 = (curIndex * 2) + 1;
} else {
isTrue = false;
}
}
return returnVal;
}

[@anupmistry479]

proper explanation is missing

[@curiossoul]

Using 1 based index is such a mood off

[@Seeethy]

nicely explained, but you should work with your accent, couse sometimes i could barely understand you.

[@onlineearning6301]

its really helpful for me, thanks , i need more guide line about max heap coding, can you share please you email , i wanna contact with you, please