Heap data structure drag method

Question

I am working on my task, which is to read from a text file, store the first 10 words on the heap. Then continue reading from the text file, and if the word is smaller than the root of the heap, replace it and drag the whole heap. My code seems to work for the most part, but I am facing a few problems.

• Some words, even if they are less than the root, do not change places.
• Duplicate words

I have to get a bunch 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:

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

Answer 1

If you use this kind of indexing, you will not get a binary tree:

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

I think you wanted 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 the repeating elements, as far as I know, the heap can contain duplicates and does not support duplicate removal. For example, this is a valid bunch of numbers

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