최소 힙에 노드를 삽입하여 왼쪽 자식을 우선 순위 지정

Question

최소 힙 오른쪽에 메모를 삽입하는 코드를 얻은 후 노드의 왼쪽 자식에 우선 순위를 지정하려면 어떤 변경을해야하는지 혼란 스럽습니다. 힙을 다시 정렬합니다.

I 5 //insert number 5 in the Min Heap 
I 4 
I 3 
I 2 
I 1 

및 출력이되어야한다 : 대신 평소의

1 2 3 4 5 

이 출력하는 방법에 대한

1 2 4 5 3 

어떤 아이디어 입력은 같은 것입니까? 미리 감사드립니다.

Answer 1

힙 구조는 항목을 삽입하는 순서에 전적으로 의존합니다. 그 이유는 삽입 할 때 새 노드를 힙 끝 부분에 추가 한 다음 부모 포인터를 통해 위로 이동해야하기 때문입니다. 규칙은 다음과 같습니다.

1. 힙 끝에 항목을 추가하십시오.
2. 항목이 상위 항목보다 크거나 같으면 완료됩니다.
3. 항목을 상위 항목으로 바꿉니다.
4. 이동이 규칙을 감안할 때 2

에, 당신은 순서 [5,4,3,2,1]의 항목을 삽입 할 때의 일이 무엇인지를 살펴 보겠습니다.

[5] 
[5,4] // the new item is smaller than its parent, so swap 
[4,5] 
[4,5,3] // the new item is smaller than its parent, so swap 
[3,5,4] 
[3,5,4,2] // the new item is smaller than its parent, so swap 
[3,2,4,5] // still smaller than its parent 
[2,3,4,5] 
[2,3,4,5,1] // 1 is smaller than 3, so swap 
[2,1,4,5,3] // 1 is smaller than 2, so swap 
[1,2,4,5,3] 

특히 이진 힙에서 특정 하위 트리를 "우선 순위 지정"하는 효율적인 방법은 없습니다. 단지 5 개의 항목으로 힙에서 간단하게 보이지만 추가하는 모든 수준은 형제 노드를 적절한 순서로 유지하는 데 드는 비용을 증가시킵니다. 노드를 정렬하고 결과 배열에서 힙을 만드는 것이 좋습니다.

정렬 된 힙이별로 도움이되지 않습니다. 첫 번째 항목을 제거하자마자 힙을 다시 배열하면 더 이상 정렬되지 않습니다.