힙의 삽입과 삭제

Question

첫째, 나는 힙에서 7을 삭제해야하고 그 후 17, 14

추가 문제는 내가 그 힙이 무엇인지 잘 모릅니다이다. 최소 힙입니까? 또는 이항 힙?

각 작업을 수행하는 방법을 설명 할 수 있습니까?

감사

Answer 1

힙 내부의 모든 요소는 단순히 마지막 잎으로를 교체 한 후 마지막 잎에 Heapify operation을 적용하여 O(logn)에서 삭제할 수 있습니다.

오른쪽 하단에있는 첫 번째 빈 리프에 새 노드를 추가 한 다음 해당 리프를 정리해야합니다.

Heapify : 오래는 부모가 아닌 작은하고 루트 아니므로 부모 노드와 :

• 반복적으로 ( 힙 조건을 위반하는 요소 일반) 새로운 요소를 교환한다.
• 새로운 요소가 leave 또는 both 자식 노드가 될 때까지 요소 자체보다 더 큰 값을 가진 자식 요소와 새로운 요소를 반복적으로 교환하십시오.