| Jump to content | https://en.wikipedia.org/wiki/Binary_heap#bodyContent |
| Main page | https://en.wikipedia.org/wiki/Main_Page |
| Contents | https://en.wikipedia.org/wiki/Wikipedia:Contents |
| Current events | https://en.wikipedia.org/wiki/Portal:Current_events |
| Random article | https://en.wikipedia.org/wiki/Special:Random |
| About Wikipedia | https://en.wikipedia.org/wiki/Wikipedia:About |
| Contact us | https://en.wikipedia.org/wiki/Wikipedia:Contact_us |
| Help | https://en.wikipedia.org/wiki/Help:Contents |
| Learn to edit | https://en.wikipedia.org/wiki/Help:Introduction |
| Community portal | https://en.wikipedia.org/wiki/Wikipedia:Community_portal |
| Recent changes | https://en.wikipedia.org/wiki/Special:RecentChanges |
| Upload file | https://en.wikipedia.org/wiki/Wikipedia:File_upload_wizard |
| Special pages | https://en.wikipedia.org/wiki/Special:SpecialPages |
|
| https://en.wikipedia.org/wiki/Main_Page |
|
Search
| https://en.wikipedia.org/wiki/Special:Search |
| Donate | https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en |
| Create account | https://en.wikipedia.org/w/index.php?title=Special:CreateAccount&returnto=Binary+heap |
| Log in | https://en.wikipedia.org/w/index.php?title=Special:UserLogin&returnto=Binary+heap |
|
Donate | https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en |
|
Create account | https://en.wikipedia.org/w/index.php?title=Special:CreateAccount&returnto=Binary+heap |
|
Log in | https://en.wikipedia.org/w/index.php?title=Special:UserLogin&returnto=Binary+heap |
|
(Top)
| https://en.wikipedia.org/wiki/Binary_heap |
|
1
Heap operations
| https://en.wikipedia.org/wiki/Binary_heap#Heap_operations |
|
1.1
Insert
| https://en.wikipedia.org/wiki/Binary_heap#Insert |
|
1.2
Extract
| https://en.wikipedia.org/wiki/Binary_heap#Extract |
|
1.3
Insert then extract
| https://en.wikipedia.org/wiki/Binary_heap#Insert_then_extract |
|
1.4
Search
| https://en.wikipedia.org/wiki/Binary_heap#Search |
|
1.5
Delete
| https://en.wikipedia.org/wiki/Binary_heap#Delete |
|
1.6
Decrease or increase key
| https://en.wikipedia.org/wiki/Binary_heap#Decrease_or_increase_key |
|
2
Building a heap
| https://en.wikipedia.org/wiki/Binary_heap#Building_a_heap |
|
3
Heap implementation
| https://en.wikipedia.org/wiki/Binary_heap#Heap_implementation |
|
4
Derivation of index equations
| https://en.wikipedia.org/wiki/Binary_heap#Derivation_of_index_equations |
|
4.1
Child nodes
| https://en.wikipedia.org/wiki/Binary_heap#Child_nodes |
|
4.2
Parent node
| https://en.wikipedia.org/wiki/Binary_heap#Parent_node |
|
5
Related structures
| https://en.wikipedia.org/wiki/Binary_heap#Related_structures |
|
6
Summary of running times
| https://en.wikipedia.org/wiki/Binary_heap#Summary_of_running_times |
|
7
References
| https://en.wikipedia.org/wiki/Binary_heap#References |
|
8
External links
| https://en.wikipedia.org/wiki/Binary_heap#External_links |
| العربية | https://ar.wikipedia.org/wiki/%D9%83%D9%88%D9%85%D8%A9_%D8%AB%D9%86%D8%A7%D8%A6%D9%8A%D8%A9 |
| Català | https://ca.wikipedia.org/wiki/Monticle_binari |
| Čeština | https://cs.wikipedia.org/wiki/Bin%C3%A1rn%C3%AD_halda |
| Deutsch | https://de.wikipedia.org/wiki/Bin%C3%A4rer_Heap |
| Español | https://es.wikipedia.org/wiki/Mont%C3%ADculo_binario |
| فارسی | https://fa.wikipedia.org/wiki/%D9%87%D8%B1%D9%85_%D8%AF%D9%88%D8%AF%D9%88%DB%8C%DB%8C |
| Français | https://fr.wikipedia.org/wiki/Tas_binaire |
| עברית | https://he.wikipedia.org/wiki/%D7%A2%D7%A8%D7%99%D7%9E%D7%94_%D7%91%D7%99%D7%A0%D7%90%D7%A8%D7%99%D7%AA |
| Magyar | https://hu.wikipedia.org/wiki/Bin%C3%A1ris_kupac |
| Italiano | https://it.wikipedia.org/wiki/Heap_binario |
| 日本語 | https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E3%83%92%E3%83%BC%E3%83%97 |
| 한국어 | https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%9E%99 |
| Polski | https://pl.wikipedia.org/wiki/Kopiec_binarny |
| Русский | https://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0 |
| Slovenčina | https://sk.wikipedia.org/wiki/Bin%C3%A1rna_halda |
| Српски / srpski | https://sr.wikipedia.org/wiki/Binarni_hip |
| ไทย | https://th.wikipedia.org/wiki/%E0%B8%AE%E0%B8%B5%E0%B8%9B%E0%B8%97%E0%B8%A7%E0%B8%B4%E0%B8%A0%E0%B8%B2%E0%B8%84 |
| Українська | https://uk.wikipedia.org/wiki/%D0%94%D0%B2%D1%96%D0%B9%D0%BA%D0%BE%D0%B2%D0%B0_%D0%BA%D1%83%D0%BF%D0%B0 |
| Tiếng Việt | https://vi.wikipedia.org/wiki/%C4%90%E1%BB%91ng_nh%E1%BB%8B_ph%C3%A2n |
| 粵語 | https://zh-yue.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E5%A0%86%E7%A9%8D%E6%A8%B9 |
| 中文 | https://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E5%A0%86 |
| Edit links | https://www.wikidata.org/wiki/Special:EntityPage/Q803847#sitelinks-wikipedia |
| Article | https://en.wikipedia.org/wiki/Binary_heap |
| Talk | https://en.wikipedia.org/wiki/Talk:Binary_heap |
| Read | https://en.wikipedia.org/wiki/Binary_heap |
| Edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit |
| View history | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=history |
|
Read | https://en.wikipedia.org/wiki/Binary_heap |
|
Edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit |
|
View history | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=history |
| What links here | https://en.wikipedia.org/wiki/Special:WhatLinksHere/Binary_heap |
| Related changes | https://en.wikipedia.org/wiki/Special:RecentChangesLinked/Binary_heap |
| Upload file | https://en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard |
| Permanent link | https://en.wikipedia.org/w/index.php?title=Binary_heap&oldid=1350857347 |
| Page information | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=info |
| Cite this page | https://en.wikipedia.org/w/index.php?title=Special:CiteThisPage&page=Binary_heap&id=1350857347&wpFormIdentifier=titleform |
| Get shortened URL | https://en.wikipedia.org/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBinary_heap |
| Download as PDF | https://en.wikipedia.org/w/index.php?title=Special:DownloadAsPdf&page=Binary_heap&action=show-download-screen |
| Printable version | https://en.wikipedia.org/w/index.php?title=Binary_heap&printable=yes |
| Wikimedia Commons | https://commons.wikimedia.org/wiki/Category:Binary_heaps |
| Wikidata item | https://www.wikidata.org/wiki/Special:EntityPage/Q803847 |
| Type | https://en.wikipedia.org/wiki/List_of_data_structures |
| J. W. J. Williams | https://en.wikipedia.org/wiki/J._W._J._Williams |
| Time complexity | https://en.wikipedia.org/wiki/Time_complexity |
| big O notation | https://en.wikipedia.org/wiki/Big_O_notation |
| Space complexity | https://en.wikipedia.org/wiki/Space_complexity |
| https://en.wikipedia.org/wiki/File:Max-Heap.svg |
| https://en.wikipedia.org/wiki/File:Min-heap.png |
| heap | https://en.wikipedia.org/wiki/Heap_(data_structure) |
| data structure | https://en.wikipedia.org/wiki/Data_structure |
| binary tree | https://en.wikipedia.org/wiki/Binary_tree |
| priority queues | https://en.wikipedia.org/wiki/Priority_queue |
| [1] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-clrs-1 |
| J. W. J. Williams | https://en.wikipedia.org/wiki/J._W._J._Williams |
| heapsort | https://en.wikipedia.org/wiki/Heapsort |
| [2] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-2 |
| [3] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-3 |
| complete binary tree | https://en.wikipedia.org/wiki/Complete_binary_tree |
| total order | https://en.wikipedia.org/wiki/Total_order |
| logarithmic time | https://en.wikipedia.org/wiki/Logarithmic_time |
| heapsort | https://en.wikipedia.org/wiki/Heapsort |
| sorting algorithm | https://en.wikipedia.org/wiki/Sorting_algorithm |
| implicit data structure | https://en.wikipedia.org/wiki/Implicit_data_structure |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=1 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=2 |
| [4] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-4 |
| [5] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-5 |
| https://en.wikipedia.org/wiki/File:InsertingIntoBinaryHeap.gif |
| transitive relation | https://en.wikipedia.org/wiki/Transitive_relation |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=3 |
| https://en.wikipedia.org/wiki/File:ExtractingFromBinaryHeap.gif |
| pseudocode | https://en.wikipedia.org/wiki/Pseudocode |
| array | https://en.wikipedia.org/wiki/Array_data_structure |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=4 |
| Python | https://en.wikipedia.org/wiki/Python_(programming_language) |
| [6] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-6 |
| [7] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-7 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=5 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=6 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=7 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=8 |
| [a] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-9 |
| Floyd | https://en.wikipedia.org/wiki/Robert_W._Floyd |
| [8] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-heapbuildjalg-8 |
| series | https://en.wikipedia.org/wiki/Series_(mathematics) |
| converges | https://en.wikipedia.org/wiki/Convergent_series |
| [9] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-10 |
| [b] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-11 |
| sum of all digits of the binary representation | https://en.wikipedia.org/wiki/Hamming_weight |
| [10] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-12 |
| [11] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-13 |
| floor | https://en.wikipedia.org/wiki/Floor_function |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=9 |
| https://en.wikipedia.org/wiki/File:Binary_tree_in_array.svg |
| https://en.wikipedia.org/wiki/File:Binary_Heap_with_Array_Implementation.JPG |
| array | https://en.wikipedia.org/wiki/Array_data_structure |
| pointers | https://en.wikipedia.org/wiki/Pointer_(computer_programming) |
| implicit data structure | https://en.wikipedia.org/wiki/Implicit_data_structure |
| Ahnentafel | https://en.wikipedia.org/wiki/Ahnentafel |
| programming language | https://en.wikipedia.org/wiki/Programming_language |
| floor | https://en.wikipedia.org/wiki/Floor_function |
| floor | https://en.wikipedia.org/wiki/Floor_function |
| heapsort | https://en.wikipedia.org/wiki/Heapsort |
| in-place | https://en.wikipedia.org/wiki/In-place_algorithm |
| Priority queue | https://en.wikipedia.org/wiki/Priority_queue |
| dynamic array | https://en.wikipedia.org/wiki/Dynamic_array |
| tail-recursively | https://en.wikipedia.org/wiki/Tail_recursion |
| virtual memory | https://en.wikipedia.org/wiki/Virtual_memory |
| page | https://en.wikipedia.org/wiki/Page_(computer_memory) |
| B-heaps | https://en.wikipedia.org/wiki/B-heap |
| [12] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-14 |
| [13] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-15 |
| [14] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-16 |
| [15] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-17 |
| binomial heaps | https://en.wikipedia.org/wiki/Binomial_heap |
| inorder | https://en.wikipedia.org/wiki/Inorder |
|
O
{\displaystyle O}
| https://en.wikipedia.org/wiki/Big_O_notation |
| [16] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-sym-18 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=10 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=11 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=12 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=13 |
| treap | https://en.wikipedia.org/wiki/Treap |
| d-ary heap | https://en.wikipedia.org/wiki/D-ary_heap |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=14 |
| time complexities | https://en.wikipedia.org/wiki/Computational_complexity_theory |
| [17] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-CLRS-19 |
| Big O notation | https://en.wikipedia.org/wiki/Big_O_notation |
| [c] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-23 |
| [17] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-CLRS-19 |
| Skew | https://en.wikipedia.org/wiki/Skew_heap |
| [18] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-sleator-tarjan-skew-20 |
| Leftist | https://en.wikipedia.org/wiki/Leftist_tree |
| [19] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-tarjan-leftist-21 |
| Binomial | https://en.wikipedia.org/wiki/Binomial_heap |
| [17] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-CLRS-19 |
| [21] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-24 |
| [d] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-bootstrap-meld-25 |
| Skew binomial | https://en.wikipedia.org/wiki/Skew_binomial_heap |
| [22] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-brodal-okasaki-26 |
| [d] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-bootstrap-meld-25 |
| 2–3 heap | https://en.wikipedia.org/wiki/2%E2%80%933_heap |
| [24] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-28 |
| [d] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-bootstrap-meld-25 |
| Bottom-up skew | https://en.wikipedia.org/wiki/Skew_heap |
| [18] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-sleator-tarjan-skew-20 |
| Pairing | https://en.wikipedia.org/wiki/Pairing_heap |
| [25] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-Iacono-29 |
| [e] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-pairingdecreasekey-32 |
| Rank-pairing | https://en.wikipedia.org/w/index.php?title=Rank-pairing_heap&action=edit&redlink=1 |
| [28] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-33 |
| Fibonacci | https://en.wikipedia.org/wiki/Fibonacci_heap |
| [17] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-CLRS-19 |
| [29] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-Fredman_And_Tarjan-34 |
| Strict Fibonacci | https://en.wikipedia.org/wiki/Strict_Fibonacci_heap |
| [30] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-35 |
| [f] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-optimum-36 |
| Brodal | https://en.wikipedia.org/wiki/Brodal_queue |
| [31] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-37 |
| [f] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-optimum-36 |
| [32] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-38 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-9 |
| in the worst case | https://en.wikipedia.org/wiki/Best,_worst_and_average_case |
| [1] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-clrs-1 |
| permutations | https://en.wikipedia.org/wiki/Permutation |
| [8] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-heapbuildjalg-8 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-11 |
| heapsort | https://en.wikipedia.org/wiki/Heapsort |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-23 |
| [18] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-sleator-tarjan-skew-20 |
| [19] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-tarjan-leftist-21 |
| [20] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-hayward-mcdiarmid-heap-build-22 |
| a | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-bootstrap-meld_25-0 |
| b | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-bootstrap-meld_25-1 |
| c | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-bootstrap-meld_25-2 |
| persistent | https://en.wikipedia.org/wiki/Persistent_data_structure |
| [23] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-27 |
| [22] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-brodal-okasaki-26 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-pairingdecreasekey_32-0 |
| [26] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-Fredman1999-30 |
| [27] | https://en.wikipedia.org/wiki/Binary_heap#cite_note-31 |
| a | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-optimum_36-0 |
| b | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-optimum_36-1 |
| persistent | https://en.wikipedia.org/wiki/Persistent_data_structure |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=15 |
| a | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-clrs_1-0 |
| b | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-clrs_1-1 |
| Cormen, Thomas H. | https://en.wikipedia.org/wiki/Thomas_H._Cormen |
| Leiserson, Charles E. | https://en.wikipedia.org/wiki/Charles_E._Leiserson |
| Rivest, Ronald L. | https://en.wikipedia.org/wiki/Ron_Rivest |
| Stein, Clifford | https://en.wikipedia.org/wiki/Clifford_Stein |
| Introduction to Algorithms | https://en.wikipedia.org/wiki/Introduction_to_Algorithms |
| ISBN | https://en.wikipedia.org/wiki/ISBN_(identifier) |
| 0-262-03384-4 | https://en.wikipedia.org/wiki/Special:BookSources/0-262-03384-4 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-2 |
| Williams, J. W. J. | https://en.wikipedia.org/wiki/J._W._J._Williams |
| Communications of the ACM | https://en.wikipedia.org/wiki/Communications_of_the_ACM |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1145/512274.3734138 | https://doi.org/10.1145%2F512274.3734138 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-3 |
| "Binary Heaps" | http://lcm.csa.iisc.ernet.in/dsa/node137.html |
| Data Structures and Algorithms | https://gtl.csa.iisc.ac.in/dsa/ |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-4 |
| Bibcode | https://en.wikipedia.org/wiki/Bibcode_(identifier) |
| 1975ITSEn...1..292P | https://ui.adsabs.harvard.edu/abs/1975ITSEn...1..292P |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1109/TSE.1975.6312854 | https://doi.org/10.1109%2FTSE.1975.6312854 |
| ISSN | https://en.wikipedia.org/wiki/ISSN_(identifier) |
| 1939-3520 | https://search.worldcat.org/issn/1939-3520 |
| S2CID | https://en.wikipedia.org/wiki/S2CID_(identifier) |
| 18907513 | https://api.semanticscholar.org/CorpusID:18907513 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-5 |
| "Data structures" | https://publikationen.sulb.uni-saarland.de/handle/20.500.11880/26179 |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.22028/D291-26123 | https://doi.org/10.22028%2FD291-26123 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-6 |
| "python/cpython/heapq.py" | https://github.com/python/cpython/blob/master/Lib/heapq.py |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-7 |
| "heapq — Heap queue algorithm — Python 3.8.5 documentation" | https://docs.python.org/3/library/heapq.html#heapq.heappushpop |
| a | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-heapbuildjalg_8-0 |
| b | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-heapbuildjalg_8-1 |
| "Average Case Analysis of Heap Building by Repeated Insertion" | https://web.archive.org/web/20160205023201/http://www.stats.ox.ac.uk/__data/assets/pdf_file/0015/4173/heapbuildjalg.pdf |
| CiteSeerX | https://en.wikipedia.org/wiki/CiteSeerX_(identifier) |
| 10.1.1.353.7888 | https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.353.7888 |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1016/0196-6774(91)90027-v | https://doi.org/10.1016%2F0196-6774%2891%2990027-v |
| the original | http://www.stats.ox.ac.uk/__data/assets/pdf_file/0015/4173/heapbuildjalg.pdf |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-10 |
| "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program" | http://www.deepdyve.com/lp/ios-press/elementary-yet-precise-worst-case-analysis-of-floyd-s-heap-50NW30HMxU |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.3233/FI-2012-751 | https://doi.org/10.3233%2FFI-2012-751 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-12 |
| "An Average Case Analysis of Floyd's Algorithm to Construct Heaps" | https://core.ac.uk/download/pdf/82135122.pdf |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1016/S0019-9958(84)80053-4 | https://doi.org/10.1016%2FS0019-9958%2884%2980053-4 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-13 |
| CiteSeerX | https://en.wikipedia.org/wiki/CiteSeerX_(identifier) |
| 10.1.1.15.9526 | https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.9526 |
| ISBN | https://en.wikipedia.org/wiki/ISBN_(identifier) |
| 951-650-888-X | https://en.wikipedia.org/wiki/Special:BookSources/951-650-888-X |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-14 |
| "You're Doing It Wrong" | http://queue.acm.org/detail.cfm?id=1814327 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-15 |
| "binary heap" | http://nist.gov/dads/HTML/binaryheap.html |
| Archived | https://web.archive.org/web/20080808141408/http://www.nist.gov/dads/HTML/binaryheap.html |
| Wayback Machine | https://en.wikipedia.org/wiki/Wayback_Machine |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-16 |
| J.-R. Sack | https://en.wikipedia.org/wiki/J%C3%B6rg-R%C3%BCdiger_Sack |
| "An Algorithm for Merging Heaps" | https://doi.org/10.1007%2FBF00264229 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-17 |
| Sack, Jörg-Rüdiger | https://en.wikipedia.org/wiki/J%C3%B6rg-R%C3%BCdiger_Sack |
| "A characterization of heaps and its applications" | https://doi.org/10.1016%2F0890-5401%2890%2990026-E |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1016/0890-5401(90)90026-E | https://doi.org/10.1016%2F0890-5401%2890%2990026-E |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-sym_18-0 |
| Atkinson, M.D. | https://en.wikipedia.org/wiki/Michael_D._Atkinson |
| J.-R. Sack | https://en.wikipedia.org/wiki/J%C3%B6rg-R%C3%BCdiger_Sack |
| "Min-max heaps and generalized priority queues" | https://web.archive.org/web/20070127093845/http://cg.scs.carleton.ca/%7Emorin/teaching/5408/refs/minmax.pdf |
| the original | http://cg.scs.carleton.ca/~morin/teaching/5408/refs/minmax.pdf |
| a | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-CLRS_19-0 |
| b | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-CLRS_19-1 |
| c | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-CLRS_19-2 |
| d | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-CLRS_19-3 |
| Cormen, Thomas H. | https://en.wikipedia.org/wiki/Thomas_H._Cormen |
| Leiserson, Charles E. | https://en.wikipedia.org/wiki/Charles_E._Leiserson |
| Rivest, Ronald L. | https://en.wikipedia.org/wiki/Ron_Rivest |
| Introduction to Algorithms | https://en.wikipedia.org/wiki/Introduction_to_Algorithms |
| ISBN | https://en.wikipedia.org/wiki/ISBN_(identifier) |
| 0-262-03141-8 | https://en.wikipedia.org/wiki/Special:BookSources/0-262-03141-8 |
| a | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-sleator-tarjan-skew_20-0 |
| b | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-sleator-tarjan-skew_20-1 |
| c | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-sleator-tarjan-skew_20-2 |
| Sleator, Daniel Dominic | https://en.wikipedia.org/wiki/Daniel_Sleator |
| Tarjan, Robert Endre | https://en.wikipedia.org/wiki/Robert_Tarjan |
| "Self-Adjusting Heaps" | https://www.cs.cmu.edu/~sleator/papers/Adjusting-Heaps.htm |
| SIAM Journal on Computing | https://en.wikipedia.org/wiki/SIAM_Journal_on_Computing |
| CiteSeerX | https://en.wikipedia.org/wiki/CiteSeerX_(identifier) |
| 10.1.1.93.6678 | https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.93.6678 |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1137/0215004 | https://doi.org/10.1137%2F0215004 |
| ISSN | https://en.wikipedia.org/wiki/ISSN_(identifier) |
| 0097-5397 | https://search.worldcat.org/issn/0097-5397 |
| a | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-tarjan-leftist_21-0 |
| b | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-tarjan-leftist_21-1 |
| Tarjan, Robert | https://en.wikipedia.org/wiki/Robert_Tarjan |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1137/1.9781611970265 | https://doi.org/10.1137%2F1.9781611970265 |
| ISBN | https://en.wikipedia.org/wiki/ISBN_(identifier) |
| 978-0-89871-187-5 | https://en.wikipedia.org/wiki/Special:BookSources/978-0-89871-187-5 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-hayward-mcdiarmid-heap-build_22-0 |
| "Average Case Analysis of Heap Building by Repeated Insertion" | https://web.archive.org/web/20160205023201/http://www.stats.ox.ac.uk/__data/assets/pdf_file/0015/4173/heapbuildjalg.pdf |
| CiteSeerX | https://en.wikipedia.org/wiki/CiteSeerX_(identifier) |
| 10.1.1.353.7888 | https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.353.7888 |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1016/0196-6774(91)90027-v | https://doi.org/10.1016%2F0196-6774%2891%2990027-v |
| the original | http://www.stats.ox.ac.uk/__data/assets/pdf_file/0015/4173/heapbuildjalg.pdf |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-24 |
| "Binomial Heap | Brilliant Math & Science Wiki" | https://brilliant.org/wiki/binomial-heap/ |
| a | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-brodal-okasaki_26-0 |
| b | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-brodal-okasaki_26-1 |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1017/s095679680000201x | https://doi.org/10.1017%2Fs095679680000201x |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-27 |
| Okasaki, Chris | https://en.wikipedia.org/wiki/Chris_Okasaki |
| ISBN | https://en.wikipedia.org/wiki/ISBN_(identifier) |
| 9780521631242 | https://en.wikipedia.org/wiki/Special:BookSources/9780521631242 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-28 |
| Takaoka, Tadao | https://en.wikipedia.org/w/index.php?title=Tadao_Takaoka&action=edit&redlink=1 |
| Theory of 2–3 Heaps | https://ir.canterbury.ac.nz/bitstream/handle/10092/14769/2-3heaps.pdf |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-Iacono_29-0 |
| Iacono, John | https://en.wikipedia.org/wiki/John_Iacono |
| Proc. 7th Scandinavian Workshop on Algorithm Theory | http://john2.poly.edu/papers/swat00/paper.pdf |
| arXiv | https://en.wikipedia.org/wiki/ArXiv_(identifier) |
| 1110.4428 | https://arxiv.org/abs/1110.4428 |
| CiteSeerX | https://en.wikipedia.org/wiki/CiteSeerX_(identifier) |
| 10.1.1.748.7812 | https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.748.7812 |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1007/3-540-44985-X_5 | https://doi.org/10.1007%2F3-540-44985-X_5 |
| ISBN | https://en.wikipedia.org/wiki/ISBN_(identifier) |
| 3-540-67690-2 | https://en.wikipedia.org/wiki/Special:BookSources/3-540-67690-2 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-Fredman1999_30-0 |
| Fredman, Michael Lawrence | https://en.wikipedia.org/wiki/Michael_Fredman |
| "On the Efficiency of Pairing Heaps and Related Data Structures" | http://www.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf |
| Journal of the Association for Computing Machinery | https://en.wikipedia.org/wiki/Journal_of_the_Association_for_Computing_Machinery |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1145/320211.320214 | https://doi.org/10.1145%2F320211.320214 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-31 |
| Towards a Final Analysis of Pairing Heaps | http://web.eecs.umich.edu/~pettie/papers/focs05.pdf |
| CiteSeerX | https://en.wikipedia.org/wiki/CiteSeerX_(identifier) |
| 10.1.1.549.471 | https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.549.471 |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1109/SFCS.2005.75 | https://doi.org/10.1109%2FSFCS.2005.75 |
| ISBN | https://en.wikipedia.org/wiki/ISBN_(identifier) |
| 0-7695-2468-0 | https://en.wikipedia.org/wiki/Special:BookSources/0-7695-2468-0 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-33 |
| Tarjan, Robert E. | https://en.wikipedia.org/wiki/Robert_Tarjan |
| "Rank-pairing heaps" | http://sidsen.org/papers/rp-heaps-journal.pdf |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1137/100785351 | https://doi.org/10.1137%2F100785351 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-Fredman_And_Tarjan_34-0 |
| Fredman, Michael Lawrence | https://en.wikipedia.org/wiki/Michael_Fredman |
| Tarjan, Robert E. | https://en.wikipedia.org/wiki/Robert_Tarjan |
| "Fibonacci heaps and their uses in improved network optimization algorithms" | http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Fibonacci-Heap-Tarjan.pdf |
| Journal of the Association for Computing Machinery | https://en.wikipedia.org/wiki/Journal_of_the_Association_for_Computing_Machinery |
| CiteSeerX | https://en.wikipedia.org/wiki/CiteSeerX_(identifier) |
| 10.1.1.309.8927 | https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.309.8927 |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1145/28869.28874 | https://doi.org/10.1145%2F28869.28874 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-35 |
| Brodal, Gerth Stølting | https://en.wikipedia.org/wiki/Gerth_St%C3%B8lting_Brodal |
| Tarjan, Robert E. | https://en.wikipedia.org/wiki/Robert_Tarjan |
| Strict Fibonacci heaps | http://www.cs.au.dk/~gerth/papers/stoc12.pdf |
| CiteSeerX | https://en.wikipedia.org/wiki/CiteSeerX_(identifier) |
| 10.1.1.233.1740 | https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.233.1740 |
| doi | https://en.wikipedia.org/wiki/Doi_(identifier) |
| 10.1145/2213977.2214082 | https://doi.org/10.1145%2F2213977.2214082 |
| ISBN | https://en.wikipedia.org/wiki/ISBN_(identifier) |
| 978-1-4503-1245-5 | https://en.wikipedia.org/wiki/Special:BookSources/978-1-4503-1245-5 |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-37 |
| Brodal, Gerth S. | https://en.wikipedia.org/wiki/Gerth_St%C3%B8lting_Brodal |
| "Worst-Case Efficient Priority Queues" | http://www.cs.au.dk/~gerth/papers/soda96.pdf |
| ^ | https://en.wikipedia.org/wiki/Binary_heap#cite_ref-38 |
| Goodrich, Michael T. | https://en.wikipedia.org/wiki/Michael_T._Goodrich |
| Tamassia, Roberto | https://en.wikipedia.org/wiki/Roberto_Tamassia |
| ISBN | https://en.wikipedia.org/wiki/ISBN_(identifier) |
| 0-471-46983-1 | https://en.wikipedia.org/wiki/Special:BookSources/0-471-46983-1 |
| edit | https://en.wikipedia.org/w/index.php?title=Binary_heap&action=edit§ion=16 |
| Open Data Structures - Section 10.1 - BinaryHeap: An Implicit Binary Tree | http://opendatastructures.org/versions/edition-0.1e/ods-java/10_1_BinaryHeap_Implicit_Bi.html |
| Pat Morin | https://en.wikipedia.org/wiki/Pat_Morin |
| Implementation of binary max heap in C | https://robin-thomas.github.io/max-heap/ |
| Implementation of binary min heap in C | https://robin-thomas.github.io/min-heap/ |
| v | https://en.wikipedia.org/wiki/Template:Data_structures |
| t | https://en.wikipedia.org/wiki/Template_talk:Data_structures |
| e | https://en.wikipedia.org/wiki/Special:EditPage/Template:Data_structures |
| Data structures | https://en.wikipedia.org/wiki/Data_structure |
| Collection | https://en.wikipedia.org/wiki/Collection_(abstract_data_type) |
| Container | https://en.wikipedia.org/wiki/Container_(abstract_data_type) |
| Abstract | https://en.wikipedia.org/wiki/Abstract_data_type |
| Associative array | https://en.wikipedia.org/wiki/Associative_array |
| Multimap | https://en.wikipedia.org/wiki/Multimap |
| Retrieval Data Structure | https://en.wikipedia.org/wiki/Retrieval_Data_Structure |
| List | https://en.wikipedia.org/wiki/List_(abstract_data_type) |
| Stack | https://en.wikipedia.org/wiki/Stack_(abstract_data_type) |
| Queue | https://en.wikipedia.org/wiki/Queue_(abstract_data_type) |
| Double-ended queue | https://en.wikipedia.org/wiki/Double-ended_queue |
| Priority queue | https://en.wikipedia.org/wiki/Priority_queue |
| Double-ended priority queue | https://en.wikipedia.org/wiki/Double-ended_priority_queue |
| Set | https://en.wikipedia.org/wiki/Set_(abstract_data_type) |
| Multiset | https://en.wikipedia.org/wiki/Set_(abstract_data_type)#Multiset |
| Disjoint-set | https://en.wikipedia.org/wiki/Disjoint-set_data_structure |
| Arrays | https://en.wikipedia.org/wiki/Array_(data_structure) |
| Bit array | https://en.wikipedia.org/wiki/Bit_array |
| Circular buffer | https://en.wikipedia.org/wiki/Circular_buffer |
| Dynamic array | https://en.wikipedia.org/wiki/Dynamic_array |
| Hash table | https://en.wikipedia.org/wiki/Hash_table |
| Hashed array tree | https://en.wikipedia.org/wiki/Hashed_array_tree |
| Sparse matrix | https://en.wikipedia.org/wiki/Sparse_matrix |
| Linked | https://en.wikipedia.org/wiki/Linked_data_structure |
| Association list | https://en.wikipedia.org/wiki/Association_list |
| Linked list | https://en.wikipedia.org/wiki/Linked_list |
| Skip list | https://en.wikipedia.org/wiki/Skip_list |
| Unrolled linked list | https://en.wikipedia.org/wiki/Unrolled_linked_list |
| XOR linked list | https://en.wikipedia.org/wiki/XOR_linked_list |
| Trees | https://en.wikipedia.org/wiki/Tree_(data_structure) |
| B-tree | https://en.wikipedia.org/wiki/B-tree |
| Binary search tree | https://en.wikipedia.org/wiki/Binary_search_tree |
| AA tree | https://en.wikipedia.org/wiki/AA_tree |
| AVL tree | https://en.wikipedia.org/wiki/AVL_tree |
| Red–black tree | https://en.wikipedia.org/wiki/Red%E2%80%93black_tree |
| Self-balancing tree | https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree |
| Splay tree | https://en.wikipedia.org/wiki/Splay_tree |
| Heap | https://en.wikipedia.org/wiki/Heap_(data_structure) |
| Binomial heap | https://en.wikipedia.org/wiki/Binomial_heap |
| Fibonacci heap | https://en.wikipedia.org/wiki/Fibonacci_heap |
| R-tree | https://en.wikipedia.org/wiki/R-tree |
| R* tree | https://en.wikipedia.org/wiki/R*_tree |
| R+ tree | https://en.wikipedia.org/wiki/R%2B_tree |
| Hilbert R-tree | https://en.wikipedia.org/wiki/Hilbert_R-tree |
| Rope | https://en.wikipedia.org/wiki/Rope_(data_structure) |
| Trie | https://en.wikipedia.org/wiki/Trie |
| Hash tree | https://en.wikipedia.org/wiki/Hash_tree_(persistent_data_structure) |
| Graphs | https://en.wikipedia.org/wiki/Graph_(abstract_data_type) |
| Binary decision diagram | https://en.wikipedia.org/wiki/Binary_decision_diagram |
| Directed acyclic graph | https://en.wikipedia.org/wiki/Directed_acyclic_graph |
| Directed acyclic word graph | https://en.wikipedia.org/wiki/Deterministic_acyclic_finite_state_automaton |
| List of data structures | https://en.wikipedia.org/wiki/List_of_data_structures |
| https://en.wikipedia.org/w/index.php?title=Binary_heap&oldid=1350857347 | https://en.wikipedia.org/w/index.php?title=Binary_heap&oldid=1350857347 |
| Categories | https://en.wikipedia.org/wiki/Help:Category |
| Heaps (data structures) | https://en.wikipedia.org/wiki/Category:Heaps_(data_structures) |
| Binary trees | https://en.wikipedia.org/wiki/Category:Binary_trees |
| Webarchive template wayback links | https://en.wikipedia.org/wiki/Category:Webarchive_template_wayback_links |
| Articles with short description | https://en.wikipedia.org/wiki/Category:Articles_with_short_description |
| Short description is different from Wikidata | https://en.wikipedia.org/wiki/Category:Short_description_is_different_from_Wikidata |
| Creative Commons Attribution-ShareAlike 4.0 License | https://en.wikipedia.org/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License |
| Terms of Use | https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use |
| Privacy Policy | https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy |
| Wikimedia Foundation, Inc. | https://wikimediafoundation.org/ |
| Privacy policy | https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy |
| About Wikipedia | https://en.wikipedia.org/wiki/Wikipedia:About |
| Disclaimers | https://en.wikipedia.org/wiki/Wikipedia:General_disclaimer |
| Contact Wikipedia | https://en.wikipedia.org/wiki/Wikipedia:Contact_us |
| Legal & safety contacts | https://foundation.wikimedia.org/wiki/Special:MyLanguage/Legal:Wikimedia_Foundation_Legal_and_Safety_Contact_Information |
| Code of Conduct | https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct |
| Developers | https://developer.wikimedia.org |
| Statistics | https://stats.wikimedia.org/#/en.wikipedia.org |
| Cookie statement | https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement |
| Mobile view | https://en.wikipedia.org/w/index.php?title=Binary_heap&mobileaction=toggle_view_mobile |
| https://www.wikimedia.org/ |
| https://www.mediawiki.org/ |
|
| https://en.wikipedia.org/wiki/Binary_heap |
|
| https://en.wikipedia.org/wiki/Binary_heap |
|
| https://en.wikipedia.org/wiki/Binary_heap |
|
| https://en.wikipedia.org/wiki/Binary_heap |
|
| https://en.wikipedia.org/wiki/Binary_heap |
|
| https://en.wikipedia.org/wiki/Binary_heap |
|
| https://en.wikipedia.org/wiki/Binary_heap |
|
Add topic
| https://en.wikipedia.org/wiki/Binary_heap |
