최소 힙

최소 힙
최소 힙
유형	바이너리 트리 / 바이너리
발명된	1986
빅 O 표기의 시간 복잡도
알고리즘.
알고리즘.
삽입
삭제

컴퓨터 과학에서 min-max 힙은 min-heap과 max-heap의 유용성을 결합한 완전한 이진수 트리 데이터 구조이다. 즉,^[2] 최소 및 최대 요소 모두의 지속적인 시간 검색과 로그 시간 제거를 제공한다.이를 통해 min-max 힙은 이중 엔드 priority 큐를 구현하기 위한 매우 유용한 데이터 구조가 됩니다.min-max 힙은 이진수 최소 힙 및 최대 힙과 마찬가지로 로그 삽입 ^[3]및 삭제를 지원하며 선형 시간으로 구축할 수 있습니다.min-max 힙은 종종 암묵적으로 ^[4]배열에 표현되므로 암묵적 데이터 구조라고 합니다.

min-max 힙 속성은 다음과 같습니다.트리의 짝수 레벨의 각 노드가 하위 노드보다 작은 반면 트리의 홀수 레벨의 각 노드는 하위 ^[4]노드보다 큽니다.

또한 다음과 같은 다른 주문 통계 작업을 효율적으로 지원하기 위해 구조를 일반화할 수 있습니다.find-median,delete-median,^[2]find(k)(구조에서 k번째로 작은 값을 구함) 및 연산delete(k)(구조에서 k번째 최소값 삭제), k의 고정값(또는 값 집합)에 대해.이 마지막 두 연산은 각각 상수 시간과 로그 시간으로 구현할 수 있습니다.최소-최대 순서의 개념은 최대 또는 최소 순서에 기반한 다른 구조(예: 왼쪽 트리)로 확장되어 새로운(그리고 더 강력한) 데이터 ^[4]구조를 생성할 수 있습니다.min-max 힙은 외부 QuickSort를 ^[5]구현하는 경우에도 유용합니다.

묘사

min-max 힙은 최소(또는 짝수)와 최대(또는 홀수) 수준을 번갈아 포함하는 완전한 이진 트리입니다.짝수 레벨은 예를 들어 0, 2, 4 등이고 홀수 레벨은 각각 1, 3, 5 등입니다.다음 포인트에서는 루트 요소가 첫 번째 레벨, 즉 0에 있다고 가정합니다.

Min-max 힙의 예

min-max 힙의 각 노드에는 데이터 멤버(통상은 키라고 불립니다)가 있으며, 이 값은 min-max 힙의 노드 순서를 결정하기 위해 사용됩니다.
루트 요소는 min-max 힙에서 가장 작은 요소입니다.
두 번째 레벨의 두 가지 요소 중 하나인 최대(또는 홀수) 레벨은 최소-최대 힙에서 가장 큰 요소입니다.
x $(\displaystyle$ x $)$ 를 $x$ min-max 힙의 임의의 노드라고 $합니다$ .
- $x$ {\ $displaystyle$ x $}$ 가 $x$ 최소(또는 짝수) 수준인 $경우$ x. $k$ e $y$ {\ $displaystyle$ x. $key}$ 는 $x.key$ 루트 $x$ {\ $displaystyle$ x $x$ 를 가진 서브트리의 모든 키 중 최소 키입니다.
- x{\ $displaystyle$ x $}$ 가 $x$ 최대(또는 홀수) 수준인 $경우$ x. $k$ e $y$ {\ $displaystyle$ x. $key}$ 는 $x.key$ $루트$ x {\ $displaystyle$ x $x$ 를 가진 서브트리의 모든 키 중 최대 키입니다.
최소(최대) 수준의 노드를 최소(최대) 노드라고 합니다.

max-min 힙은 유사하게 정의됩니다.이러한 힙에서는 최대값이 루트에 저장되고 최소값이 루트의 ^[4]자녀 중 하나에 저장됩니다.

운용

다음 조작에서는 min-max 힙이 배열로 표현된다고 가정합니다.A[1..N]; 어레이 $내$ 의\ $displaystyle i\$ displaystyle $ith$ $i\log$ i $\rfloor}$ 레벨에 $\lfloor \log i\rfloor$ 있는 $\lfloor \log i\rfloor$ 에 $ith$ 합니다 $\lfloor \log i\rfloor$

빌드

min-max 힙 생성은 Floyd의 선형 시간 힙 구성 알고리즘을 적용하여 이루어집니다. 이 알고리즘은 상향식으로 ^[4]진행됩니다.Floyd의 일반적인 빌드히프^[6] 알고리즘은 다음과 같습니다.

함수 FLOID-BUILD-HEAP(h): 각 인덱스 i에 대해 $\lfloor length(h)/2\rfloor$  l  $\lfloor length(h)/2\rfloor$   $\lfloor length(h)/2\rfloor$   $\lfloor length(h)/2\rfloor$  t $\lfloor length(h)/2\rfloor$  ( $\lfloor length(h)/2\rfloor$ ) /  $\lfloor length(h)/2\rfloor$   ${\$  {  $displaystyle \lfloor$ (  $h$ ) /  $2$ \  $rfloor$ }에서1 $\lfloor length(h)/2\rfloor$  do : push-down ( h , i )rfloor return h

이 함수에서 h는 초기 배열입니다.이 배열의 요소는 min-max 힙속성에 따라 정렬되지 않을 수 있습니다.그push-down다음으로 min-max 힙의 동작(히피라고도 불립니다)에 대해 설명합니다.

푸시 다운

그push-down알고리즘(또는trickle-down에 기재되어 있는 것은, 다음과 같습니다.

PUSH-DOWN(h, i): i가 최소 수준일 경우: PUSH-DOWN-MIN(h, i) 기타: PUSH-DOWN-MAX(h, i) endif

최소 푸시 다운

기능 PUSH-DOWN-MIN(h, i): 된 다음 아이들이 있습니다. m:제가 가장 작은 아이나 손자)지수는 만약 m은 손자:만약 h[m]<> 다음 h[나는]:스왑 h[m]과 h[나는]만약 h[m]> 다음 h[부모(m)]:스왑 h[m]과 h[부모(m)]endif PUSH-DOWN-MIN(h, m) 다른 endif 만약 h[m]<>;h[나는].n:endif를 h[m]와 h[i]로 바꿉니다.

최대 푸시 다운

의 알고리즘push-down-maxpush-down-min과 동일하지만 모든 비교 연산자가 반전됩니다.

기능 PUSH-DOWN-MAX(h, i): 된 다음 아이들이 있습니다. m:제가 가장 큰 아이나 손자)지수는 만약 m은 손자:만약 h[m]> 다음 h[나는]:스왑 h[m]과 h[나는]만약 h[m]<> 다음 h[부모(m)]:스왑 h[m]과 h[부모(m)]endif PUSH-DOWN-MAX(h, m)endif 다른 만약 h[m]>h[나는].:endif를 h[m]와 h[i]로 바꿉니다.

반복 양식

재귀 콜로서push-down-min그리고.push-down-max테일 위치에 있는 경우, 다음 기능은 일정한 공간에서 실행되는 순수 반복 형식으로 변환할 수 있습니다.

함수 PUSH-DOWN-MIN-ITER(h,m): m에 자녀가 있는 경우: i : = m : = 가장 작은 아이 또는 i의 손자의 인덱스: h [m] < h [ i ]그러면: m이 i의 손자인 경우 h [m] 및 h [i ]를 스왑합니다.

삽입

요소를 min-max 힙에 추가하려면 다음 작업을 수행합니다.

필요한 키를 min-max 힙을 나타내는 배열(끝)에 추가합니다.이로 인해 min-max 힙 속성이 파손될 수 있으므로 힙을 조정해야 합니다.
새 키를 부모 키와 비교합니다.
1. 부모 노드보다 작은(큰) 것으로 판명된 경우 힙 루트에 대한 경로에 있는 최대(최소) 레벨의 다른 모든 노드보다 작은(큰) 것이 확실합니다.이제 최소(최대) 수준에서 노드를 확인합니다.
2. 새 노드에서 루트까지의 경로(최소(최대) 수준만 고려)는 삽입 전과 마찬가지로 내림차순(오름차순)이어야 합니다.따라서 이 시퀀스에 새로운 노드를 바이너리 삽입해야 합니다.기술적으로 새 노드를 부모 노드와 스왑하는 것이 더 간단하지만 부모가 더 크거나 더 작습니다.

이 프로세스는, 다음의 콜에 의해서 실장됩니다.push-up새로 추가된 키의 인덱스에 대해 다음에 설명하는 알고리즘입니다.

푸시업

그push-up알고리즘(또는bubble-up에 기재되어 있는 것은, 다음과 같습니다.

PUSH-UP(h, i): i가 루트가 아닌 경우: i가 최소 수준인 경우: h[i]> h[parent(i)]의 경우: h[i]와 h[parent(i)]의 PUSH-UP-MAX(h, parent(i) 이외의 경우: h-UPH-UP-MIN(h, i)의 경우.기타: PUSH-UP-MAX(h, i) endif endif endif

최소 푸시업

PUSH-UP-MIN(h, i): 조부모가 있고 h[i] < h [ grandparent （ i ） ][ grandparent （ i ） ]PUSH-UP-MIN(h, grandparent （ i ） end:

최대 푸시업

와 마찬가지로push-down조작,push-up-max와 동일하다push-up-min단, 비교 연산자가 반전된 경우:

PUSH-UP-MAX(h, i): 조부모가 있고 h[i]> h[grandparent(i)]인 경우: 다음과 같이 swap h[i]와 h[grandparent(i)] PUSH-UP-MAX(h, grandparent(i)엔드를 바꿉니다.

반복 양식

재귀 콜로서push-up-min그리고.push-up-max테일 위치에 있는 경우, 이러한 기능은 일정 공간에서 실행되는 순수 반복 형식으로 변환할 수도 있습니다.

PUSH-UP-MIN-ITER(h, i): 조부모와 h[i]< h[투명(i)]가 있는 동안: i:=할아버지(i)가 끝나는 동안

예

다음으로 요소를 Min-Max 힙에 삽입하는 예를 제시하겠습니다.

다음과 같은 최소 최대 힙이 있으며 값이 6인 새 노드를 삽입하려고 합니다.

처음에 노드 6은 노드 11의 오른쪽 자식으로 삽입되며, 노드 6은 11보다 작기 때문에 최대 레벨(41)의 모든 노드보다 작으며, 최소 레벨(8 및 11)만 체크하면 됩니다.노드 6과 11을 교환하고 나서6과 8을 교환해야 합니다.따라서 6은 힙의 루트 위치로 이동하고, 이전 루트 8은 아래로 이동하여 11을 대체하며, 11은 8의 오른쪽 자식이 됩니다.

6이 아닌 새로운 노드 81을 추가하는 것을 검토합니다.처음에는 노드 11의 오른쪽 자식으로 삽입되며 81은 11보다 크므로 최소 레벨(8, 11)의 어느 노드보다 크다.이제 최대 레벨(41)의 노드를 체크하고 스왑을 1개만 하면 됩니다.

최소값 찾기

Min-Max 힙의 최소 노드(또는 중복 키의 경우 최소 노드)는 항상 루트에 있습니다.따라서 최소값 찾기는 단순히 루트를 반환하는 간단한 상수 시간 연산입니다.

최대값 찾기

Min-Max 힙의 최대 노드(또는 중복 키의 경우 최대 노드)는 항상 첫 번째 최대 레벨(즉, 루트의 직계 하위 노드 중 하나)에 위치합니다.따라서 최대값 찾기는 루트의 두 자식 중 어느 쪽이 더 큰지 판단하기 위해 최대 한 번의 비교가 필요하며, 따라서 일정 시간 연산이기도 합니다.

최소 삭제

최소값 삭제는 어레이에서 인덱스가 알려진 임의 노드를 제거하는 특수한 경우에 불과합니다.이 경우 어레이의 마지막 요소가 제거되어 어레이의 선두에 있는 루트를 대체하기 위해 사용됩니다. push-down다음으로 루트 인덱스에서 호출되어 O $O(\log _{2}(n))$ ( $O(\log _{2}(n))$ 2 $O(\log _{2}(n))$ " ( $O(\log _{2}(n))$ ) $O(\log _{2}(n))$ { $displaystyle$ O ( \ $log$ _ { $2}$ ( $n$ ) } } $O(\log _{2}(n))$ 내에 힙속성을 복원합니다.

최대값 제거

최대값을 제거하는 것은 알려진 인덱스를 가진 임의 노드를 제거하는 특수한 경우입니다.[최대 검색(Find Maximum)]작업과 마찬가지로 루트의 최대 자아를 식별하기 위해서는 단일 비교가 필요합니다.이후 루트는 어레이의 최종 요소로 대체되고,push-down다음으로 치환된 최대값의 인덱스를 호출하여 힙 속성을 복원합니다.

내선번호

min-max-median 힙은 min-max 힙의 배리언트이며, 순서 통계 트리의 조작을 서포트합니다.

레퍼런스

^ Mischel. "Jim". Stack Overflow. Retrieved 8 September 2016.
^ ^a ^b ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "Min-Max Heaps and Generalized Priority Queues" (PDF). Communications of the ACM. 29 (10): 996–1000. doi:10.1145/6617.6621.
^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "Min-Max Heaps and Generalized Priority Queues" (PDF). Communications of the ACM. 29 (10): 996–1000. doi:10.1145/6617.6621.
^ ^a ^b ^c ^d ^e ^f ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "Min-Max Heaps and Generalized Priority Queues" (PDF). Communications of the ACM. 29 (10): 996–1000. doi:10.1145/6617.6621.
^ Gonnet, Gaston H.; Baeza-Yates, Ricardo (1991). Handbook of Algorithms and Data Structures: In Pascal and C. ISBN 0201416077.
^ K. Paparrizos, Ioannis (2011). "A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm". arXiv:1012.0956. Bibcode:2010arXiv1012.0956P. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "Min-Max Heaps and Generalized Priority Queues" (PDF). Communications of the ACM. 29 (10): 996–1000. doi:10.1145/6617.6621.

[How_to_perform_a_general_deletion_operation_on_a_min-max_heap?-1] Mischel. "Jim". Stack Overflow. Retrieved 8 September 2016.

[:0-2] ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "Min-Max Heaps and Generalized Priority Queues" (PDF). Communications of the ACM. 29 (10): 996–1000. doi:10.1145/6617.6621.

[3] ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "Min-Max Heaps and Generalized Priority Queues" (PDF). Communications of the ACM. 29 (10): 996–1000. doi:10.1145/6617.6621.

[:1-4] ^ ^a ^b ^c ^d ^e ^f ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "Min-Max Heaps and Generalized Priority Queues" (PDF). Communications of the ACM. 29 (10): 996–1000. doi:10.1145/6617.6621.

[5] Gonnet, Gaston H.; Baeza-Yates, Ricardo (1991). Handbook of Algorithms and Data Structures: In Pascal and C. ISBN 0201416077.

[6] K. Paparrizos, Ioannis (2011). "A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm". arXiv:1012.0956. Bibcode:2010arXiv1012.0956P. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[7] ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian (ed.). "Min-Max Heaps and Generalized Priority Queues" (PDF). Communications of the ACM. 29 (10): 996–1000. doi:10.1145/6617.6621.

[1]

[2]

[3]

[4]

[5]

[6]

Search

최소 힙

네임스페이스

더

목차

묘사

운용

빌드

푸시 다운

최소 푸시 다운

최대 푸시 다운

반복 양식

삽입

푸시업

최소 푸시업

최대 푸시업

반복 양식

예

최소값 찾기

최대값 찾기

최소 삭제

최대값 제거

내선번호

레퍼런스