Метод кучи структуры данных кучи

Question

Я работаю над своим назначением, которое должно читать из текстового файла, хранить первые 10 слов в куче. Затем продолжайте читать из текстового файла, и если слово меньше корня кучи, замените его и перетащите всю кучу. Мой код, похоже, работает по большей части, но я сталкиваюсь с несколькими проблемами.

• Некоторые слова, даже если они меньше корня не выгружена
• Повторяющиеся слова

Я должен закончить с кучей, содержащей слова abandoning abandons abased abash abashed abashes abasing abate abatement abbe

Однако я получить слова, abashes abashed abash abased abandons abandoning bewilderedly abandoning armful abandoning

---

Вот мой код до сих пор:

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

Вы не получите бинарное дерево, если вы используете такую ​​индексацию:

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

Я думаю, что вы имели в виду, чтобы написать это:

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

Таким образом, дерево будет выглядеть так:

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

Что касается повторяющихся элементов, насколько я знаю, куча может содержать дубликаты и не поддерживает дублирование удаления. Например, это действительная куча чисел

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