Блог

Я пытаюсь представить, почему мой minHeapify is неправильно сортируется. Вот мой код:

 import java.util.List;
import java.util.ArrayList;

public class Heap {
    
    public void insert2(List<Integer> heap, int value) {
        if(heap.isEmpty()) {
            heap.add(value);
        }
        else {
            heap.add(value);
            for(int index = heap.size() / 2 - 1;index >= 0;index--) {
                minHeapify(heap, index);
            }
        }
    }
    
    public void minHeapify(List<Integer> heap, int index) {
        int smallest = index;
        int leftChildIndex = 2 * index   1;
        int rightChildIndex = 2 * index   2;
        
        if(leftChildIndex < heap.size() amp;amp; heap.get(leftChildIndex) < heap.get(smallest)) {
            smallest = leftChildIndex;
        }
        if(rightChildIndex < heap.size() amp;amp; heap.get(rightChildIndex) < heap.get(smallest)) {
            smallest = rightChildIndex;
        }
        if(smallest != index) {
            int temp  = heap.get(smallest);
            heap.set(smallest, heap.get(index));
            heap.set(index, temp);
            minHeapify(heap, smallest);
        }
    }
    
    public static void main(String[] args) {
        List<Integer> input2 = new ArrayList<Integer>();
        
        Heap heap2 = new Heap();
        heap2.insert2(input2, 3);
        heap2.insert2(input2, 4);
        heap2.insert2(input2, 48);
        heap2.insert2(input2, 9);
        heap2.insert2(input2, 5);
        heap2.insert2(input2, 2);
        
        System.out.println(input2);
    }

}

  

Вывод является [2, 4, 3, 9, 5, 48]

Выходные данные для минимальной кучи всегда должны быть отсортированы. Прав ли я в этом предположении и должно ли оно быть [2, 3, 4, 5, 9, 48] ?

Ваша реализация верна, и результат после ваших следующих шагов вставки соответствует действительности [2, 4, 3, 9, 5, 48] .

Выходные данные для минимальной кучи всегда должны быть отсортированы

Но вы получаете немного неправильное представление о MinHeap , то есть каждый узел меньше, чем его левый и правый дочерние узлы. НО правильный дочерний узел может быть больше, меньше, чем его брат, при условии, что он больше родительского.

Таким образом, представленная List часть вашей кучи не может быть отсортирована в правильном порядке.

https://www.geeksforgeeks.org/heap-data-structure/