DAA-삽입 방법

힙에 요소를 삽입하려면 처음에 새 요소가 배열의 마지막 요소로 힙 끝에 추가됩니다.

이 요소를 삽입 한 후 힙 속성이 위반 될 수 있으므로 추가 된 요소를 부모와 비교하고 추가 된 요소를 한 수준 위로 이동하여 위치를 부모와 교체하여 힙 속성을 복구합니다. 이 과정을percolation up.

상위 요소가 여과 요소보다 크거나 같을 때까지 비교가 반복됩니다.

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)

분석

처음에는 요소가 배열 끝에 추가됩니다. 힙 속성을 위반하면 요소가 부모와 교환됩니다. 나무의 높이는log n. 최고log n 여러 작업을 수행해야합니다.

따라서이 기능의 복잡성은 O(log n).

예

아래에 표시된 것처럼 새 요소 5를 추가해야하는 최대 힙을 고려해 보겠습니다.

처음에는이 배열 끝에 55 개가 추가됩니다.

삽입 후 힙 속성을 위반합니다. 따라서 요소는 부모와 교체해야합니다. 스왑 후 힙은 다음과 같습니다.

다시 말하지만, 요소는 힙의 속성을 위반합니다. 따라서 부모와 교체됩니다.

이제 멈춰야합니다.