Binary Heap Max Heap using Array Representation

[NewBlueTrue]

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

[AmanSingh-pfkb]

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);
}



}

[techteach]

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

[curiossoul]

Using 1 based index is such a mood off

[AmanSingh-pfkb]

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);
//
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);
}

}

[Seeethy]

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

[onlineearning]

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