Chèn các phần tử vào Binary Min Heaps

Question

Nếu tôi chèn các mục: 10,12,14,1,6 vào heap nhỏ nhất một mục sau một kết quả khác như thế nào, vấn đề của tôi là sau

khi tôi bắt đầu tôi có:

10 

sau đó

10 
/
12 

sau đó

10 
/\ 
12 14 

sau đó

1 
/\ 
10 14 
/
12 

nhưng điều này là không đúng, vì vậy đúng cách để làm điều đó là gì? Lưu ý: đây là một câu hỏi về bài tập về nhà, tôi đang cố gắng hiểu khái niệm, nếu bạn không cảm thấy thoải mái khi giải quyết câu hỏi (dù sao thì đó không phải là câu hỏi đầy đủ), vui lòng cung cấp một ví dụ với vấn đề tương tự.

Answer 1

Bạn phải thêm phần tử mới dưới dạng con (hoặc lá chính xác) vào heap (không phải root), điều đó có nghĩa là bạn đặt nó ở vị trí đầu tiên "đúng" miễn phí (hoặc trong mảng heap của bạn) cuối cùng).

Sau đó, bạn phải thiết lập lại điều kiện heap, điều này được gọi là "heapify". Điều này xảy ra theo hai giai đoạn:

1. Lặp lại trao đổi phần tử mới (phần tử vi phạm điều kiện heap) với nút cha của nó miễn là nút gốc nhỏ hơn gốc và không phải là gốc.
2. Lặp lại trao đổi phần tử mới với con có giá trị nhỏ nhất, cho đến khi phần tử mới trở thành một phần còn lại hoặc cả hai nút con lớn hơn chính phần tử đó.

Điều đó có nghĩa

10 
/\ 
12 14 

+ 1 dẫn đến

10 
/\ 
12 14 
/
1 

Và đó vi phạm các điều kiện heap, vì vậy bạn phải heapify

10 
/\ 
    1 14 
/
12 

Nhưng điều này vẫn không phải là đúng, vì vậy bạn phải heapify một lần nữa

 1 
/\ 
10 14 
/
12 

Và có bạn là ... tất cả mọi thứ OK bây giờ :-)

Answer 2

step1:  10 
step2:  10 
     /
     12 
step3:  10 
     /\ 
     12 14 
step4:  1 
     /\ 
     10 12 
     /
     14 
step5:  1 
     /\ 
     6 10 
     /\ 
     12 14