MinHeapify 打印不正确的值

Question

我正在尝试想象为什么我的 minHeapify 排序不正确。这是我的代码：

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() && heap.get(leftChildIndex) < heap.get(smallest)) {
            smallest = leftChildIndex;
        }
        if(rightChildIndex < heap.size() && 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] 吗？

Answer 1

您的实现是正确的，您执行以下插入步骤后的结果确实是 [2, 4, 3, 9, 5, 48]。

The output for min heap should be always sorted

但是你对MinHeap的理解有点错误，即每个节点都小于它的左右子节点。但是右子节点可以比它的兄弟节点大，也可以小于它的兄弟节点，只要比它的父节点大。

因此您的堆的 List 无法按正确顺序排序。

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

MinHeapify 打印不正确的值

MinHeapify printing incorrect value

java

sorting

algorithm

heap