CODEWITHSUNDEEP
javadata-structures
user2593573
user2593573

Reputation:

Heap Data-Structure Re-Heap Method

I'm working on my assignment, which is to read from a text file, store the first 10 words in a heap. Then continue to read from the text file and if the word is less than the root of the heap, to replace it and re-heap the entire heap. My code seems to be working for the most part however I am running into a few problems.

I am supposed to end up with a heap containing the words abandoning abandons abased abash abashed abashes abasing abate abatement abbe

However I get the words, abashes abashed abash abased abandons abandoning bewilderedly abandoning armful abandoning

Here is my code so far:

public static void readFile() {
    BufferedReader reader;
    String inputLine;
    int counter = 0;

    try {
        reader = new BufferedReader(new FileReader(".\\src\\dictionary.txt"));
        while((inputLine = reader.readLine()) != null) {
            if(counter < 10) {
                heap.insert(inputLine);
                counter++;
            }

            if(inputLine.compareTo(heap.find(0)) < 0) {
                heap.change(0, inputLine);
            }
        }
    } catch (IOException e) {
        System.out.println("Error: " + e);
    }
}

public boolean insert(String value) {
    if(currentSize == maxSize) { return false; }

    Node newNode = new Node(value);
    heap[currentSize] = newNode;
    trickleUp(currentSize++);
    return true;
}

public void trickleUp(int index) {
    int parent = (index - 1) / 2;
    Node bottom = heap[index];

    while(index > 0 && heap[parent].getData().compareTo(bottom.getData()) < 0) {
        heap[index] = heap[parent];
        index = parent;
        parent = (parent - 1) / 2;
    }
    heap[index] = bottom;
}

public void trickleDown(int index) {
    int largerChild;
    Node top = heap[index];

    while(index < currentSize / 2) {
        int leftChild = 2 * index + 1;
        int rightChild = index + 1;

        if(rightChild < currentSize && heap[leftChild].getData().compareTo(heap[rightChild].getData()) < 0) {
            largerChild = rightChild;
        } else {
            largerChild = leftChild;
        }

        if(top.getData().compareTo(heap[largerChild].getData()) > 0) {
            break;
        }

        heap[index] = heap[largerChild];
        index = largerChild;
    }
    heap[index] = top;
}

public boolean change(int index, String newValue) {
    if(index < 0 || index >= currentSize) { return false; }

    String oldValue = heap[index].getData();
    heap[index].setData(newValue);

    if(oldValue.compareTo(newValue) < 0) {
        trickleUp(index);
    } else {
        trickleDown(index);
    }
    return true;
}

Upvotes: 4

Views: 3939

Answers (1)

Fefer_Ivan
Fefer_Ivan

Reputation: 116

You won't get binary tree if you use such indexing:

    int leftChild = 2 * index + 1;
    int rightChild = index + 1;

I think you meant to write this:

    int leftChild = 2 * index + 1;
    int rightChild = 2 * index + 2;

So the tree will look like this

       0
     /   \
    1     2
   / \   / \
  3   4 5   6 
 / \
7   8 ... and so on

As for duplicate elements as far as I know heap can contain duplicates and does not support duplicate removal. For example this is a valid heap of numbers

      10
    /    \
   9      8
  / \    / \
 5   7  7   6

Upvotes: 1

Related Questions