힙(데이터 구조)

노드 키가 1 ~100의 정수인 바이너리 max-heap의 예

컴퓨터 과학에서 힙은 본질적으로 힙 속성을 충족하는 거의 완전한^[1] 트리인 특수한 트리 기반 데이터 구조입니다. 즉, 임의의 노드 C의 최대 힙에서 P가 C의 부모 노드일 경우 P의 키(값)는 C의 키보다 크거나 같습니다.최소 힙에서 P의 키는 ^[2]C의 키 이하입니다.힙의 맨 위(부모 없음)에 있는 노드를 루트 노드라고 합니다.

힙은 priority 큐라고 불리는 추상적인 데이터 타입의 최대 효율 구현입니다.실제로 priority 큐는 구현 방법에 관계없이 종종 "히프"라고 불립니다.힙에서는 항상 가장 높은(또는 가장 낮은) 우선순위 요소가 루트에 저장됩니다.그러나 힙은 정렬된 구조가 아니므로 부분적으로 정렬된 것으로 간주할 수 있습니다.힙은 우선순위가 가장 높은(또는 가장 낮은) 개체를 반복적으로 제거해야 하거나 루트 노드 제거와 함께 삽입을 삽입해야 할 때 유용한 데이터 구조입니다.

힙의 일반적인 구현은 이진 힙입니다. 여기서 트리는 이진 트리입니다(그림 참조).힙 데이터 구조, 특히 바이너리 힙은 힙소트 정렬 ^[3]알고리즘을 위한 데이터 구조로서 1964년에 J. W. J. Williams에 의해 도입되었습니다.힙은 Dijkstra의 알고리즘과 같은 몇 가지 효율적인 그래프 알고리즘에서도 매우 중요합니다.힙이 완전한 바이너리 트리일 경우 가능한 최소 높이(N개의 노드가 있는 힙 및 각 노드의 브랜치)를 가집니다_a.

그림에서 볼 수 있듯이 형제자매나 사촌 간에 암묵적인 순서가 없으며 순차 트래버설의 암묵적인 시퀀스도 없습니다(예를 들어 이진 검색 트리).위에서 설명한 힙 관계는 노드와 그 부모, 조부모님 사이에만 적용됩니다.각 노드에서 가질 수 있는 최대 자식 수는 힙 유형에 따라 달라집니다.

운용

힙과 관련된 일반적인 작업은 다음과 같습니다.

기본의

find-max(또는 find-min): max-max 또는 min-min-max의 각각 최대 항목 또는 min-max의 최소 항목 검색(일명 peek)
insert: 힙에 새 키 추가(일명^[4] push)
extract-max(또는 extract-min): 최대값 노드를 힙에서 삭제한 후 최대값(또는^[5] 최소값)의 노드를 반환한다(예를 들어 pop).
delete-max(또는 delete-min): 각각 최대 힙(또는 최소 힙)의 루트노드 삭제
replace: pop root를 선택하고 새 키를 누릅니다.두 번이 아니라 한 번만 균형을 잡으면 되기 때문에 pop보다 효율적이며 고정 ^[6]크기 더미에 적합합니다.

창조.

create-diag: 빈 힙을 만듭니다.
heapify: 지정된 요소 배열에서 힙을 만듭니다.
병합(연합): 두 개의 힙을 결합하여 두 개의 요소를 모두 포함하는 유효한 새 힙을 형성하고 원래 힙을 보존합니다.
meld: 두 개의 힙을 결합하여 두 개의 요소를 모두 포함하는 유효한 새 힙을 형성하고 원래 힙을 파괴합니다.

감사

size: 힙 내의 항목 수를 반환합니다.
is-empty: 힙이 비어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

내부의

증가 키 또는 감소 키: 각각 최대 또는 최소 대역폭 내의 키 업데이트
delete: 임의의 노드를 삭제합니다(마지막 노드를 이동하고 히프를 유지하기 위해 체크를 함으로써 삭제).
siff-up: 삽입 후 힙 상태를 복원하기 위해 사용되는 트리 내의 노드를 필요에 따라 위로 이동합니다.노드가 체와 같이 올바른 수준에 도달할 때까지 트리 위로 이동하기 때문에 "sift"라고 합니다.
sypter-down : 삭제 또는 치환 후 힙 상태를 복원하기 위해 사용되는 시프업과 마찬가지로 트리 내의 노드를 아래로 이동합니다.

실행

힙은 보통 다음과 같이 배열과 함께 구현됩니다.

어레이 내의 각 요소는 히프의 노드를 나타냅니다.
부모/자녀 관계는 배열 내 요소의 인덱스에 의해 암묵적으로 정의됩니다.

노드 키가 1 ~100의 정수인 완전한 바이너리 max-heap의 예와 배열에 저장하는 방법.

이진 힙의 경우 배열에서 첫 번째 인덱스는 루트 요소를 포함합니다.배열의 다음 두 인덱스는 루트의 하위 항목을 포함합니다.다음 4개의 인덱스는 루트의 2개의 하위 노드의 4개의 하위 노드를 포함합니다.따라서 $인덱스$ i의 노드를 지정하면 하위 노드는 $2i+1$ $2i+1$ i + $2i+1$ ({ $displaystyle 2i+1$ $2i+2$ 2 $2i+2$ + $2i+2$ ({ $displaystyle 2i+2$ 에 있고, 상위 노드는 인덱스 $'(i-1)/2'$ 에 있습니다.이 간단한 인덱싱 방식을 사용하면 트리를 "위로" 또는 "아래로" 효율적으로 이동할 수 있습니다.

힙 밸런싱은 시프업 또는 시프다운 조작(불순한 요소 교환)을 통해 이루어집니다.추가 메모리(예를 들어 노드)가 필요 없는 어레이에서 힙을 구축할 수 있으므로 힙소트를 사용하여 어레이를 인플레이스 정렬할 수 있습니다.

요소를 힙에 삽입하거나 힙에서 삭제한 후 힙 속성을 위반할 수 있으므로 어레이 내의 요소를 스왑하여 힙을 재조정해야 합니다.

힙 유형에 따라 연산이 다르게 구현되지만 가장 일반적인 방법은 다음과 같습니다.

삽입:힙 끝의 사용 가능한 첫 번째 공간에 새 요소를 추가합니다.이로 인해 히프 속성이 위반될 경우 히프 속성이 재정립될 때까지 새 요소(수영 작업)를 체로 걸러냅니다.
추출:루트를 제거하고 힙의 마지막 요소를 루트에 삽입합니다.이것이 히프 속성을 위반하는 경우는, 새로운 루트(싱크 조작)를 체다운 해 히프 속성을 재정립합니다.
대체: 뿌리를 제거하고 새 요소를 뿌리에 넣은 후 체에 거릅니다.추출 후에 삽입하는 것과 비교하면, 이것은 시프 업 스텝을 회피합니다.

이진(또는d-ary)더미의 요소들의 주어진 배열에서 건설 선형 시간의 고전적인 플로이드 알고리즘을 사용하여, 비교의 최악의 경우 번호 2N − 2s2(N)− e2(N)(이진 고물차가), N의 이진법 표현의 모든 손가락의 s2(N)및 2의 주요 도레미파에 e2(N)은 지수와 0과 수행할 수 있다.ctorN의 ^[7]이제이것은 원래 빈 힙에 연속적으로 삽입되는 일련의 ^[a]로그 선형보다 빠릅니다.

변종

변종에 대한 이론적 한계 비교

다음은 다양한 힙 데이터 구조의 시간^[8] 복잡성입니다.함수명은 max-heap을 전제로 합니다."O(f)" 및 "δ(f)"의 의미는 빅 O 표기법을 참조하십시오.

작동	검색 최대값	삭제 최대값	삽입하다	증가 키	혼재
바이너리^[8]	θ(1)	δ(로그 n)	O(log n)	O(log n)	θ(n)
좌파	θ(1)	δ(로그 n)	δ(로그 n)	O(log n)	δ(로그 n)
이항^[8]^[9]	θ(1)	δ(로그 n)	θ(1)^[b]	δ(로그 n)	O(log n)^[c]
피보나치^[8]^[10]	θ(1)	O(log n)^[b]	θ(1)	θ(1)^[b]	θ(1)
페어링^[11]	θ(1)	O(log n)^[b]	θ(1)	o(로그 n)^[b]^[d]	θ(1)
브로달^[14]^[e]	θ(1)	O(log n)	θ(1)	θ(1)	θ(1)
랭크 페어링^[16]	θ(1)	O(log n)^[b]	θ(1)	θ(1)^[b]	θ(1)
엄밀한 피보나치^[17]	θ(1)	O(log n)	θ(1)	θ(1)	θ(1)
2 ~ 3 히프^[18]	O(log n)	O(log n)^[b]	O(log n)^[b]	θ(1)	?

^ 각 삽입에는 히프의 기존 크기에서 O(log(k)가 사용됩니다.따라서 $\sum _{k=1}^{n}O(\log k)$ $\sum _{k=1}^{n}O(\log k)$ 1 nO ( $\sum _{k=1}^{n}O(\log k)$ k $){$ $displaystyle \sum$ _ {k $= 1$ )^{ $n}O$ ( \ $log$ k ) $。$ $\log n/2=(\log n)-1$ n / $\log n/2=(\log n)-1$ = ( $\log n/2=(\log n)-1$ $\log n/2=(\log n)-1$ - $\log n/2=(\log n)-1$ { $displaystyle \ log$ n / $\log n/2=(\log n)-1$ $=$ 2 ( \ $log$ n （ \ loperfactor ) $\log n/2=(\log n)-1$ ） } factor n - 1 } factor n - 1 （ log - 1 $\log n/2=(\log n)-1$ } } $\log n/2=(\log n)-1$ 。 $k=n$ k $k=n$ \ $displaystyle$ k $= n$ $k=n$ 정식 시각은 $nO(\log n)-O(n)=O(n\log n)$ O ( log $nO(\log n)-O(n)=O(n\log n)$ $nO(\log n)-O(n)=O(n\log n)$ ) $nO(\log n)-O(n)=O(n\log n)$ - $nO(\log n)-O(n)=O(n\log n)$ ( $nO(\log n)-O(n)=O(n\log n)$ ) $nO(\log n)-O(n)=O(n\log n)$ $nO(\log n)-O(n)=O(n\log n)$ ( $nO(\log n)-O(n)=O(n\log n)$ $nO(\log n)-O(n)=O(n\log n)$ n $){$ $displaystyle nO$ ( \ $log$ n ) = O ( $n$ ) $nO(\log n)-O(n)=O(n\log n)$ } 입니다.이것은 스털링의 근사치에서도 쉽게 알 수 있다.
^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ 상각시간
^ n은 큰 힙의 크기입니다.
^ 하한 $\Omega (\log \log n),$ ( $\Omega (\log \log n),$ log $\Omega (\log \log n),$ n $\Omega (\log \log n),$ ) $\Omega (\log \log n),$ , {\ $displaystyle \Omega$ ( \ $log \log$ n ) $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$ O의 $\Omega (\log \log n),$ ^[12] $O(2^{2{\sqrt {\log \log n}}}).$ ( $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ log $O(2^{2{\sqrt {\log \log n}}}).$ n ) $。{$ $display style$ O ( $2$ ^ { $2$ \ $sq$ \ $log$ \ $log n$ } } 。 $}$ ^[13]
^ Brodal과 Okasaki는 나중에 지원되지 않는 decrement-key를 제외하고 동일한 경계를 가진 영속적인 변종을 기술합니다.n개의 요소가 있는 힙은 O(n)^[15]에서 상향식으로 구성할 수 있습니다.

적용들

힙 데이터 구조에는 많은 응용 프로그램이 있습니다.

힙소트:배치되어 있고 2차 최악의 시나리오가 없는 최상의 정렬 방법 중 하나입니다.
선택 알고리즘:히프를 사용하면 최소 또는 최대 요소에 일정 시간 동안 액세스할 수 있으며, ^[19]힙에 있는 데이터에 대해 다른 선택(중앙값 또는 kth 요소 등)을 하위 선형 시간으로 수행할 수 있습니다.
그래프 알고리즘 : 힙을 내부 횡단 데이터 구조로 함으로써 다항식 순서로 실행 시간을 단축할 수 있습니다.이러한 문제의 예로는 Prim의 최소 스패닝 트리 알고리즘과 Dijkstra의 최단 경로 알고리즘이 있습니다.
priority 큐:priority 큐는 "목록" 또는 "맵"과 같은 추상 개념입니다.목록을 링크된 목록 또는 배열로 구현할 수 있는 것처럼 priority 큐는 힙 또는 기타 다양한 방법으로 구현할 수 있습니다.
K-way 병합:힙 데이터 구조는 이미 정렬된 많은 입력 스트림을 하나의 정렬된 출력 스트림으로 병합하는 데 유용합니다.Marge의 필요성의 예로는 로그 구조화된 Marge Tree와 같은 분산 데이터로부터의 외부 정렬 및 스트리밍 결과를 들 수 있습니다.내부 루프는 min 요소를 취득하여 대응하는 입력 스트림의 다음 요소로 치환한 후 시프다운히프 작업을 수행합니다.(대체 함수) (extract-max 및 priority 큐의 삽입 함수를 사용하면 효율이 훨씬 떨어집니다.)
주문 통계:히프 데이터 구조를 사용하면 배열에서 k번째로 작은(또는 가장 큰) 요소를 효율적으로 찾을 수 있습니다.

프로그래밍 언어 구현

C++ 스탠다드 라이브러리는임의의 랜덤 액세스 반복기에서 동작하는 힙(일반적으로 바이너리 힙으로 구현됨)에 대한 make_push_param 알고리즘 및 pop_param 알고리즘.반복기를 어레이에 대한 참조로 간주하고 어레이에서 힙으로 변환합니다.또한 컨테이너 어댑터 priority_queue를 제공하여 이러한 기능을 컨테이너와 같은 클래스로 묶습니다.단, 치환, 체업/시프트다운 또는 키 감소/증가 조작에는 표준 지원이 없습니다.
Boost C++ 라이브러리에는 힙 라이브러리가 포함되어 있습니다.STL과는 달리 감소 및 증가 연산을 지원하며 추가 유형의 힙을 지원합니다. 구체적으로는 d-ary, 이항, 피보나치, 페어링 및 스큐 힙을 지원합니다.
D-ary 힙과 B-heap을 지원하는 C 및 C++에는 범용 힙 구현이 있습니다.STL과 같은 API를 제공합니다.
D 프로그래밍 언어의 표준 라이브러리에는 std.container가 포함되어 있습니다.BinaryHeap은 D의 범위로 구현됩니다.인스턴스는 임의의 랜덤액세스 범위에서 구성할 수 있습니다.BinaryHeap은 D의 내장 foreach 문과의 반복 및 std.algorithm 패키지의 범위 기반 API와의 통합을 허용하는 입력 범위 인터페이스를 제공합니다.
Haskell을 위한 데이터가 있습니다.히프 모듈
Java 플랫폼(버전 1.5 이후)은 클래스에서 바이너리 힙 구현을 제공합니다.java.util.PriorityQueueJava Collections Framework에서 확인할 수 있습니다.이 클래스는 기본적으로 min-heap을 구현합니다. max-heap을 구현하려면 프로그래머가 커스텀 비교기를 작성해야 합니다.치환, 체업/시프트다운 또는 키 감소/증가 조작은 지원되지 않습니다.
Python에는 이진 힙을 사용하여 priority 큐를 구현하는 힙큐 모듈이 있습니다.라이브러리는 k-way 병합을 지원하는 힙 교체 함수를 제공합니다.
표준 PHP 라이브러리에는 버전 5.3의 경우 max-heap(SplMaxHeap)과 min-heap(SplMinHeap)이 모두 있습니다.
Perl은 CPAN에서 사용 가능한 힙 배포에 바이너리, 이항 및 피보나치 힙을 구현합니다.
Go 언어에는 지정된 인터페이스를 충족하는 임의 유형으로 작동하는 힙 알고리즘이 포함된 힙 패키지가 포함되어 있습니다.이 패키지는 치환, 체업/시프트다운 또는 키 감소/증가 조작을 지원하지 않습니다.
Apple의 Core Foundation 라이브러리에는 CFBinaryHeap 구조가 포함되어 있습니다.
Pharo는 일련의 테스트 케이스와 함께 Collections-Sequenceable 패키지에 힙을 구현하고 있습니다.히프는 타이머이벤트 루프의 실장에 사용됩니다.
Rust 프로그래밍 언어에는 표준 라이브러리의 컬렉션 모듈에 바이너리 max-heap 구현인 BinaryHeap이 있습니다.
.NET에는 priority가 있습니다 .Quarternary(d-ary) min-heap 구현을 사용하는 큐클래스에서 입수할 수 있습니다.NET 6 。

「」를 참조해 주세요.

레퍼런스

^ CORMEN, THOMAS H. (2009). INTRODUCTION TO ALGORITHMS. United States of America: The MIT Press Cambridge, Massachusetts London, England. pp. 151–152. ISBN 978-0-262-03384-8.
^ 블랙(ed.), 폴 E.(2004-12-14)알고리즘 및 데이터 구조 사전의 힙 항목입니다.온라인 버전미국 국립표준기술연구소, 2004년 12월 14일.https://xlinux.nist.gov/dads/HTML/heap.html에서 2017-10-08에 취득.
^ Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, doi:10.1145/512274.512284
^ Python Standard Library, 8.4. heapq: 힙 큐 알고리즘, heapq.heappush
^ Python Standard Library, 8.4. heapq: 힙 큐 알고리즘, heapq.heapop
^ Python Standard Library, 8.4. heapq - 힙큐 알고리즘, heapreplace
^ 를 클릭합니다Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751.
^ ^a ^b ^c ^d Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
^ "Binomial Heap Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.
^ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.
^ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
^ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
^ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
^ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
^ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.
^ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
^ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
^ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
^ Frederickson, Greg N. (1993), "An Optimal Algorithm for Selection in a Min-Heap", Information and Computation (PDF), vol. 104, Academic Press, pp. 197–214, doi:10.1006/inco.1993.1030, archived from the original (PDF) on 2012-12-03, retrieved 2010-10-31

외부 링크

울프램 매스월드의 힙
기본적인 힙알고리즘의 동작
Bentley, Jon Louis (2000). Programming Pearls (2nd ed.). Addison Wesley. pp. 147–162. ISBN 0201657880.

[8] 각 삽입에는 히프의 기존 크기에서 O(log(k)가 사용됩니다.따라서 $\sum _{k=1}^{n}O(\log k)$ $\sum _{k=1}^{n}O(\log k)$ 1 nO ( $\sum _{k=1}^{n}O(\log k)$ k $){$ $displaystyle \sum$ _ {k $= 1$ )^{ $n}O$ ( \ $log$ k ) $。$ $\log n/2=(\log n)-1$ n / $\log n/2=(\log n)-1$ = ( $\log n/2=(\log n)-1$ $\log n/2=(\log n)-1$ - $\log n/2=(\log n)-1$ { $displaystyle \ log$ n / $\log n/2=(\log n)-1$ $=$ 2 ( \ $log$ n （ \ loperfactor ) $\log n/2=(\log n)-1$ ） } factor n - 1 } factor n - 1 （ log - 1 $\log n/2=(\log n)-1$ } } $\log n/2=(\log n)-1$ 。 $k=n$ k $k=n$ \ $displaystyle$ k $= n$ $k=n$ 정식 시각은 $nO(\log n)-O(n)=O(n\log n)$ O ( log $nO(\log n)-O(n)=O(n\log n)$ $nO(\log n)-O(n)=O(n\log n)$ ) $nO(\log n)-O(n)=O(n\log n)$ - $nO(\log n)-O(n)=O(n\log n)$ ( $nO(\log n)-O(n)=O(n\log n)$ ) $nO(\log n)-O(n)=O(n\log n)$ $nO(\log n)-O(n)=O(n\log n)$ ( $nO(\log n)-O(n)=O(n\log n)$ $nO(\log n)-O(n)=O(n\log n)$ n $){$ $displaystyle nO$ ( \ $log$ n ) = O ( $n$ ) $nO(\log n)-O(n)=O(n\log n)$ } 입니다.이것은 스털링의 근사치에서도 쉽게 알 수 있다.

[amortized-11] ^ ^a ^b ^c ^d ^e ^f ^g ^h ⁱ 상각시간

[meld-12] 은 큰 힙의 크기입니다.

[pairingdecreasekey-17] 하한 $\Omega (\log \log n),$ ( $\Omega (\log \log n),$ log $\Omega (\log \log n),$ n $\Omega (\log \log n),$ ) $\Omega (\log \log n),$ , {\ $displaystyle \Omega$ ( \ $log \log$ n ) $\Omega (\log \log n),$ $O(2^{2{\sqrt {\log \log n}}}).$ O의 $\Omega (\log \log n),$ ^[12] $O(2^{2{\sqrt {\log \log n}}}).$ ( $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ $O(2^{2{\sqrt {\log \log n}}}).$ log $O(2^{2{\sqrt {\log \log n}}}).$ n ) $。{$ $display style$ O ( $2$ ^ { $2$ \ $sq$ \ $log$ \ $log n$ } } 。 $}$ ^[13]

[brodal-20] Brodal과 Okasaki는 나중에 지원되지 않는 decrement-key를 제외하고 동일한 경계를 가진 영속적인 변종을 기술합니다.n개의 요소가 있는 힙은 O(n)^[15]에서 상향식으로 구성할 수 있습니다.

[1] CORMEN, THOMAS H. (2009). INTRODUCTION TO ALGORITHMS. United States of America: The MIT Press Cambridge, Massachusetts London, England. pp. 151–152. ISBN 978-0-262-03384-8.

[2] 블랙(ed.), 폴 E.(2004-12-14)알고리즘 및 데이터 구조 사전의 힙 항목입니다.온라인 버전미국 국립표준기술연구소, 2004년 12월 14일.https://xlinux.nist.gov/dads/HTML/heap.html에서 2017-10-08에 취득.

[3] Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, doi:10.1145/512274.512284

[4] Python Standard Library, 8.4. heapq: 힙 큐 알고리즘, heapq.heappush

[5] Python Standard Library, 8.4. heapq: 힙 큐 알고리즘, heapq.heapop

[6] Python Standard Library, 8.4. heapq - 힙큐 알고리즘, heapreplace

[7] 를 클릭합니다Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751.

[CLRS-9] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.

[10] "Binomial Heap Brilliant Math & Science Wiki". brilliant.org. Retrieved 2019-09-30.

[Fredman_And_Tarjan-13] Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.

[Iacono-14] Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2

[Fredman1999-15] Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.

[16] Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.

[18] Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58

[19] Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.

[21] Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.

[22] Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.

[23] Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12

[24] Frederickson, Greg N. (1993), "An Optimal Algorithm for Selection in a Min-Heap", Information and Computation (PDF), vol. 104, Academic Press, pp. 197–214, doi:10.1006/inco.1993.1030, archived from the original (PDF) on 2012-12-03, retrieved 2010-10-31

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[a]

[8]

[9]

[b]

[c]

[10]

[11]

[d]

[14]

[e]

[16]

[17]

[18]

[12]

[13]

[15]

[19]

v t 트리 데이터 구조
트리 검색 (다이나믹 세트/어소시에이션 어레이)	2–3 2–3–4 AA (a, b) AVL B B+ B* B^x. (최적) 바이너리 검색 춤추다 HTree 간격 주문통계 (좌향) 레드-블랙 희생양 스플라이 T 나무 UB 무게 밸런스
수북이	바이너리 이항 브로달 피보나치 좌파 페어링 스큐 판 엠데 보아스 약한
시도하다	Ctrie C-trie(압축 ADT) 해시 기수 서픽스 삼진수 검색 X-Fast 고속
공간 데이터 파티션 트리	공 BK BSP 데카르트어 힐베르트 R k-d(표준 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 부분 부사장 X
기타 트리	덮다 지수 펜윅 손가락. 프랙탈 트리 인덱스 퓨전 해시 캘린더 i디스턴스 K-ary 좌측자녀 우측자매 링크/컷 로그 구조화 결합 머클 p q. 범위 SPQR 정상

v t 잘 알려진 데이터 구조
종류들	수집 컨테이너.
추상적인	연관 배열 멀티맵 데이터 구조 검색 목록. 스택 큐 더블 엔드 큐 priority 큐 이중 엔드 priority 큐 세트 멀티셋 디조인트 세트
어레이	비트 배열 순환 버퍼 다이내믹 어레이 해시 테이블 해시 어레이 트리 희박 행렬
링크되어 있다	어소시에이션리스트 링크 리스트 스킵 리스트 언롤링된 링크 리스트 XOR 링크 리스트
나무들	B-트리 이진 검색 트리 AA나무 AVL 트리 붉은색-검은색 셀프밸런싱 트리 스플레이 트리 히프 이진 힙 이항 힙 피보나치 힙 R 트리 R* 트리 R+ 트리 힐베르트 R-트리 트리 해시 트리
그래프	이항 결정도 방향 비순환 그래프 지시 비순환 단어 그래프
데이터 구조 목록

Search

힙(데이터 구조)

네임스페이스

더

목차

운용

실행

변종

변종에 대한 이론적 한계 비교

적용들

프로그래밍 언어 구현

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

힙(데이터 구조)

운용

실행

변종

변종에 대한 이론적 한계 비교

적용들

프로그래밍 언어 구현

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.