Tôi đã viết một bản triển khai java của một vùng heap tối đa bao gồm các nút chứa hai nội dung, một chuỗi và một giá trị kép có thể được truy cập từ mỗi nút. Chúng nên được chèn theo thứ tự giá trị kép của chúng. Tôi không chắc liệu việc chèn hoặc xóa của tôi có hoạt động không chính xác hay không, nhưng khi tôi cố gắng xóa năm giá trị lớn nhất đầu tiên khỏi vùng nhớ heap, tôi không nhận được kết quả mong muốn. Bạn có biết nấc cụt ở đâu không? Có các phương pháp như isfull và isempty để kiểm tra tình huống cơ bản xem nó trống hay đầy. Tất nhiên... Count là tổng số nút trong mảng (heap là một mảng).

chèn boolean công khai (Chuỗi W, gấp đôi R) {

    Từ HeapNode = HeapNode mới(W,R);
    nếu (isFull()){
        trả về sai;
    }
    khác {
        count++;
        đống[đếm - 1] = từ;
        siftUp(đếm - 1);
    }
    System.out.println("Đã thêm");
    trả về đúng sự thật;
}

boolean công khai siftUp(int place){

    int parentNode;
    HeapNode tmp;
    nếu (địa điểm != 0) {
        // nút cha của địa điểm
        //parentNode = getParentNode(địa điểm);
        parentNode = ((place-1) / 2);
        if (heap[parentNode].getDouble() < heap[place].getDouble()) {
              tmp = heap[parentNode];
              heap[parentNode] = heap[place];
              heap[place] = tmp;
              siftUp(parentNode);
        }
    }
    trả về đúng sự thật;
}

Đó là chèn, bây giờ là xóa:

HeapNode công khai xóa(){
    Giá trị tối đa của HeapNode;
    nếu (isEmpty()){
        return null;
    }
    khác{
        // Giá trị lớn nhất luôn nằm ở đâu? 
        maxValue = đống [0]; 

        // Giá trị nào sẽ lấy gốc cuối cùng? 

        đống[0] = đống[đếm-1]; 
        đếm--; ;

        // Bắt đầu thấm xuống chỉ mục gốc 
        lỗ int = 0; 

        int con; 
        HeapNode temp = heap[hole]; 

        while(lỗ * 2 + 1 < đếm) 
        { 
         // Chỉ số nút con trái của nút trong lỗ chỉ mục 
         con = 2 * lỗ + 1; 

         // tìm con lớn hơn
         if(child != count && (heap[child + 1].getDouble()) > (heap[child].getDouble())) 
            con++;//trao đổi chỉ mục

         if((heap[child].getDouble()) > (temp.getDouble())) // so sánh cuối cùng
            đống[lỗ] = đống[con];
         khác 
            phá vỡ; 

         lỗ = con; 
        } 
        đống [lỗ] = nhiệt độ; 
    }
    trả về giá trị tối đa;
}

Trường hợp thử nghiệm tôi đang sử dụng. Nhập các nút theo thứ tự này dựa trên các giá trị kép: 1.0, 0.8, 0.9, 0.8, 1.0, 0.6, 1.0, 1.0, 0.8, 1.0, 0.7, 1.0, 0.8 loại bỏ năm nút đầu tiên. Tôi sẽ nhận được tất cả 1.0? Tôi nhận được 1,0, 0,8, 1,0, 0,7, 1,0 là năm.

câu trả lời hay nhất

Tôi có thể tìm thấy 2 lỗi.

1. bạn có parentNode = (địa điểm/2);
   hiện hữu sàng lọc trong phương pháp. Rõ ràng, bạn đang sử dụng chỉ mục mảng dựa trên 0, vì vậy nút 0 phải có 1 và 2 là con, nhưng phương trình này cho 1 là cha của 2.
   thay đổi nó thành parentNode = ((place-1)/2);.

2. Một cái khác ở dòng tiếp theo:
   if (heap[parentNode].getDouble() > heap[place].getDouble()).
   Điều này sẽ đưa nút nhỏ nhất lên trên cùng thay vì nút lớn nhất.

Về java - chèn và xóa max heap java, chúng tôi đã tìm thấy một câu hỏi tương tự trên Stack Overflow: https://stackoverflow.com/questions/19897911/