There is a small mistake in liang book. I was going through this heap Data Structure in the book,I found out that parent index , left child index and right child index needs correction
In the book
Parent index = (currentIndex - 1)/2
leftChild Index = (2 * currentIndex);
rightChildIndex = (2 * currentIndex + 1);
this is giving wrong results
Proof:
but in actual it should be:
package com.liang.datastructures;
import java.util.ArrayList;
public class Heap {
private ArrayList list = new ArrayList();
public Heap(){
}
public ArrayList getList() {
return list;
}
public void setList(ArrayList list) {
this.list = list;
}
public Heap(Object []objects){
for(int i=0;i<objects.length;i++){
add(objects[i]);
}
}
public void add(Object obj){
list.add(obj);
int currentIndex = list.size() - 1;
int parentIndex;
while(currentIndex > 0){
parentIndex = (currentIndex - 1)/2;
if(((Comparable)(list.get(currentIndex))).compareTo(list.get(parentIndex)) > 0){
Object temp = list.get(currentIndex);
list.set(currentIndex,list.get(parentIndex));
list.set(parentIndex,temp);
}
else
{
break;
}
currentIndex = parentIndex;
}
}
public Object remove(){
if(list.size() == 0) return null;
Object removedObject = list.get(0);
list.set(0,list.get(list.size() - 1));
list.remove(list.size() - 1);
int currentIndex = 0;
while(currentIndex < list.size()){
int leftChildIndex = 2 * currentIndex;
int rightChildIndex = 2 * currentIndex + 1; if(leftChildIndex >= list.size()){
break;
}
int maxIndex = leftChildIndex;
if(rightChildIndex < list.size()){
if(((Comparable)(list.get(leftChildIndex))).compareTo(list.get(rightChildIndex)) < 0){
maxIndex = rightChildIndex;
}
}
if(((Comparable)(list.get(currentIndex))).compareTo(list.get(maxIndex))<0){
Object temp = list.get(currentIndex);
list.set(currentIndex,list.get(maxIndex));
list.set(maxIndex,temp);
currentIndex = maxIndex;
}
else{
break;
}
}
return removedObject;
}
public int getSize(){
return(list.size());
}
}
package com.liang.datastructures;
public class HeapSort {
public static void main(String[] args) {
Heap heap = new Heap(new Integer[]{2,3,1,4,7,9,8,6,5});
while(heap.getSize() > 0){
System.out.println(" "+heap.remove());
}
}
}
Result:
9
6
8
5
7
4
3
2
1
Parent index = (currentIndex )/2
leftChild Index = (2 * currentIndex + 1);
rightChildIndex = (2 * currentIndex + 2);
this is giving correct results
proof:
package com.liang.datastructures;
import java.util.ArrayList;
public class Heap {
private ArrayList list = new ArrayList();
public Heap(){
}
public ArrayList getList() {
return list;
}
public void setList(ArrayList list) {
this.list = list;
}
public Heap(Object []objects){
for(int i=0;i<objects.length;i++){
add(objects[i]);
}
}
public void add(Object obj){
list.add(obj);
int currentIndex = list.size() - 1;
int parentIndex;
while(currentIndex > 0){
parentIndex = currentIndex /2;
if(((Comparable)(list.get(currentIndex))).compareTo(list.get(parentIndex)) > 0){
Object temp = list.get(currentIndex);
list.set(currentIndex,list.get(parentIndex));
list.set(parentIndex,temp);
}
else
{
break;
}
currentIndex = parentIndex;
}
}
public Object remove(){
if(list.size() == 0) return null;
Object removedObject = list.get(0);
list.set(0,list.get(list.size() - 1));
list.remove(list.size() - 1);
int currentIndex = 0;
while(currentIndex < list.size()){
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
if(leftChildIndex >= list.size()){
break;
}
int maxIndex = leftChildIndex;
if(rightChildIndex < list.size()){
if(((Comparable)(list.get(leftChildIndex))).compareTo(list.get(rightChildIndex)) < 0){
maxIndex = rightChildIndex;
}
}
if(((Comparable)(list.get(currentIndex))).compareTo(list.get(maxIndex))<0){
Object temp = list.get(currentIndex);
list.set(currentIndex,list.get(maxIndex));
list.set(maxIndex,temp);
currentIndex = maxIndex;
}
else{
break;
}
}
return removedObject;
}
public int getSize(){
return(list.size());
}
}
package com.liang.datastructures;
public class HeapSort {
public static void main(String[] args) {
Heap heap = new Heap(new Integer[]{2,3,1,4,7,9,8,6,5});
while(heap.getSize() > 0){
System.out.println(" "+heap.remove());
}
}
}
Result:
9
8
7
6
5
4
3
2
1
In the book
Parent index = (currentIndex - 1)/2
leftChild Index = (2 * currentIndex);
rightChildIndex = (2 * currentIndex + 1);
this is giving wrong results
Proof:
but in actual it should be:
package com.liang.datastructures;
import java.util.ArrayList;
public class Heap {
private ArrayList list = new ArrayList();
public Heap(){
}
public ArrayList getList() {
return list;
}
public void setList(ArrayList list) {
this.list = list;
}
public Heap(Object []objects){
for(int i=0;i<objects.length;i++){
add(objects[i]);
}
}
public void add(Object obj){
list.add(obj);
int currentIndex = list.size() - 1;
int parentIndex;
while(currentIndex > 0){
parentIndex = (currentIndex - 1)/2;
if(((Comparable)(list.get(currentIndex))).compareTo(list.get(parentIndex)) > 0){
Object temp = list.get(currentIndex);
list.set(currentIndex,list.get(parentIndex));
list.set(parentIndex,temp);
}
else
{
break;
}
currentIndex = parentIndex;
}
}
public Object remove(){
if(list.size() == 0) return null;
Object removedObject = list.get(0);
list.set(0,list.get(list.size() - 1));
list.remove(list.size() - 1);
int currentIndex = 0;
while(currentIndex < list.size()){
int leftChildIndex = 2 * currentIndex;
int rightChildIndex = 2 * currentIndex + 1; if(leftChildIndex >= list.size()){
break;
}
int maxIndex = leftChildIndex;
if(rightChildIndex < list.size()){
if(((Comparable)(list.get(leftChildIndex))).compareTo(list.get(rightChildIndex)) < 0){
maxIndex = rightChildIndex;
}
}
if(((Comparable)(list.get(currentIndex))).compareTo(list.get(maxIndex))<0){
Object temp = list.get(currentIndex);
list.set(currentIndex,list.get(maxIndex));
list.set(maxIndex,temp);
currentIndex = maxIndex;
}
else{
break;
}
}
return removedObject;
}
public int getSize(){
return(list.size());
}
}
package com.liang.datastructures;
public class HeapSort {
public static void main(String[] args) {
Heap heap = new Heap(new Integer[]{2,3,1,4,7,9,8,6,5});
while(heap.getSize() > 0){
System.out.println(" "+heap.remove());
}
}
}
Result:
9
6
8
5
7
4
3
2
1
Parent index = (currentIndex )/2
leftChild Index = (2 * currentIndex + 1);
rightChildIndex = (2 * currentIndex + 2);
this is giving correct results
proof:
package com.liang.datastructures;
import java.util.ArrayList;
public class Heap {
private ArrayList list = new ArrayList();
public Heap(){
}
public ArrayList getList() {
return list;
}
public void setList(ArrayList list) {
this.list = list;
}
public Heap(Object []objects){
for(int i=0;i<objects.length;i++){
add(objects[i]);
}
}
public void add(Object obj){
list.add(obj);
int currentIndex = list.size() - 1;
int parentIndex;
while(currentIndex > 0){
parentIndex = currentIndex /2;
if(((Comparable)(list.get(currentIndex))).compareTo(list.get(parentIndex)) > 0){
Object temp = list.get(currentIndex);
list.set(currentIndex,list.get(parentIndex));
list.set(parentIndex,temp);
}
else
{
break;
}
currentIndex = parentIndex;
}
}
public Object remove(){
if(list.size() == 0) return null;
Object removedObject = list.get(0);
list.set(0,list.get(list.size() - 1));
list.remove(list.size() - 1);
int currentIndex = 0;
while(currentIndex < list.size()){
int leftChildIndex = 2 * currentIndex + 1;
int rightChildIndex = 2 * currentIndex + 2;
if(leftChildIndex >= list.size()){
break;
}
int maxIndex = leftChildIndex;
if(rightChildIndex < list.size()){
if(((Comparable)(list.get(leftChildIndex))).compareTo(list.get(rightChildIndex)) < 0){
maxIndex = rightChildIndex;
}
}
if(((Comparable)(list.get(currentIndex))).compareTo(list.get(maxIndex))<0){
Object temp = list.get(currentIndex);
list.set(currentIndex,list.get(maxIndex));
list.set(maxIndex,temp);
currentIndex = maxIndex;
}
else{
break;
}
}
return removedObject;
}
public int getSize(){
return(list.size());
}
}
package com.liang.datastructures;
public class HeapSort {
public static void main(String[] args) {
Heap heap = new Heap(new Integer[]{2,3,1,4,7,9,8,6,5});
while(heap.getSize() > 0){
System.out.println(" "+heap.remove());
}
}
}
Result:
9
8
7
6
5
4
3
2
1