전체 이진 최소 힙 이동

Question

노드가 항상 오름차순이되도록 아래의 트리 구조를 탐색하는 방법을 모르겠습니다. 나는이 표현에 대응을 생각 배열 [0 1 3 2 5 4 7 9 6 8]의 배열 [9 8 7 6 5 4 3 2 1 0] 결과를 Heapifying :

(나중에 효율적으로 삽입을 원하기 때문에) 내가 효율적으로 그것을 통과 할 수있는 방법이기 때문에 배열을 유지 싶은

오름차순? (노드를이 순서로 방문하고 있습니다. [0 1 2 3 4 5 6 7 8 9])

Answer 1

배열을 정렬하면됩니다. 이후에는 최소 힙이 될 것이고 다른 알고리즘은 점근 적으로 더 효율적이지는 않습니다.

Answer 2

실제로 오히려 제안 것 self-balancing 여기 binary search tree (BST) :

이진 검색 트리 (BST) ... 다음과 같은 속성이있는 노드 기반의 이진 트리 데이터 구조입니다 :

을
• 노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드 만 포함됩니다.
• 노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드 만 포함됩니다.
• 왼쪽 및 오른쪽 하위 트리 각각은 이진 검색 트리 여야합니다.
• 중복 노드가 없어야합니다.

그것은 정렬 된 순서에서 BST를 통과하는 효율적인 공간 간단하고 더 힙으로 이렇게보다 (A가에 차 통과 소위).

BST는 O (log n) 삽입 및 O (n) 통과를 지원합니다.

트래버스를 다시하기 전에 많은 수의 삽입을 수행하는 경우, 트래버스하기 전에 정렬로 배열을 정렬하는 것이 더 효율적일 수 있습니다. - 관련 실행 시간은 삽입의 경우 O (1)이고 삽입의 경우 O (n log n) 정렬 된 순서를 얻으려면이 옵션이 BST를 사용하는 것보다 효율적이되는 정확한 지점을 벤치마킹해야합니다. 호기심을 위해서

---

, 여기 당신이, 당신이 알고있는 경우에, (정렬 된 순서로 힙을 통과 아마 간단하다, 빈 때까지 단지 힙에서 최소를 제거하는 유지하고 싶지 않은 방법 옵션은 최소값을 제거하는 것이 힙의 표준 연산이기 때문에).

힙의 속성에서, 왼쪽 하위 트리에있는 요소가 멈추거나, 오른쪽 하위 요소가 뒤 따르거나, 왼쪽 요소가 다시 왼쪽 요소가되는 등의 요소가 없습니다. 즉, 왼쪽 하위 트리를 완전히 완성한 다음 오른쪽에서 시작하십시오. 이렇게하면 메모리에 많은 힙을 유지해야 할 수도 있습니다.

주요 아이디어는 요소가 항상 양쪽 자식보다 작다는 사실에 기반합니다.새로운 힙이 있지만

새로운 힙

에 원래 힙의 루트를 삽입

• 힙 만들기 (또 다른) :이를 바탕으로
  , 우리는 다음과 같은 알고리즘을 구성 할 수 요소 :
• 가 추가 요소
• 출력 힙에서
  • 제거 최소 그 어떤 경우 원래 힙 그 요소의 자식은 새로운 힙

이는 (참조를 위해 BST 통과 소요 시간 O (N)의 공간 (N 로그 n) O 소요 O (log n) space), 추가 된 코드 복잡성은 말할 것도 없습니다.

Answer 3

BST를 트래버스 할 수있는 것과 같은 의미로 힙을 트래버스 할 수 없습니다. 정렬 된 순회가 중요한 작업 인 경우 @Dukeling은 더 나은 선택 인 BST에 대해 옳습니다. 그러나 O (1) 추가 공간이 필요한 다음 알고리즘을 사용할 수 있습니다.

일반적인 배열 형태로 힙이 있다고 가정합니다.

1. 항목을 정렬 순서대로 한 번에 하나씩 제거하여 순회를 위해 "방문"하십시오.
2. i 번째 항목을 방문한 후 힙에 현재 사용되지 않는 위치 n-i의 힙 배열에 다시 놓습니다 (0부터 시작하는 배열 인덱스라고 가정).
3. 새 힙을 만들기 위해 순회 배열을 순회 한 후.

항목을 제거하려면 O (n log n) 시간이 필요합니다. 반전은 또 다른 O (n)입니다.

끝까지 탐색 할 필요가 없으면 언제든지 중지하고 O (n) heapify 작업을 실행하여 배열을 "수정"할 수 있습니다. 예를 들어 pseudocode here을 참조하십시오.