DAA - Phương pháp Chèn

Để chèn một phần tử trong một đống, phần tử mới ban đầu được nối vào cuối đống như là phần tử cuối cùng của mảng.

Sau khi chèn phần tử này, thuộc tính heap có thể bị vi phạm, do đó, thuộc tính heap được sửa chữa bằng cách so sánh phần tử đã thêm với phần tử gốc của nó và di chuyển phần tử đã thêm lên một cấp, hoán đổi vị trí với phần tử chính. Quá trình này được gọi làpercolation up.

Phép so sánh được lặp lại cho đến khi phần tử gốc lớn hơn hoặc bằng phần tử tô màu.

Algorithm: Max-Heap-Insert (numbers[], key) 
heapsize = heapsize + 1 
numbers[heapsize] = -∞ 
i = heapsize 
numbers[i] = key 
while i > 1 and numbers[Parent(numbers[], i)] < numbers[i] 
   exchange(numbers[i], numbers[Parent(numbers[], i)]) 
   i = Parent (numbers[], i)

Phân tích

Ban đầu, một phần tử đang được thêm vào cuối mảng. Nếu nó vi phạm thuộc tính heap, phần tử sẽ được trao đổi với cha của nó. Chiều cao của cây làlog n. Tối đalog n số lượng hoạt động cần được thực hiện.

Do đó, độ phức tạp của chức năng này là O(log n).