Saturday, 28 September 2013

A small mistake in Liang book

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