[algorithm] 힙을 어떻게 복잡하게 만들 수 있습니까?

이 주제에 묻힌 몇 가지 질문이 있다고 생각합니다.

• O (n) 시간에 buildHeap실행되도록 어떻게 구현 합니까?
• 올바르게 구현했을 때 O (n) 시간에 buildHeap실행되는 것을 어떻게 표시 합니까?
• 힙 정렬 이 O (n log n)가 아닌 O (n) 시간에 실행되도록 동일한 논리가 작동하지 않는 이유는 무엇 입니까?

O (n) 시간에 buildHeap실행되도록 어떻게 구현 합니까?

종종,이 질문에 대한 대답의 차이에 초점을 siftUp하고 siftDown. 사이의 올바른 선택을 siftUp하고하는 것은 siftDown얻는 것이 중요합니다 O (n)의 성능을 buildHeap하지만, 도움의 일에 아무 차이 이해하지 않습니다 buildHeap및 heapSort일반적입니다. 사실, 모두의 적절한 구현 buildHeap과 heapSort것이다 에만 사용 siftDown. siftUp가 예를 들어, 이진 힙을 사용하여 우선 순위 큐를 구현하는 데 사용 될 수 있도록 운영은 기존 힙에 삽입을 수행하기 위해 필요합니다.

최대 힙 작동 방식을 설명하기 위해 이것을 작성했습니다. 이는 일반적으로 힙 정렬 또는 높은 값이 높은 우선 순위를 나타내는 우선 순위 큐에 사용되는 힙 유형입니다. 최소 힙도 유용합니다. 예를 들어, 정수 키가있는 항목을 오름차순으로 검색하거나 문자열을 알파벳 순서로 검색 할 때. 원칙은 동일합니다. 정렬 순서를 전환하기 만하면됩니다.

힙 속성 을 지정 이진 힙의 각 노드는 적어도 그 아이 모두 큰대로해야한다는. 특히 이것은 힙에서 가장 큰 항목이 루트에 있음을 의미합니다. 시프 팅 다운 및 시프 팅은 기본적으로 반대 방향으로 동일한 작업입니다.

• siftDown 하위 노드가 너무 커질 때까지 하위 노드가 너무 큰 노드를 가장 큰 하위 노드로 바꿉니다 (아래로 이동).
• siftUp 위의 노드보다 크지 않을 때까지 상위 노드와 너무 큰 노드를 교체 (위로 이동)합니다.

연산의 수는 필요 siftDown하고 siftUp, 노드가 이동할 수있는 거리에 비례한다. 의 경우 siftDown, 트리의 맨 아래까지의 거리이므로 트리 siftDown의 맨 위에있는 노드의 경우 비용이 많이 듭니다. 을 사용 siftUp하면 작업이 트리의 상단까지의 거리에 비례하므로 트리 siftUp의 하단에있는 노드의 경우 비용이 많이 듭니다. 최악의 경우 두 작업이 모두 O (log n) 이지만 힙에서는 하나의 노드 만 맨 위에 있고 반면에 절반은 맨 아래 레이어에 있습니다. 따라서 모든 노드에 작업을 적용해야하는 경우 siftDownover를 선호한다는 것은 놀라운 일이 아닙니다 siftUp.

이 buildHeap함수는 정렬되지 않은 항목의 배열을 가져 와서 모두 힙 특성을 충족 할 때까지 이동하여 유효한 힙을 생성합니다. 위에서 설명한 및 작업 을 buildHeap사용하기 위해 취할 수있는 두 가지 방법이 있습니다 .siftUpsiftDown

1. 힙 상단 (어레이의 시작)에서 시작 siftUp하여 각 항목을 호출 합니다. 각 단계에서 이전에 선별 된 항목 (배열에서 현재 항목 이전의 항목)은 유효한 힙을 형성하고 다음 항목을 선별하면 힙에서 유효한 위치에 배치됩니다. 각 노드를 선별 한 후 모든 항목이 힙 특성을 충족시킵니다.

2. 또는 반대 방향으로 이동하십시오. 어레이의 끝에서 시작하여 앞쪽으로 뒤로 이동하십시오. 반복 할 때마다 올바른 위치에 놓일 때까지 항목을 분류합니다.

어떤 구현 buildHeap이 더 효율적입니까?

이 두 가지 솔루션 모두 유효한 힙을 생성합니다. 당연히 더 효율적인 방법은를 사용하는 두 번째 작업입니다 siftDown.

하자 H = 로그를 N 힙의 높이를 나타냅니다. siftDown접근에 필요한 작업 은 합계로 제공됩니다.

(0 * n/2) + (1 * n/4) + (2 * n/8) + ... + (h * 1).

합계의 각 항에는 주어진 높이에서 노드가 이동해야하는 최대 거리 (하단 레이어의 경우 0, 루트의 경우 h)에 해당 높이의 노드 수를 곱한 값이 있습니다. 반대로 siftUp각 노드 에서 호출하는 합계 는

(h * n/2) + ((h-1) * n/4) + ((h-2)*n/8) + ... + (0 * 1).

두 번째 합계가 더 큽니다. 첫 번째 항만 hn / 2 = 1/2 n log n이므로이 방법은 최상의 O (n log n) 복잡성을 갖습니다 .

siftDown접근법 의 합 이 실제로 O (n) 임을 어떻게 증명할 수 있습니까?

한 가지 방법 (작동하는 다른 분석도 있음)은 유한 합계를 무한 계열로 변환 한 다음 Taylor 계열을 사용하는 것입니다. 첫 번째 용어 인 0을 무시할 수 있습니다.

각 단계가 왜 작동하는지 확실하지 않은 경우 다음과 같이 프로세스에 대한 정당화가 있습니다.

• 항은 모두 양수이므로 유한 합은 무한 합보다 작아야합니다.
• 이 계열은 x = 1 / 2로 평가 된 검정력 계열과 같습니다 .
• 이 검정력 계열은 f (x) = 1 / (1-x) 에 대한 Taylor 계열의 도함수와 같습니다 (상수 ) .
• x = 1 / 2 는 해당 Taylor 계열의 수렴 간격 내에 있습니다.
• 따라서 Taylor 계열을 1 / (1-x)로 바꾸고 , 차별화하여 평가하여 무한 계열의 값을 찾을 수 있습니다.

무한 합은 정확히 n 이므로 유한 합은 더 크지 않으므로 O (n) 입니다.

힙 정렬에 O (n log n) 시간이 필요한 이유는 무엇 입니까?

buildHeap선형 시간 으로 실행할 수 있다면 왜 힙 정렬에 O (n log n) 시간이 필요합니까? 힙 정렬은 두 단계로 구성됩니다. 먼저 buildHeap배열 을 호출 하는데, 최적으로 구현 된 경우 O (n) 시간 이 필요합니다 . 다음 단계는 힙에서 가장 큰 항목을 반복적으로 삭제하여 배열의 끝에 배치하는 것입니다. 힙에서 항목을 삭제하기 때문에 힙을 종료 한 직후에는 항목을 저장할 수있는 열린 지점이 항상 있습니다. 따라서 힙 정렬은 다음으로 큰 항목을 연속적으로 제거하고 마지막 위치에서 시작하여 앞쪽으로 이동하여 배열에 배치하여 정렬 된 순서를 달성합니다. 힙 정렬에서 지배하는 것은이 마지막 부분의 복잡성입니다. 루프는 이것을 좋아합니다 :

for (i = n - 1; i > 0; i--) {
    arr[i] = deleteMax();
}

분명히 루프는 O (n) 번 실행됩니다 ( 정확하게하려면 n-1 , 마지막 항목은 이미 제자리에 있음). deleteMax힙 의 복잡도 는 O (log n) 입니다. 일반적으로 루트 (힙에 남아있는 가장 큰 항목)를 제거하고 힙에있는 마지막 항목 (잎) 인 가장 작은 항목 중 하나로 대체하여 구현됩니다. 이 새로운 루트는 힙 속성을 거의 확실히 위반하므로 siftDown다시 허용 가능한 위치로 이동할 때까지 호출해야합니다 . 이것은 또한 다음으로 큰 항목을 루트까지 이동시키는 효과가 있습니다. 트리의 맨 아래에서 buildHeap호출하는 대부분의 노드의 위치 와 달리 siftDown이제는 호출siftDown 각 반복의 트리의 상단에서!나무는 줄어들지 만 충분히 빨리 줄어들지 않습니다 . 나무의 높이는 노드의 전반부를 제거 할 때까지 (하단 레이어를 완전히 지울 때) 일정하게 유지됩니다. 그런 다음 다음 분기의 높이는 h-1 입니다. 이 두 번째 단계의 총 작업은

h*n/2 + (h-1)*n/4 + ... + 0 * 1.

스위치를 확인하십시오. 이제 제로 작업 사례는 단일 노드에 해당 하고 h 작업 사례는 노드의 절반에 해당합니다. 이 합은 siftUp을 사용하여 구현 되는 비효율적 인 버전과 마찬가지로 O (n log n)buildHeap 입니다. 그러나이 경우 정렬을 시도하고 있으므로 다음으로 큰 항목을 제거해야하므로 선택의 여지가 없습니다.

요약하면 힙 정렬 작업은 두 단계의 합입니다. buildHeap의 O (n) 시간과 O (n log n)는 각 노드를 순서대로 제거 하므로 복잡도는 O (n log n) 입니다. 당신은 (정보 이론의 일부 아이디어를 사용하여) 비교 기반 정렬의 경우 O (n log n) 이 어쨌든 기대할 수있는 최선임을 증명할 수 있으므로 이것에 실망하거나 힙 정렬을 기대할 이유가 없습니다. O (N) 시간은 결합 buildHeap한다.

답변

Green  = n/2^1 * 0 (no iterations since no children)
red    = n/2^2 * 1 (heapify will perform atmost one swap for each red node)
blue   = n/2^3 * 2 (heapify will perform atmost two swaps for each blue node)
purple = n/2^4 * 3 (heapify will perform atmost three swaps for each purple node)

->(n/2^1 * 0) + (n/2^2 * 1)+ (n/2^3 * 2) + (n/2^4 * 3) +...+ (n/2^(h+1) * h)
-> n * ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) )

-> ( 0 + 1/4 + 2/8 + 3/16 +...+ h/2^(h+1) )