순서

Question

에 다음과 같은 요소를 삽입하여 힙을 만들기 질문 :

들이 주어진 순서대로 다음과 같은 요소를 삽입하여 힙을 만듭니다. 각 삽입 및 물방울 후 힙을 표시하십시오. (힙은 상단에있는 가장 높은 키 값을 유지하기 위해 구현해야합니다.)

5 4 6 7 9 8 1 2 3 

당신은 힙 작성이 완료되면, 그것에서 각 요소를 제거합니다. 각 제거 및 물방울 후 힙을 표시하십시오. 단계에서 제거 된 요소를 나타냅니다.

요소를 힙에 삽입하는 방법은 알고 있지만 어떻게 작성합니까? 그리고 정말 힙에서 요소를 제거하는 방법을 모르겠습니다.

Answer 1

내 대답을 바이너리 힙을 가정합니다, 거기에 여러 가지 힙 있지만,이 숙제 같은 소리와 상당히 기본적인 질문이기 때문에 나는이 가장 기본적인 힙을 포함 줘야 :

음, 먼저 힙이 비어 있습니다.

은 그런 다음 5를 삽입, 그래서 힙은 지금 :

5 

는 그런 다음 하단에 4를 삽입합니다. 4는 5보다 작으므로 부모와 함께 위치를 변경하지 않습니다. 힙은 지금 :

5 
/
4 

그런 다음 우리가 (왼쪽에서 오른쪽으로 항상 하단에 삽입) 5 이하, 하단에 (6)를 삽입합니다.

이

6 
/\ 
4 5 

이제 우리는 (다음 사용 가능한 지점에 7 삽입 : 우리는 그것 (5) 그 부모와 함께 새로 삽입 된 노드 (6)의 값을 비교하고 우리가 그들을 교체해야 실현, 힙 속성을 위반하지합니다) 4 아래에, 그리고 부모 7> 4. 그런 다음 우리는 교환 때문에이기로 교체 (또는 세류) 다시 7> 6으로 얻을 :

7 
/\ 
    6 5 
/
4 

등등 ...