CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Binomial heap - Wikipedia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )enwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":["",""],"wgDigitTransformTable":["",""],"wgDefaultDateFormat":"dmy", "wgMonthNames":["","January","February","March","April","May","June","July","August","September","October","November","December"],"wgRequestId":"a7fcfb38-1c66-45cc-8c47-535d686eee28","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Binomial_heap","wgTitle":"Binomial heap","wgCurRevisionId":1221086681,"wgRevisionId":1221086681,"wgArticleId":254138,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","Use dmy dates from May 2018","All articles with unsourced statements","Articles with unsourced statements from October 2019","Heaps (data structures)"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Binomial_heap","wgRelevantArticleId":254138,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit":[], "wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":false,"wgFlaggedRevsParams":{"tags":{"status":{"levels":1}}},"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"en","pageLanguageDir":"ltr","pageVariantFallbacks":"en"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":false,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":10000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q864032","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false, "wgGELevelingUpEnabledForUser":false};RLSTATE={"ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","ext.cite.styles":"ready","ext.math.styles":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","jquery.makeCollapsible.styles":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","mediawiki.page.media","site","mediawiki.page.ready","jquery.makeCollapsible","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ReferenceTooltips","ext.gadget.switcher","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init", "ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions","wikibase.client.vector-2022","ext.checkUser.clientHints","ext.growthExperiments.SuggestedEditSession","wikibase.sidebar.tracking"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=en&modules=ext.cite.styles%7Cext.math.styles%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cjquery.makeCollapsible.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=en&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=en&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.5"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Binomial heap - Wikipedia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//en.m.wikipedia.org/wiki/Binomial_heap"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Binomial_heap&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipedia (en)"> <link rel="EditURI" type="application/rsd+xml" href="//en.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://en.wikipedia.org/wiki/Binomial_heap"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en"> <link rel="alternate" type="application/atom+xml" title="Wikipedia Atom feed" href="/w/index.php?title=Special:RecentChanges&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="//login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Binomial_heap rootpage-Binomial_heap skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Jump to content</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Main menu" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Main menu</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Main menu</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">hide</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Main_Page" title="Visit the main page [z]" accesskey="z"><span>Main page</span></a></li><li id="n-contents" class="mw-list-item"><a href="/wiki/Wikipedia:Contents" title="Guides to browsing Wikipedia"><span>Contents</span></a></li><li id="n-currentevents" class="mw-list-item"><a href="/wiki/Portal:Current_events" title="Articles related to current events"><span>Current events</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Special:Random" title="Visit a randomly selected article [x]" accesskey="x"><span>Random article</span></a></li><li id="n-aboutsite" class="mw-list-item"><a href="/wiki/Wikipedia:About" title="Learn about Wikipedia and how it works"><span>About Wikipedia</span></a></li><li id="n-contactpage" class="mw-list-item"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us" title="How to contact Wikipedia"><span>Contact us</span></a></li> </ul> </div> </div> <div id="p-interaction" class="vector-menu mw-portlet mw-portlet-interaction" > <div class="vector-menu-heading"> Contribute </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-help" class="mw-list-item"><a href="/wiki/Help:Contents" title="Guidance on how to use and edit Wikipedia"><span>Help</span></a></li><li id="n-introduction" class="mw-list-item"><a href="/wiki/Help:Introduction" title="Learn how to edit Wikipedia"><span>Learn to edit</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikipedia:Community_portal" title="The hub for editors"><span>Community portal</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Special:RecentChanges" title="A list of recent changes to Wikipedia [r]" accesskey="r"><span>Recent changes</span></a></li><li id="n-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_upload_wizard" title="Add images or other media for use on Wikipedia"><span>Upload file</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Main_Page" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipedia" src="/static/images/mobile/copyright/wikipedia-wordmark-en.svg" style="width: 7.5em; height: 1.125em;"> <img class="mw-logo-tagline" alt="The Free Encyclopedia" src="/static/images/mobile/copyright/wikipedia-tagline-en.svg" width="117" height="13" style="width: 7.3125em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Special:Search" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Search Wikipedia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Search Wikipedia" aria-label="Search Wikipedia" autocapitalize="sentences" title="Search Wikipedia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Special:Search"> </div> <button class="cdx-button cdx-search-input__end-button">Search</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Personal tools"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Change the appearance of the page's font size, width, and color" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Appearance" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Appearance</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en" class=""><span>Donate</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:CreateAccount&returnto=Binomial+heap" title="You are encouraged to create an account and log in; however, it is not mandatory" class=""><span>Create account</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Special:UserLogin&returnto=Binomial+heap" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o" class=""><span>Log in</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Log in and more options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Personal tools" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Personal tools</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="User menu" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/wiki/Special:FundraiserRedirector?utm_source=donate&utm_medium=sidebar&utm_campaign=C13_en.wikipedia.org&uselang=en"><span>Donate</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:CreateAccount&returnto=Binomial+heap" title="You are encouraged to create an account and log in; however, it is not mandatory"><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Create account</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Special:UserLogin&returnto=Binomial+heap" title="You're encouraged to log in; however, it's not mandatory. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Log in</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages for logged out editors <a href="/wiki/Help:Introduction" aria-label="Learn more about editing"><span>learn more</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Special:MyContributions" title="A list of edits made from this IP address [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Special:MyTalk" title="Discussion about edits from this IP address [n]" accesskey="n"><span>Talk</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Contents" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Contents</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">hide</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">(Top)</div> </a> </li> <li id="toc-Binomial_heap" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Binomial_heap"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Binomial heap</span> </div> </a> <ul id="toc-Binomial_heap-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Structure_of_a_binomial_heap" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Structure_of_a_binomial_heap"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Structure of a binomial heap</span> </div> </a> <ul id="toc-Structure_of_a_binomial_heap-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementation" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Implementation"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Implementation</span> </div> </a> <button aria-controls="toc-Implementation-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Toggle Implementation subsection</span> </button> <ul id="toc-Implementation-sublist" class="vector-toc-list"> <li id="toc-Merge" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Merge"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.1</span> <span>Merge</span> </div> </a> <ul id="toc-Merge-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Insert" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Insert"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.2</span> <span>Insert</span> </div> </a> <ul id="toc-Insert-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Find_minimum" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Find_minimum"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.3</span> <span>Find minimum</span> </div> </a> <ul id="toc-Find_minimum-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Delete_minimum" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Delete_minimum"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.4</span> <span>Delete minimum</span> </div> </a> <ul id="toc-Delete_minimum-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Decrease_key" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Decrease_key"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.5</span> <span>Decrease key</span> </div> </a> <ul id="toc-Decrease_key-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Delete" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Delete"> <div class="vector-toc-text"> <span class="vector-toc-numb">3.6</span> <span>Delete</span> </div> </a> <ul id="toc-Delete-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> <li id="toc-Summary_of_running_times" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Summary_of_running_times"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Summary of running times</span> </div> </a> <ul id="toc-Summary_of_running_times-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Applications" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Applications"> <div class="vector-toc-text"> <span class="vector-toc-numb">5</span> <span>Applications</span> </div> </a> <ul id="toc-Applications-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-See_also" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#See_also"> <div class="vector-toc-text"> <span class="vector-toc-numb">6</span> <span>See also</span> </div> </a> <ul id="toc-See_also-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-References" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#References"> <div class="vector-toc-text"> <span class="vector-toc-numb">7</span> <span>References</span> </div> </a> <ul id="toc-References-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-External_links" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#External_links"> <div class="vector-toc-text"> <span class="vector-toc-numb">8</span> <span>External links</span> </div> </a> <ul id="toc-External_links-sublist" class="vector-toc-list"> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Toggle the table of contents</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Binomial heap</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Go to an article in another language. Available in 16 languages" > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-16" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">16 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-ar mw-list-item"><a href="https://ar.wikipedia.org/wiki/%D9%83%D9%88%D9%85%D8%A9_%D8%B0%D8%A7%D8%AA_%D8%AD%D8%AF%D9%8A%D9%86" title="كومة ذات حدين – Arabic" lang="ar" hreflang="ar" data-title="كومة ذات حدين" data-language-autonym="العربية" data-language-local-name="Arabic" class="interlanguage-link-target"><span>العربية</span></a></li><li class="interlanguage-link interwiki-cs mw-list-item"><a href="https://cs.wikipedia.org/wiki/Binomi%C3%A1ln%C3%AD_halda" title="Binomiální halda – Czech" lang="cs" hreflang="cs" data-title="Binomiální halda" data-language-autonym="Čeština" data-language-local-name="Czech" class="interlanguage-link-target"><span>Čeština</span></a></li><li class="interlanguage-link interwiki-de badge-Q17437798 badge-goodarticle mw-list-item" title="good article badge"><a href="https://de.wikipedia.org/wiki/Binomial-Heap" title="Binomial-Heap – German" lang="de" hreflang="de" data-title="Binomial-Heap" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Heap_Binomial" title="Heap Binomial – Spanish" lang="es" hreflang="es" data-title="Heap Binomial" data-language-autonym="Español" data-language-local-name="Spanish" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%BE%D8%B4%D8%AA%D9%87%E2%80%8C%D9%87%D8%A7%DB%8C_%D8%AF%D9%88%D8%AC%D9%85%D9%84%D9%87%E2%80%8C%D8%A7%DB%8C" title="پشته‌های دوجمله‌ای – Persian" lang="fa" hreflang="fa" data-title="پشته‌های دوجمله‌ای" data-language-autonym="فارسی" data-language-local-name="Persian" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-fr mw-list-item"><a href="https://fr.wikipedia.org/wiki/Tas_binomial" title="Tas binomial – French" lang="fr" hreflang="fr" data-title="Tas binomial" data-language-autonym="Français" data-language-local-name="French" class="interlanguage-link-target"><span>Français</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%ED%9E%99" title="이항 힙 – Korean" lang="ko" hreflang="ko" data-title="이항 힙" data-language-autonym="한국어" data-language-local-name="Korean" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Heap_binomiale" title="Heap binomiale – Italian" lang="it" hreflang="it" data-title="Heap binomiale" data-language-autonym="Italiano" data-language-local-name="Italian" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-he mw-list-item"><a href="https://he.wikipedia.org/wiki/%D7%A2%D7%A8%D7%99%D7%9E%D7%94_%D7%91%D7%99%D7%A0%D7%95%D7%9E%D7%99%D7%AA" title="ערימה בינומית – Hebrew" lang="he" hreflang="he" data-title="ערימה בינומית" data-language-autonym="עברית" data-language-local-name="Hebrew" class="interlanguage-link-target"><span>עברית</span></a></li><li class="interlanguage-link interwiki-ja mw-list-item"><a href="https://ja.wikipedia.org/wiki/%E4%BA%8C%E9%A0%85%E3%83%92%E3%83%BC%E3%83%97" title="二項ヒープ – Japanese" lang="ja" hreflang="ja" data-title="二項ヒープ" data-language-autonym="日本語" data-language-local-name="Japanese" class="interlanguage-link-target"><span>日本語</span></a></li><li class="interlanguage-link interwiki-pl mw-list-item"><a href="https://pl.wikipedia.org/wiki/Kopiec_dwumianowy" title="Kopiec dwumianowy – Polish" lang="pl" hreflang="pl" data-title="Kopiec dwumianowy" data-language-autonym="Polski" data-language-local-name="Polish" class="interlanguage-link-target"><span>Polski</span></a></li><li class="interlanguage-link interwiki-pt mw-list-item"><a href="https://pt.wikipedia.org/wiki/Heap_binomial" title="Heap binomial – Portuguese" lang="pt" hreflang="pt" data-title="Heap binomial" data-language-autonym="Português" data-language-local-name="Portuguese" class="interlanguage-link-target"><span>Português</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0" title="Биномиальная куча – Russian" lang="ru" hreflang="ru" data-title="Биномиальная куча" data-language-autonym="Русский" data-language-local-name="Russian" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/%D0%91%D0%B8%D0%BD%D0%BE%D0%BC%D0%BD%D0%B8_%D1%85%D0%B8%D0%BF" title="Биномни хип – Serbian" lang="sr" hreflang="sr" data-title="Биномни хип" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%91%D1%96%D0%BD%D0%BE%D0%BC%D1%96%D0%B0%D0%BB%D1%8C%D0%BD%D0%B0_%D0%BA%D1%83%D0%BF%D0%B0" title="Біноміальна купа – Ukrainian" lang="uk" hreflang="uk" data-title="Біноміальна купа" data-language-autonym="Українська" data-language-local-name="Ukrainian" class="interlanguage-link-target"><span>Українська</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E4%BA%8C%E9%A1%B9%E5%A0%86" title="二项堆 – Chinese" lang="zh" hreflang="zh" data-title="二项堆" data-language-autonym="中文" data-language-local-name="Chinese" class="interlanguage-link-target"><span>中文</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q864032#sitelinks-wikipedia" title="Edit interlanguage links" class="wbc-editpage">Edit links</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Namespaces"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Binomial_heap" title="View the content page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Talk:Binomial_heap" rel="discussion" title="Discuss improvements to the content page [t]" accesskey="t"><span>Talk</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Change language variant" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">English</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Views"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Binomial_heap"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Binomial_heap&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Binomial_heap&action=history" title="Past revisions of this page [h]" accesskey="h"><span>View history</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Tools" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Tools</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Tools</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">hide</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="More options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Binomial_heap"><span>Read</span></a></li><li id="ca-more-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Binomial_heap&action=edit" title="Edit this page [e]" accesskey="e"><span>Edit</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Binomial_heap&action=history"><span>View history</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> General </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Special:WhatLinksHere/Binomial_heap" title="List of all English Wikipedia pages containing links to this page [j]" accesskey="j"><span>What links here</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Special:RecentChangesLinked/Binomial_heap" rel="nofollow" title="Recent changes in pages linked from this page [k]" accesskey="k"><span>Related changes</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages" title="A list of all special pages [q]" accesskey="q"><span>Special pages</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Binomial_heap&oldid=1221086681" title="Permanent link to this revision of this page"><span>Permanent link</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Binomial_heap&action=info" title="More information about this page"><span>Page information</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Special:CiteThisPage&page=Binomial_heap&id=1221086681&wpFormIdentifier=titleform" title="Information on how to cite this page"><span>Cite this page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Special:UrlShortener&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBinomial_heap"><span>Get shortened URL</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Special:QrCode&url=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FBinomial_heap"><span>Download QR code</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Print/export </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Special:DownloadAsPdf&page=Binomial_heap&action=show-download-screen" title="Download this page as a PDF file"><span>Download as PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Binomial_heap&printable=yes" title="Printable version of this page [p]" accesskey="p"><span>Printable version</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> In other projects </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="wb-otherproject-link wb-otherproject-commons mw-list-item"><a href="https://commons.wikimedia.org/wiki/Category:Binomial_heap" hreflang="en"><span>Wikimedia Commons</span></a></li><li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q864032" title="Structured data on this page hosted by Wikidata [g]" accesskey="g"><span>Wikidata item</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Page tools"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Appearance"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Appearance</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">move to sidebar</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">hide</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">From Wikipedia, the free encyclopedia</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="en" dir="ltr"><div class="shortdescription nomobile noexcerpt noprint searchaux" style="display:none">Data structure that acts as a priority queue</div> <p class="mw-empty-elt"> </p> <style data-mw-deduplicate="TemplateStyles:r1236090951">.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}</style><div role="note" class="hatnote navigation-not-searchable">"Binomial tree" redirects here. For binomial price trees, see <a href="/wiki/Binomial_options_pricing_model" title="Binomial options pricing model">binomial options pricing model</a>.</div> <style data-mw-deduplicate="TemplateStyles:r1257001546">.mw-parser-output .infobox-subbox{padding:0;border:none;margin:-3px;width:auto;min-width:100%;font-size:100%;clear:none;float:none;background-color:transparent}.mw-parser-output .infobox-3cols-child{margin:auto}.mw-parser-output .infobox .navbar{font-size:100%}@media screen{html.skin-theme-clientpref-night .mw-parser-output .infobox-full-data:not(.notheme)>div:not(.notheme)[style]{background:#1f1f23!important;color:#f8f9fa}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .infobox-full-data:not(.notheme) div:not(.notheme){background:#1f1f23!important;color:#f8f9fa}}@media(min-width:640px){body.skin--responsive .mw-parser-output .infobox-table{display:table!important}body.skin--responsive .mw-parser-output .infobox-table>caption{display:table-caption!important}body.skin--responsive .mw-parser-output .infobox-table>tbody{display:table-row-group}body.skin--responsive .mw-parser-output .infobox-table tr{display:table-row!important}body.skin--responsive .mw-parser-output .infobox-table th,body.skin--responsive .mw-parser-output .infobox-table td{padding-left:inherit;padding-right:inherit}}</style><table class="infobox"><tbody><tr><th colspan="2" class="infobox-above">Binomial heap</th></tr><tr><th scope="row" class="infobox-label"><a href="/wiki/List_of_data_structures" title="List of data structures">Type</a></th><td class="infobox-data"><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">heap</a></td></tr><tr><th scope="row" class="infobox-label">Invented</th><td class="infobox-data">1978</td></tr><tr><th scope="row" class="infobox-label">Invented by</th><td class="infobox-data">Jean Vuillemin</td></tr><tr><th colspan="2" class="infobox-header">Complexities in <a href="/wiki/Big_O_notation" title="Big O notation">big O notation</a></th></tr><tr><td colspan="2" class="infobox-full-data"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1257001546"><table class="infobox-subbox infobox-3cols-child infobox-table"><tbody><tr><th colspan="4" class="infobox-header"><a href="/wiki/Space_complexity" title="Space complexity">Space complexity</a></th></tr><tr><th colspan="4" class="infobox-header"><a href="/wiki/Time_complexity" title="Time complexity">Time complexity</a></th></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Function</th><td class="infobox-data infobox-data-a"> </td><td class="infobox-data infobox-data-b"> <a href="/wiki/Amortized_analysis" title="Amortized analysis"><b>Amortized</b></a></td><td class="infobox-data infobox-data-c"> <a href="/wiki/Best,_worst_and_average_case" title="Best, worst and average case"><b>Worst Case</b></a></td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Insert</th><td class="infobox-data infobox-data-a"> </td><td class="infobox-data infobox-data-b"> <i>Θ</i>(1)</td><td class="infobox-data infobox-data-c"> O(log <i>n</i>)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Find-min</th><td class="infobox-data infobox-data-a"> </td><td class="infobox-data infobox-data-b"> <i>Θ</i>(1)</td><td class="infobox-data infobox-data-c"> O(1)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Delete-min</th><td class="infobox-data infobox-data-a"> </td><td class="infobox-data infobox-data-b"> <i>Θ</i>(log <i>n</i>)</td><td class="infobox-data infobox-data-c"> O(log <i>n</i>)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Decrease-key</th><td class="infobox-data infobox-data-a"> </td><td class="infobox-data infobox-data-b"> <i>Θ</i>(log <i>n</i>)</td><td class="infobox-data infobox-data-c"> O(log <i>n</i>)</td></tr><tr><th scope="row" class="infobox-label" style="white-space:nowrap;">Merge</th><td class="infobox-data infobox-data-a"> </td><td class="infobox-data infobox-data-b"> <i>Θ</i>(log <i>n</i>)</td><td class="infobox-data infobox-data-c"> O(log <i>n</i>)</td></tr></tbody></table></td></tr></tbody></table> <p>In <a href="/wiki/Computer_science" title="Computer science">computer science</a>, a <b>binomial heap</b> is a <a href="/wiki/Data_structure" title="Data structure">data structure</a> that acts as a <a href="/wiki/Priority_queue" title="Priority queue">priority queue</a>. It is an example of a <a href="/wiki/Mergeable_heap" title="Mergeable heap">mergeable heap</a> (also called meldable heap), as it supports merging two heaps in logarithmic time. It is implemented as a <a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">heap</a> similar to a <a href="/wiki/Binary_heap" title="Binary heap">binary heap</a> but using a special tree structure that is different from the <a href="/wiki/Complete_binary_tree" class="mw-redirect" title="Complete binary tree">complete binary trees</a> used by binary heaps.<sup id="cite_ref-clrs_1-0" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Binomial heaps were invented in 1978 by <a href="/wiki/Jean_Vuillemin" title="Jean Vuillemin">Jean Vuillemin</a>.<sup id="cite_ref-clrs_1-1" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Binomial_heap">Binomial heap</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=1" title="Edit section: Binomial heap"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A binomial heap is implemented as a set of <b>binomial <a href="/wiki/Tree_data_structure" class="mw-redirect" title="Tree data structure">trees</a></b> (compare with a <a href="/wiki/Binary_heap" title="Binary heap">binary heap</a>, which has a shape of a single <a href="/wiki/Binary_tree" title="Binary tree">binary tree</a>), which are defined recursively as follows:<sup id="cite_ref-clrs_1-2" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p> <ul><li>A binomial tree of order 0 is a single node</li> <li>A binomial tree of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> has a root node whose children are roots of binomial trees of orders <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/21363ebd7038c93aae93127e7d910fc1b2e2c745" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}"></span>, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-2}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>−</mo> <mn>2</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k-2}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7fd591543c6ffeba17bb12075476c00165f54e9e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-2}"></span>, ..., 2, 1, 0 (in this order).</li></ul> <figure class="mw-halign-center" typeof="mw:File/Thumb"><a href="/wiki/File:Binomial_Trees.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/500px-Binomial_Trees.svg.png" decoding="async" width="500" height="286" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/750px-Binomial_Trees.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Binomial_Trees.svg/1000px-Binomial_Trees.svg.png 2x" data-file-width="700" data-file-height="400" /></a><figcaption>Binomial trees of order 0 to 3: Each tree has a root node with subtrees of all lower ordered binomial trees, which have been highlighted. For example, the order 3 binomial tree is connected to an order 2, 1, and 0 (highlighted as blue, green and red respectively) binomial tree.</figcaption></figure> <p>A binomial tree of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> has <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{k}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mi>k</mi> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{k}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2d82641ae2702b0db07dd11830af27b9ee0cd196" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.251ex; height:2.676ex;" alt="{\displaystyle 2^{k}}"></span> nodes, and height <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span>. The name comes from the shape: a binomial tree of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> has <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\tbinom {k}{d}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mrow> <mrow class="MJX-TeXAtom-OPEN"> <mo maxsize="1.2em" minsize="1.2em">(</mo> </mrow> <mfrac linethickness="0"> <mi>k</mi> <mi>d</mi> </mfrac> <mrow class="MJX-TeXAtom-CLOSE"> <mo maxsize="1.2em" minsize="1.2em">)</mo> </mrow> </mrow> </mstyle> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle {\tbinom {k}{d}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a3e8e37ad98d84fb1594ca1e31a061d4d7d80357" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:2.99ex; height:3.509ex;" alt="{\displaystyle {\tbinom {k}{d}}}"></span> nodes at depth <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle d}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>d</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle d}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e85ff03cbe0c7341af6b982e47e9f90d235c66ab" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.216ex; height:2.176ex;" alt="{\displaystyle d}"></span>, a <a href="/wiki/Binomial_coefficient" title="Binomial coefficient">binomial coefficient</a>. Because of its structure, a binomial tree of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> can be constructed from two trees of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k-1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> <mo>−</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k-1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/21363ebd7038c93aae93127e7d910fc1b2e2c745" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.214ex; height:2.343ex;" alt="{\displaystyle k-1}"></span> by attaching one of them as the leftmost child of the root of the other tree. This feature is central to the <i>merge</i> operation of a binomial heap, which is its major advantage over other conventional heaps.<sup id="cite_ref-clrs_1-3" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-brown_3-0" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Structure_of_a_binomial_heap">Structure of a binomial heap</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=2" title="Edit section: Structure of a binomial heap"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>A binomial heap is implemented as a set of binomial trees that satisfy the <i>binomial heap properties</i>:<sup id="cite_ref-clrs_1-4" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p> <ul><li>Each binomial tree in a heap obeys the <i><a href="/wiki/Minimum-heap_property" class="mw-redirect" title="Minimum-heap property">minimum-heap property</a></i>: the key of a node is greater than or equal to the key of its parent.</li> <li>There can be at most one binomial tree for each order, including zero order.</li></ul> <p>The first property ensures that the root of each binomial tree contains the smallest key in the tree. It follows that the smallest key in the entire heap is one of the roots.<sup id="cite_ref-clrs_1-5" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>The second property implies that a binomial heap with <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> nodes consists of at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1+\log _{2}n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mn>1</mn> <mo>+</mo> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 1+\log _{2}n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/54b720ebf95f5052e6f4cdddcc16ce1d7ced71b5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:9.811ex; height:2.676ex;" alt="{\displaystyle 1+\log _{2}n}"></span> binomial trees, where <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log _{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c381607e0a0db64e23e9c8483369aec660f7fd8d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.026ex; height:2.676ex;" alt="{\displaystyle \log _{2}}"></span> is the <a href="/wiki/Binary_logarithm" title="Binary logarithm">binary logarithm</a>. The number and orders of these trees are uniquely determined by the number of nodes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>: there is one binomial tree for each nonzero bit in the <a href="/wiki/Binary_numeral_system" class="mw-redirect" title="Binary numeral system">binary</a> representation of the number <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span>. For example, the decimal number 13 is 1101 in binary, <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{3}+2^{2}+2^{0}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>3</mn> </mrow> </msup> <mo>+</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msup> <mo>+</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>0</mn> </mrow> </msup> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle 2^{3}+2^{2}+2^{0}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b7a31157e28dd1c2dac1781d7a3f8b47b9ccfcc4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:12.331ex; height:2.843ex;" alt="{\displaystyle 2^{3}+2^{2}+2^{0}}"></span>, and thus a binomial heap with 13 nodes will consist of three binomial trees of orders 3, 2, and 0 (see figure below).<sup id="cite_ref-clrs_1-6" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-brown_3-1" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <figure class="mw-halign-center" typeof="mw:File/Thumb"><a href="/wiki/File:Binomial-heap-13.svg" class="mw-file-description"><img alt="Example of a binomial heap" src="//upload.wikimedia.org/wikipedia/commons/thumb/6/61/Binomial-heap-13.svg/325px-Binomial-heap-13.svg.png" decoding="async" width="325" height="217" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/6/61/Binomial-heap-13.svg/488px-Binomial-heap-13.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/6/61/Binomial-heap-13.svg/650px-Binomial-heap-13.svg.png 2x" data-file-width="498" data-file-height="333" /></a><figcaption>Example of a binomial heap containing 13 nodes with distinct keys. The heap consists of three binomial trees with orders 0, 2, and 3.</figcaption></figure> <p>The number of different ways that <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> items with distinct keys can be arranged into a binomial heap equals the largest odd divisor of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n!}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>!</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n!}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/bae971720be3cc9b8d82f4cdac89cb89877514a6" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.042ex; height:2.176ex;" alt="{\displaystyle n!}"></span>. For <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=1,2,3,\dots }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> <mo>=</mo> <mn>1</mn> <mo>,</mo> <mn>2</mn> <mo>,</mo> <mn>3</mn> <mo>,</mo> <mo>…</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n=1,2,3,\dots }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b207567215497887a3250644b8876c23dc3ebf10" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:13.806ex; height:2.509ex;" alt="{\displaystyle n=1,2,3,\dots }"></span> these numbers are </p> <dl><dd>1, 1, 3, 3, 15, 45, 315, 315, 2835, 14175, ... (sequence <span class="nowrap external"><a href="//oeis.org/A049606" class="extiw" title="oeis:A049606">A049606</a></span> in the <a href="/wiki/On-Line_Encyclopedia_of_Integer_Sequences" title="On-Line Encyclopedia of Integer Sequences">OEIS</a>)</dd></dl> <p>If the <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a601995d55609f2d9f5e233e36fbe9ea26011b3b" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}"></span> items are inserted into a binomial heap in a uniformly random order, each of these arrangements is equally likely.<sup id="cite_ref-brown_3-2" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Implementation">Implementation</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=3" title="Edit section: Implementation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Because no operation requires random access to the root nodes of the binomial trees, the roots of the binomial trees can be stored in a <a href="/wiki/Linked_list" title="Linked list">linked list</a>, ordered by increasing order of the tree. Because the number of children for each node is variable, it does not work well for each node to have separate links to each of its children, as would be common in a <a href="/wiki/Binary_tree" title="Binary tree">binary tree</a>; instead, it is possible to implement this tree using links from each node to its highest-order child in the tree, and to its sibling of the next smaller order than it. These sibling pointers can be interpreted as the next pointers in a linked list of the children of each node, but with the opposite order from the linked list of roots: from largest to smallest order, rather than vice versa. This representation allows two trees of the same order to be linked together, making a tree of the next larger order, in constant time.<sup id="cite_ref-clrs_1-7" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-brown_3-3" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Merge">Merge</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=4" title="Edit section: Merge"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Binomial_heap_merge1.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Binomial_heap_merge1.svg/200px-Binomial_heap_merge1.svg.png" decoding="async" width="200" height="291" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Binomial_heap_merge1.svg/300px-Binomial_heap_merge1.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/9f/Binomial_heap_merge1.svg/400px-Binomial_heap_merge1.svg.png 2x" data-file-width="275" data-file-height="400" /></a><figcaption>To merge two binomial trees of the same order, first compare the root key. Since 7>3, the black tree on the left (with root node 7) is attached to the grey tree on the right (with root node 3) as a subtree. The result is a tree of order 3.</figcaption></figure> <p>The operation of <b>merging</b> two heaps is used as a subroutine in most other operations. A basic subroutine within this procedure merges pairs of binomial trees of the same order. This may be done by comparing the keys at the roots of the two trees (the smallest keys in both trees). The root node with the larger key is made into a child of the root node with the smaller key, increasing its order by one:<sup id="cite_ref-clrs_1-8" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-brown_3-4" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <pre><b>function</b> mergeTree(p, q) <b>if</b> p.root.key <= q.root.key <b>return</b> p.addSubTree(q) <b>else</b> <b>return</b> q.addSubTree(p) </pre> <figure typeof="mw:File/Thumb"><a href="/wiki/File:Binomial_heap_merge2.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Binomial_heap_merge2.svg/300px-Binomial_heap_merge2.svg.png" decoding="async" width="300" height="248" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Binomial_heap_merge2.svg/450px-Binomial_heap_merge2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/e/e8/Binomial_heap_merge2.svg/600px-Binomial_heap_merge2.svg.png 2x" data-file-width="575" data-file-height="475" /></a><figcaption>This shows the merger of two binomial heaps. This is accomplished by merging two binomial trees of the same order one by one. If the resulting merged tree has the same order as one binomial tree in one of the two heaps, then those two are merged again.</figcaption></figure> <p>To merge two heaps more generally, the lists of roots of both heaps are traversed simultaneously in a manner similar to that of the <a href="/wiki/Merge_algorithm" title="Merge algorithm">merge algorithm</a>, in a sequence from smaller orders of trees to larger orders. When only one of the two heaps being merged contains a tree of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f461e54f5c093e92a55547b9764291390f0b5d0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}"></span>, this tree is moved to the output heap. When both of the two heaps contain a tree of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/2f461e54f5c093e92a55547b9764291390f0b5d0" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:0.985ex; height:2.509ex;" alt="{\displaystyle j}"></span>, the two trees are merged to one tree of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5baf2ec9e436e9309065133555e3cb2ecd88f87e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:4.988ex; height:2.509ex;" alt="{\displaystyle j+1}"></span> so that the minimum-heap property is satisfied. It may later become necessary to merge this tree with some other tree of order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle j+1}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>j</mi> <mo>+</mo> <mn>1</mn> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle j+1}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/5baf2ec9e436e9309065133555e3cb2ecd88f87e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.027ex; width:4.988ex; height:2.509ex;" alt="{\displaystyle j+1}"></span> in one of the two input heaps. In the course of the algorithm, it will examine at most three trees of any order, two from the two heaps we merge and one composed of two smaller trees.<sup id="cite_ref-clrs_1-9" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-brown_3-5" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <pre><b>function</b> merge(p, q) <b>while</b> <b>not</b> (p.end() <b>and</b> q.end()) tree = mergeTree(p.currentTree(), q.currentTree()) </pre> <pre> <b>if</b> <b>not</b> heap.currentTree().empty() tree = mergeTree(tree, heap.currentTree()) </pre> <pre> heap.addTree(tree) heap.next(); p.next(); q.next() </pre> <p>Because each binomial tree in a binomial heap corresponds to a bit in the binary representation of its size, there is an analogy between the merging of two heaps and the binary addition of the <i>sizes</i> of the two heaps, from right-to-left. Whenever a carry occurs during addition, this corresponds to a merging of two binomial trees during the merge.<sup id="cite_ref-clrs_1-10" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-brown_3-6" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>Each binomial tree's traversal during merge only involves roots, hence making the time taken at most order <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log _{2}n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d74677fc45e0d926639433586327cbc2982eae89" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.808ex; height:2.676ex;" alt="{\displaystyle \log _{2}n}"></span> and therefore the running time is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span>.<sup id="cite_ref-clrs_1-11" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-brown_3-7" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Insert">Insert</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=5" title="Edit section: Insert"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p><b>Inserting</b> a new element to a heap can be done by simply creating a new heap containing only this element and then merging it with the original heap. Because of the merge, a single insertion takes time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span>. However, this can be sped up using a merge procedure that shortcuts the merge after it reaches a point where only one of the merged heaps has trees of larger order. With this speedup, across a series of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle k}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>k</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle k}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/c3c9a2c7b599b37105512c5d570edc034056dd40" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.211ex; height:2.176ex;" alt="{\displaystyle k}"></span> consecutive insertions, the total time for the insertions is <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(k+\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>k</mi> <mo>+</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(k+\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/52ea4d30b861cebb6d7deaf008c82812da9579a5" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.388ex; height:2.843ex;" alt="{\displaystyle O(k+\log n)}"></span>. Another way of stating this is that (after logarithmic overhead for the first insertion in a sequence) each successive <b>insert</b> has an <a href="/wiki/Amortized_time" class="mw-redirect" title="Amortized time"><i>amortized</i> time</a> of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}"></span> (i.e. constant) per insertion.<sup id="cite_ref-clrs_1-12" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-brown_3-8" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p><p>A variant of the binomial heap, the <a href="/wiki/Skew_binomial_heap" title="Skew binomial heap">skew binomial heap</a>, achieves constant worst case insertion time by using forests whose tree sizes are based on the <a href="/wiki/Skew_binary_number_system" title="Skew binary number system">skew binary number system</a> rather than on the binary number system.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Find_minimum">Find minimum</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=6" title="Edit section: Find minimum"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To find the <b>minimum</b> element of the heap, find the minimum among the roots of the binomial trees. This can be done in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span> time, as there are just <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span> tree roots to examine.<sup id="cite_ref-clrs_1-13" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p><p>By using a pointer to the binomial tree that contains the minimum element, the time for this operation can be reduced to <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(1)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mn>1</mn> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(1)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e66384bc40452c5452f33563fe0e27e803b0cc21" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.745ex; height:2.843ex;" alt="{\displaystyle O(1)}"></span>. The pointer must be updated when performing any operation other than finding the minimum. This can be done in <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span> time per update, without raising the overall asymptotic running time of any operation.<sup class="noprint Inline-Template Template-Fact" style="white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Citation_needed" title="Wikipedia:Citation needed"><span title="This claim needs references to reliable sources. (October 2019)">citation needed</span></a></i>]</sup> </p> <div class="mw-heading mw-heading3"><h3 id="Delete_minimum">Delete minimum</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=7" title="Edit section: Delete minimum"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To <b>delete the minimum element</b> from the heap, first find this element, remove it from the root of its binomial tree, and obtain a list of its child subtrees (which are each themselves binomial trees, of distinct orders). Transform this list of subtrees into a separate binomial heap by reordering them from smallest to largest order. Then merge this heap with the original heap. Since each root has at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log _{2}n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d74677fc45e0d926639433586327cbc2982eae89" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.808ex; height:2.676ex;" alt="{\displaystyle \log _{2}n}"></span> children, creating this new heap takes time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span>. Merging heaps takes time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span>, so the entire delete minimum operation takes time <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span>.<sup id="cite_ref-clrs_1-14" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p> <pre><b>function</b> deleteMin(heap) min = heap.trees().first() <b>for each</b> current <b>in</b> heap.trees() <b>if</b> current.root < min.root <b>then</b> min = current <b>for each</b> tree <b>in</b> min.subTrees() tmp.addTree(tree) heap.removeTree(min) merge(heap, tmp) </pre> <div class="mw-heading mw-heading3"><h3 id="Decrease_key">Decrease key</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=8" title="Edit section: Decrease key"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>After <b>decreasing</b> the key of an element, it may become smaller than the key of its parent, violating the minimum-heap property. If this is the case, exchange the element with its parent, and possibly also with its grandparent, and so on, until the minimum-heap property is no longer violated. Each binomial tree has height at most <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \log _{2}n}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <msub> <mi>log</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> <mo>⁡</mo> <mi>n</mi> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \log _{2}n}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/d74677fc45e0d926639433586327cbc2982eae89" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:5.808ex; height:2.676ex;" alt="{\displaystyle \log _{2}n}"></span>, so this takes <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(\log n)}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(\log n)}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/aae0f22048ba6b7c05dbae17b056bfa16e21807d" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.336ex; height:2.843ex;" alt="{\displaystyle O(\log n)}"></span> time.<sup id="cite_ref-clrs_1-15" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> However, this operation requires that the representation of the tree include pointers from each node to its parent in the tree, somewhat complicating the implementation of other operations.<sup id="cite_ref-brown_3-9" class="reference"><a href="#cite_note-brown-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading3"><h3 id="Delete">Delete</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=9" title="Edit section: Delete"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>To <b>delete</b> an element from the heap, decrease its key to negative infinity (or equivalently, to some value lower than any element in the heap) and then delete the minimum in the heap.<sup id="cite_ref-clrs_1-16" class="reference"><a href="#cite_note-clrs-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> </p> <div class="mw-heading mw-heading2"><h2 id="Summary_of_running_times">Summary of running times</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=10" title="Edit section: Summary of running times"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Here are <a href="/wiki/Computational_complexity_theory" title="Computational complexity theory">time complexities</a><sup id="cite_ref-CLRS_5-0" class="reference"><a href="#cite_note-CLRS-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> of various heap data structures. The abbreviation <abbr title="amortized complexity">am.</abbr> indicates that the given complexity is amortized, otherwise it is a worst-case complexity. For the meaning of "<i>O</i>(<i>f</i>)" and "<i>Θ</i>(<i>f</i>)" see <a href="/wiki/Big_O_notation" title="Big O notation">Big O notation</a>. Names of operations assume a min-heap. </p> <table class="wikitable"> <tbody><tr> <th>Operation </th> <th>find-min </th> <th>delete-min </th> <th>decrease-key </th> <th>insert </th> <th>meld </th> <th>make-heap<sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>a<span class="cite-bracket">]</span></a></sup> </th></tr> <tr> <th><a href="/wiki/Binary_heap" title="Binary heap">Binary</a><sup id="cite_ref-CLRS_5-1" class="reference"><a href="#cite_note-CLRS-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ffdddd"><i>Θ</i>(<i>n</i>) </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) </td></tr> <tr> <th><a href="/wiki/Skew_heap" title="Skew heap">Skew</a><sup id="cite_ref-sleator-tarjan-skew_6-1" class="reference"><a href="#cite_note-sleator-tarjan-skew-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) <abbr title="amortized complexity">am.</abbr> </td></tr> <tr> <th><a href="/wiki/Leftist_tree" title="Leftist tree">Leftist</a><sup id="cite_ref-tarjan-leftist_7-1" class="reference"><a href="#cite_note-tarjan-leftist-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) </td></tr> <tr> <th><a class="mw-selflink selflink">Binomial</a><sup id="cite_ref-CLRS_5-2" class="reference"><a href="#cite_note-CLRS-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ddffdd"><i>Θ</i>(1) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>)<sup id="cite_ref-bootstrap-meld_11-0" class="reference"><a href="#cite_note-bootstrap-meld-11"><span class="cite-bracket">[</span>b<span class="cite-bracket">]</span></a></sup> </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) </td></tr> <tr> <th><a href="/wiki/Skew_binomial_heap" title="Skew binomial heap">Skew binomial</a><sup id="cite_ref-brodal-okasaki_12-0" class="reference"><a href="#cite_note-brodal-okasaki-12"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>)<sup id="cite_ref-bootstrap-meld_11-1" class="reference"><a href="#cite_note-bootstrap-meld-11"><span class="cite-bracket">[</span>b<span class="cite-bracket">]</span></a></sup> </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) </td></tr> <tr> <th><a href="/wiki/2%E2%80%933_heap" title="2–3 heap">2–3 heap</a><sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(1) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>)<sup id="cite_ref-bootstrap-meld_11-2" class="reference"><a href="#cite_note-bootstrap-meld-11"><span class="cite-bracket">[</span>b<span class="cite-bracket">]</span></a></sup> </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) </td></tr> <tr> <th><a href="/wiki/Skew_heap" title="Skew heap">Bottom-up skew</a><sup id="cite_ref-sleator-tarjan-skew_6-2" class="reference"><a href="#cite_note-sleator-tarjan-skew-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ddffdd"><i>Θ</i>(1) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ddffdd"><i>Θ</i>(1) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) <abbr title="amortized complexity">am.</abbr> </td></tr> <tr> <th><a href="/wiki/Pairing_heap" title="Pairing heap">Pairing</a><sup id="cite_ref-Iacono_15-0" class="reference"><a href="#cite_note-Iacono-15"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ffffdd"><i>o</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr><sup id="cite_ref-pairingdecreasekey_18-0" class="reference"><a href="#cite_note-pairingdecreasekey-18"><span class="cite-bracket">[</span>c<span class="cite-bracket">]</span></a></sup> </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) </td></tr> <tr> <th><a href="/w/index.php?title=Rank-pairing_heap&action=edit&redlink=1" class="new" title="Rank-pairing heap (page does not exist)">Rank-pairing</a><sup id="cite_ref-19" class="reference"><a href="#cite_note-19"><span class="cite-bracket">[</span>16<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ddffdd"><i>Θ</i>(1) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) </td></tr> <tr> <th><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci</a><sup id="cite_ref-CLRS_5-3" class="reference"><a href="#cite_note-CLRS-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-Fredman_And_Tarjan_20-0" class="reference"><a href="#cite_note-Fredman_And_Tarjan-20"><span class="cite-bracket">[</span>17<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>O</i>(log <i>n</i>) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ddffdd"><i>Θ</i>(1) <abbr title="amortized complexity">am.</abbr> </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) </td></tr> <tr> <th><a href="/wiki/Strict_Fibonacci_heap" title="Strict Fibonacci heap">Strict Fibonacci</a><sup id="cite_ref-21" class="reference"><a href="#cite_note-21"><span class="cite-bracket">[</span>18<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-optimum_22-0" class="reference"><a href="#cite_note-optimum-22"><span class="cite-bracket">[</span>d<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>) </td></tr> <tr> <th><a href="/wiki/Brodal_queue" title="Brodal queue">Brodal</a><sup id="cite_ref-23" class="reference"><a href="#cite_note-23"><span class="cite-bracket">[</span>19<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-optimum_22-1" class="reference"><a href="#cite_note-optimum-22"><span class="cite-bracket">[</span>d<span class="cite-bracket">]</span></a></sup> </th> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ffffdd"><i>Θ</i>(log <i>n</i>) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(1) </td> <td style="background:#ddffdd"><i>Θ</i>(<i>n</i>)<sup id="cite_ref-24" class="reference"><a href="#cite_note-24"><span class="cite-bracket">[</span>20<span class="cite-bracket">]</span></a></sup> </td></tr></tbody></table> <style data-mw-deduplicate="TemplateStyles:r1239543626">.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}</style><div class="reflist reflist-lower-alpha"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><i>make-heap</i> is the operation of building a heap from a sequence of <i>n</i> unsorted elements. It can be done in <i>Θ</i>(<i>n</i>) time whenever <i>meld</i> runs in <i>O</i>(log <i>n</i>) time (where both complexities can be amortized).<sup id="cite_ref-sleator-tarjan-skew_6-0" class="reference"><a href="#cite_note-sleator-tarjan-skew-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-tarjan-leftist_7-0" class="reference"><a href="#cite_note-tarjan-leftist-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Another algorithm achieves <i>Θ</i>(<i>n</i>) for binary heaps.<sup id="cite_ref-hayward-mcdiarmid-heap-build_8-0" class="reference"><a href="#cite_note-hayward-mcdiarmid-heap-build-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup></span> </li> <li id="cite_note-bootstrap-meld-11"><span class="mw-cite-backlink">^ <a href="#cite_ref-bootstrap-meld_11-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-bootstrap-meld_11-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-bootstrap-meld_11-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text">For <a href="/wiki/Persistent_data_structure" title="Persistent data structure">persistent</a> heaps (not supporting <i>decrease-key</i>), a generic transformation reduces the cost of <i>meld</i> to that of <i>insert</i>, while the new cost of <i>delete-min</i> is the sum of the old costs of <i>delete-min</i> and <i>meld</i>.<sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup> Here, it makes <i>meld</i> run in <i>Θ</i>(1) time (amortized, if the cost of <i>insert</i> is) while <i>delete-min</i> still runs in <i>O</i>(log <i>n</i>). Applied to skew binomial heaps, it yields Brodal-Okasaki queues, persistent heaps with optimal worst-case complexities.<sup id="cite_ref-brodal-okasaki_12-1" class="reference"><a href="#cite_note-brodal-okasaki-12"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup></span> </li> <li id="cite_note-pairingdecreasekey-18"><span class="mw-cite-backlink"><b><a href="#cite_ref-pairingdecreasekey_18-0">^</a></b></span> <span class="reference-text">Lower bound of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Omega (\log \log n),}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi mathvariant="normal">Ω</mi> <mo stretchy="false">(</mo> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> <mo stretchy="false">)</mo> <mo>,</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \Omega (\log \log n),}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7caf8c32fbd99eed1338c02b7f7f1255f16ade36" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.247ex; height:2.843ex;" alt="{\displaystyle \Omega (\log \log n),}"></span><sup id="cite_ref-Fredman1999_16-0" class="reference"><a href="#cite_note-Fredman1999-16"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup> upper bound of <span class="mwe-math-element"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>O</mi> <mo stretchy="false">(</mo> <msup> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mi>log</mi> <mo>⁡</mo> <mi>log</mi> <mo>⁡</mo> <mi>n</mi> </msqrt> </mrow> </mrow> </msup> <mo stretchy="false">)</mo> <mo>.</mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/45c772d2ec070e49a6438ea92b1c8dc764613c5e" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.052ex; height:3.509ex;" alt="{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}"></span><sup id="cite_ref-17" class="reference"><a href="#cite_note-17"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup></span> </li> <li id="cite_note-optimum-22"><span class="mw-cite-backlink">^ <a href="#cite_ref-optimum_22-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-optimum_22-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text">Brodal queues and strict Fibonacci heaps achieve optimal worst-case complexities for heaps. They were first described as imperative data structures. The Brodal-Okasaki queue is a <a href="/wiki/Persistent_data_structure" title="Persistent data structure">persistent</a> data structure achieving the same optimum, except that <i>decrease-key</i> is not supported.</span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="Applications">Applications</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=11" title="Edit section: Applications"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Discrete_event_simulation" class="mw-redirect" title="Discrete event simulation">Discrete event simulation</a></li> <li><a href="/wiki/Priority_queue" title="Priority queue">Priority queues</a></li></ul> <div class="mw-heading mw-heading2"><h2 id="See_also">See also</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=12" title="Edit section: See also"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Weak_heap" title="Weak heap">Weak heap</a>, a combination of the binary heap and binomial heap data structures</li></ul> <div class="mw-heading mw-heading2"><h2 id="References">References</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=13" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1239543626"><div class="reflist"> <div class="mw-references-wrap mw-references-columns"><ol class="references"> <li id="cite_note-clrs-1"><span class="mw-cite-backlink">^ <a href="#cite_ref-clrs_1-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-clrs_1-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-clrs_1-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-clrs_1-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-clrs_1-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-clrs_1-5"><sup><i><b>f</b></i></sup></a> <a href="#cite_ref-clrs_1-6"><sup><i><b>g</b></i></sup></a> <a href="#cite_ref-clrs_1-7"><sup><i><b>h</b></i></sup></a> <a href="#cite_ref-clrs_1-8"><sup><i><b>i</b></i></sup></a> <a href="#cite_ref-clrs_1-9"><sup><i><b>j</b></i></sup></a> <a href="#cite_ref-clrs_1-10"><sup><i><b>k</b></i></sup></a> <a href="#cite_ref-clrs_1-11"><sup><i><b>l</b></i></sup></a> <a href="#cite_ref-clrs_1-12"><sup><i><b>m</b></i></sup></a> <a href="#cite_ref-clrs_1-13"><sup><i><b>n</b></i></sup></a> <a href="#cite_ref-clrs_1-14"><sup><i><b>o</b></i></sup></a> <a href="#cite_ref-clrs_1-15"><sup><i><b>p</b></i></sup></a> <a href="#cite_ref-clrs_1-16"><sup><i><b>q</b></i></sup></a></span> <span class="reference-text"><style data-mw-deduplicate="TemplateStyles:r1238218222">.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/6/65/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/d/d6/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/a/aa/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/4/4c/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}</style><cite id="CITEREFCormenLeisersonRivestStein2001" class="citation book cs1"><a href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="/wiki/Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a>; <a href="/wiki/Clifford_Stein" title="Clifford Stein">Stein, Clifford</a> (2001) [1990]. "Chapter 19: Binomial Heaps". <a href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms"><i>Introduction to Algorithms</i></a> (2nd ed.). MIT Press and McGraw-Hill. pp. 455–475. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-262-03293-7" title="Special:BookSources/0-262-03293-7"><bdi>0-262-03293-7</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Chapter+19%3A+Binomial+Heaps&rft.btitle=Introduction+to+Algorithms&rft.pages=455-475&rft.edition=2nd&rft.pub=MIT+Press+and+McGraw-Hill&rft.date=2001&rft.isbn=0-262-03293-7&rft.aulast=Cormen&rft.aufirst=Thomas+H.&rft.au=Leiserson%2C+Charles+E.&rft.au=Rivest%2C+Ronald+L.&rft.au=Stein%2C+Clifford&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFVuillemin1978" class="citation journal cs1">Vuillemin, Jean (1 April 1978). <a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F359460.359478">"A data structure for manipulating priority queues"</a>. <i>Communications of the ACM</i>. <b>21</b> (4): 309–315. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F359460.359478">10.1145/359460.359478</a></span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Communications+of+the+ACM&rft.atitle=A+data+structure+for+manipulating+priority+queues&rft.volume=21&rft.issue=4&rft.pages=309-315&rft.date=1978-04-01&rft_id=info%3Adoi%2F10.1145%2F359460.359478&rft.aulast=Vuillemin&rft.aufirst=Jean&rft_id=https%3A%2F%2Fdoi.org%2F10.1145%252F359460.359478&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-brown-3"><span class="mw-cite-backlink">^ <a href="#cite_ref-brown_3-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-brown_3-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-brown_3-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-brown_3-3"><sup><i><b>d</b></i></sup></a> <a href="#cite_ref-brown_3-4"><sup><i><b>e</b></i></sup></a> <a href="#cite_ref-brown_3-5"><sup><i><b>f</b></i></sup></a> <a href="#cite_ref-brown_3-6"><sup><i><b>g</b></i></sup></a> <a href="#cite_ref-brown_3-7"><sup><i><b>h</b></i></sup></a> <a href="#cite_ref-brown_3-8"><sup><i><b>i</b></i></sup></a> <a href="#cite_ref-brown_3-9"><sup><i><b>j</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrown1978" class="citation journal cs1">Brown, Mark R. (1978). "Implementation and analysis of binomial queue algorithms". <i>SIAM Journal on Computing</i>. <b>7</b> (3): 298–319. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0207026">10.1137/0207026</a>. <a href="/wiki/MR_(identifier)" class="mw-redirect" title="MR (identifier)">MR</a> <a rel="nofollow" class="external text" href="https://mathscinet.ams.org/mathscinet-getitem?mr=0483830">0483830</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Implementation+and+analysis+of+binomial+queue+algorithms&rft.volume=7&rft.issue=3&rft.pages=298-319&rft.date=1978&rft_id=info%3Adoi%2F10.1137%2F0207026&rft_id=https%3A%2F%2Fmathscinet.ams.org%2Fmathscinet-getitem%3Fmr%3D483830%23id-name%3DMR&rft.aulast=Brown&rft.aufirst=Mark+R.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrodalOkasaki1996" class="citation cs2">Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", <i>Journal of Functional Programming</i>, <b>6</b> (6): 839–857, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1017%2Fs095679680000201x">10.1017/s095679680000201x</a></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Functional+Programming&rft.atitle=Optimal+purely+functional+priority+queues&rft.volume=6&rft.issue=6&rft.pages=839-857&rft.date=1996-11&rft_id=info%3Adoi%2F10.1017%2Fs095679680000201x&rft.aulast=Brodal&rft.aufirst=Gerth+St%C3%B8lting&rft.au=Okasaki%2C+Chris&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-CLRS-5"><span class="mw-cite-backlink">^ <a href="#cite_ref-CLRS_5-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-CLRS_5-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-CLRS_5-2"><sup><i><b>c</b></i></sup></a> <a href="#cite_ref-CLRS_5-3"><sup><i><b>d</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFCormenLeisersonRivest1990" class="citation book cs1"><a href="/wiki/Thomas_H._Cormen" title="Thomas H. Cormen">Cormen, Thomas H.</a>; <a href="/wiki/Charles_E._Leiserson" title="Charles E. Leiserson">Leiserson, Charles E.</a>; <a href="/wiki/Ron_Rivest" title="Ron Rivest">Rivest, Ronald L.</a> (1990). <a href="/wiki/Introduction_to_Algorithms" title="Introduction to Algorithms"><i>Introduction to Algorithms</i></a> (1st ed.). MIT Press and McGraw-Hill. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-262-03141-8" title="Special:BookSources/0-262-03141-8"><bdi>0-262-03141-8</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Introduction+to+Algorithms&rft.edition=1st&rft.pub=MIT+Press+and+McGraw-Hill&rft.date=1990&rft.isbn=0-262-03141-8&rft.aulast=Cormen&rft.aufirst=Thomas+H.&rft.au=Leiserson%2C+Charles+E.&rft.au=Rivest%2C+Ronald+L.&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-sleator-tarjan-skew-6"><span class="mw-cite-backlink">^ <a href="#cite_ref-sleator-tarjan-skew_6-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-sleator-tarjan-skew_6-1"><sup><i><b>b</b></i></sup></a> <a href="#cite_ref-sleator-tarjan-skew_6-2"><sup><i><b>c</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFSleatorTarjan1986" class="citation journal cs1"><a href="/wiki/Daniel_Sleator" title="Daniel Sleator">Sleator, Daniel Dominic</a>; <a href="/wiki/Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert Endre</a> (February 1986). <a rel="nofollow" class="external text" href="https://www.cs.cmu.edu/~sleator/papers/Adjusting-Heaps.htm">"Self-Adjusting Heaps"</a>. <i><a href="/wiki/SIAM_Journal_on_Computing" title="SIAM Journal on Computing">SIAM Journal on Computing</a></i>. <b>15</b> (1): 52–69. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.93.6678">10.1.1.93.6678</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F0215004">10.1137/0215004</a>. <a href="/wiki/ISSN_(identifier)" class="mw-redirect" title="ISSN (identifier)">ISSN</a> <a rel="nofollow" class="external text" href="https://search.worldcat.org/issn/0097-5397">0097-5397</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+Journal+on+Computing&rft.atitle=Self-Adjusting+Heaps&rft.volume=15&rft.issue=1&rft.pages=52-69&rft.date=1986-02&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.93.6678%23id-name%3DCiteSeerX&rft.issn=0097-5397&rft_id=info%3Adoi%2F10.1137%2F0215004&rft.aulast=Sleator&rft.aufirst=Daniel+Dominic&rft.au=Tarjan%2C+Robert+Endre&rft_id=https%3A%2F%2Fwww.cs.cmu.edu%2F~sleator%2Fpapers%2FAdjusting-Heaps.htm&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-tarjan-leftist-7"><span class="mw-cite-backlink">^ <a href="#cite_ref-tarjan-leftist_7-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-tarjan-leftist_7-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTarjan1983" class="citation book cs1"><a href="/wiki/Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert</a> (1983). "3.3. Leftist heaps". <i>Data Structures and Network Algorithms</i>. pp. 38–42. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F1.9781611970265">10.1137/1.9781611970265</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-0-89871-187-5" title="Special:BookSources/978-0-89871-187-5"><bdi>978-0-89871-187-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=3.3.+Leftist+heaps&rft.btitle=Data+Structures+and+Network+Algorithms&rft.pages=38-42&rft.date=1983&rft_id=info%3Adoi%2F10.1137%2F1.9781611970265&rft.isbn=978-0-89871-187-5&rft.aulast=Tarjan&rft.aufirst=Robert&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-hayward-mcdiarmid-heap-build-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-hayward-mcdiarmid-heap-build_8-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHaywardMcDiarmid1991" class="citation journal cs1">Hayward, Ryan; McDiarmid, Colin (1991). <a rel="nofollow" class="external text" href="https://web.archive.org/web/20160205023201/http://www.stats.ox.ac.uk/__data/assets/pdf_file/0015/4173/heapbuildjalg.pdf">"Average Case Analysis of Heap Building by Repeated Insertion"</a> <span class="cs1-format">(PDF)</span>. <i>J. Algorithms</i>. <b>12</b>: 126–153. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.353.7888">10.1.1.353.7888</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2F0196-6774%2891%2990027-v">10.1016/0196-6774(91)90027-v</a>. Archived from <a rel="nofollow" class="external text" href="http://www.stats.ox.ac.uk/__data/assets/pdf_file/0015/4173/heapbuildjalg.pdf">the original</a> <span class="cs1-format">(PDF)</span> on 5 February 2016<span class="reference-accessdate">. Retrieved <span class="nowrap">28 January</span> 2016</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=J.+Algorithms&rft.atitle=Average+Case+Analysis+of+Heap+Building+by+Repeated+Insertion&rft.volume=12&rft.pages=126-153&rft.date=1991&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.353.7888%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1016%2F0196-6774%2891%2990027-v&rft.aulast=Hayward&rft.aufirst=Ryan&rft.au=McDiarmid%2C+Colin&rft_id=http%3A%2F%2Fwww.stats.ox.ac.uk%2F__data%2Fassets%2Fpdf_file%2F0015%2F4173%2Fheapbuildjalg.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://brilliant.org/wiki/binomial-heap/">"Binomial Heap | Brilliant Math & Science Wiki"</a>. <i>brilliant.org</i><span class="reference-accessdate">. Retrieved <span class="nowrap">30 September</span> 2019</span>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=unknown&rft.jtitle=brilliant.org&rft.atitle=Binomial+Heap+%7C+Brilliant+Math+%26+Science+Wiki&rft_id=https%3A%2F%2Fbrilliant.org%2Fwiki%2Fbinomial-heap%2F&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-brodal-okasaki-12"><span class="mw-cite-backlink">^ <a href="#cite_ref-brodal-okasaki_12-0"><sup><i><b>a</b></i></sup></a> <a href="#cite_ref-brodal-okasaki_12-1"><sup><i><b>b</b></i></sup></a></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrodalOkasaki1996" class="citation cs2">Brodal, Gerth Stølting; Okasaki, Chris (November 1996), "Optimal purely functional priority queues", <i>Journal of Functional Programming</i>, <b>6</b> (6): 839–857, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://doi.org/10.1017%2Fs095679680000201x">10.1017/s095679680000201x</a></span></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+Functional+Programming&rft.atitle=Optimal+purely+functional+priority+queues&rft.volume=6&rft.issue=6&rft.pages=839-857&rft.date=1996-11&rft_id=info%3Adoi%2F10.1017%2Fs095679680000201x&rft.aulast=Brodal&rft.aufirst=Gerth+St%C3%B8lting&rft.au=Okasaki%2C+Chris&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFOkasaki1998" class="citation book cs1"><a href="/wiki/Chris_Okasaki" title="Chris Okasaki">Okasaki, Chris</a> (1998). "10.2. Structural Abstraction". <i>Purely Functional Data Structures</i> (1st ed.). pp. 158–162. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/9780521631242" title="Special:BookSources/9780521631242"><bdi>9780521631242</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=10.2.+Structural+Abstraction&rft.btitle=Purely+Functional+Data+Structures&rft.pages=158-162&rft.edition=1st&rft.date=1998&rft.isbn=9780521631242&rft.aulast=Okasaki&rft.aufirst=Chris&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFTakaoka1999" class="citation cs2"><a href="/w/index.php?title=Tadao_Takaoka&action=edit&redlink=1" class="new" title="Tadao Takaoka (page does not exist)">Takaoka, Tadao</a> (1999), <a rel="nofollow" class="external text" href="https://ir.canterbury.ac.nz/bitstream/handle/10092/14769/2-3heaps.pdf"><i>Theory of 2–3 Heaps</i></a> <span class="cs1-format">(PDF)</span>, p. 12</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=book&rft.btitle=Theory+of+2%E2%80%933+Heaps&rft.pages=12&rft.date=1999&rft.aulast=Takaoka&rft.aufirst=Tadao&rft_id=https%3A%2F%2Fir.canterbury.ac.nz%2Fbitstream%2Fhandle%2F10092%2F14769%2F2-3heaps.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-Iacono-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-Iacono_15-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFIacono2000" class="citation cs2"><a href="/wiki/John_Iacono" title="John Iacono">Iacono, John</a> (2000), "Improved upper bounds for pairing heaps", <a rel="nofollow" class="external text" href="http://john2.poly.edu/papers/swat00/paper.pdf"><i>Proc. 7th Scandinavian Workshop on Algorithm Theory</i></a> <span class="cs1-format">(PDF)</span>, Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, <a href="/wiki/ArXiv_(identifier)" class="mw-redirect" title="ArXiv (identifier)">arXiv</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://arxiv.org/abs/1110.4428">1110.4428</a></span>, <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.748.7812">10.1.1.748.7812</a></span>, <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F3-540-44985-X_5">10.1007/3-540-44985-X_5</a>, <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/3-540-67690-2" title="Special:BookSources/3-540-67690-2"><bdi>3-540-67690-2</bdi></a></cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Improved+upper+bounds+for+pairing+heaps&rft.btitle=Proc.+7th+Scandinavian+Workshop+on+Algorithm+Theory&rft.series=Lecture+Notes+in+Computer+Science&rft.pages=63-77&rft.pub=Springer-Verlag&rft.date=2000&rft_id=info%3Aarxiv%2F1110.4428&rft_id=info%3Adoi%2F10.1007%2F3-540-44985-X_5&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.748.7812%23id-name%3DCiteSeerX&rft.isbn=3-540-67690-2&rft.aulast=Iacono&rft.aufirst=John&rft_id=http%3A%2F%2Fjohn2.poly.edu%2Fpapers%2Fswat00%2Fpaper.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-Fredman1999-16"><span class="mw-cite-backlink"><b><a href="#cite_ref-Fredman1999_16-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFredman1999" class="citation journal cs1"><a href="/wiki/Michael_Fredman" title="Michael Fredman">Fredman, Michael Lawrence</a> (July 1999). <a rel="nofollow" class="external text" href="http://www.uqac.ca/azinflou/Fichiers840/EfficiencyPairingHeap.pdf">"On the Efficiency of Pairing Heaps and Related Data Structures"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/Journal_of_the_Association_for_Computing_Machinery" class="mw-redirect" title="Journal of the Association for Computing Machinery">Journal of the Association for Computing Machinery</a></i>. <b>46</b> (4): 473–501. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F320211.320214">10.1145/320211.320214</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+Association+for+Computing+Machinery&rft.atitle=On+the+Efficiency+of+Pairing+Heaps+and+Related+Data+Structures&rft.volume=46&rft.issue=4&rft.pages=473-501&rft.date=1999-07&rft_id=info%3Adoi%2F10.1145%2F320211.320214&rft.aulast=Fredman&rft.aufirst=Michael+Lawrence&rft_id=http%3A%2F%2Fwww.uqac.ca%2Fazinflou%2FFichiers840%2FEfficiencyPairingHeap.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-17"><span class="mw-cite-backlink"><b><a href="#cite_ref-17">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFPettie2005" class="citation conference cs1">Pettie, Seth (2005). <a rel="nofollow" class="external text" href="http://web.eecs.umich.edu/~pettie/papers/focs05.pdf"><i>Towards a Final Analysis of Pairing Heaps</i></a> <span class="cs1-format">(PDF)</span>. FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.549.471">10.1.1.549.471</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1109%2FSFCS.2005.75">10.1109/SFCS.2005.75</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-7695-2468-0" title="Special:BookSources/0-7695-2468-0"><bdi>0-7695-2468-0</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=Towards+a+Final+Analysis+of+Pairing+Heaps&rft.pages=174-183&rft.date=2005&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.549.471%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1109%2FSFCS.2005.75&rft.isbn=0-7695-2468-0&rft.aulast=Pettie&rft.aufirst=Seth&rft_id=http%3A%2F%2Fweb.eecs.umich.edu%2F~pettie%2Fpapers%2Ffocs05.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-19"><span class="mw-cite-backlink"><b><a href="#cite_ref-19">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFHaeuplerSenTarjan2011" class="citation journal cs1">Haeupler, Bernhard; Sen, Siddhartha; <a href="/wiki/Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (November 2011). <a rel="nofollow" class="external text" href="http://sidsen.org/papers/rp-heaps-journal.pdf">"Rank-pairing heaps"</a> <span class="cs1-format">(PDF)</span>. <i>SIAM J. Computing</i>. <b>40</b> (6): 1463–1485. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2F100785351">10.1137/100785351</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=SIAM+J.+Computing&rft.atitle=Rank-pairing+heaps&rft.volume=40&rft.issue=6&rft.pages=1463-1485&rft.date=2011-11&rft_id=info%3Adoi%2F10.1137%2F100785351&rft.aulast=Haeupler&rft.aufirst=Bernhard&rft.au=Sen%2C+Siddhartha&rft.au=Tarjan%2C+Robert+E.&rft_id=http%3A%2F%2Fsidsen.org%2Fpapers%2Frp-heaps-journal.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-Fredman_And_Tarjan-20"><span class="mw-cite-backlink"><b><a href="#cite_ref-Fredman_And_Tarjan_20-0">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFFredmanTarjan1987" class="citation journal cs1"><a href="/wiki/Michael_Fredman" title="Michael Fredman">Fredman, Michael Lawrence</a>; <a href="/wiki/Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (July 1987). <a rel="nofollow" class="external text" href="http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Fibonacci-Heap-Tarjan.pdf">"Fibonacci heaps and their uses in improved network optimization algorithms"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/Journal_of_the_Association_for_Computing_Machinery" class="mw-redirect" title="Journal of the Association for Computing Machinery">Journal of the Association for Computing Machinery</a></i>. <b>34</b> (3): 596–615. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.309.8927">10.1.1.309.8927</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F28869.28874">10.1145/28869.28874</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Journal+of+the+Association+for+Computing+Machinery&rft.atitle=Fibonacci+heaps+and+their+uses+in+improved+network+optimization+algorithms&rft.volume=34&rft.issue=3&rft.pages=596-615&rft.date=1987-07&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.309.8927%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1145%2F28869.28874&rft.aulast=Fredman&rft.aufirst=Michael+Lawrence&rft.au=Tarjan%2C+Robert+E.&rft_id=http%3A%2F%2Fbioinfo.ict.ac.cn%2F~dbu%2FAlgorithmCourses%2FLectures%2FFibonacci-Heap-Tarjan.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-21"><span class="mw-cite-backlink"><b><a href="#cite_ref-21">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrodalLagogiannisTarjan2012" class="citation conference cs1"><a href="/wiki/Gerth_St%C3%B8lting_Brodal" class="mw-redirect" title="Gerth Stølting Brodal">Brodal, Gerth Stølting</a>; Lagogiannis, George; <a href="/wiki/Robert_Tarjan" title="Robert Tarjan">Tarjan, Robert E.</a> (2012). <a rel="nofollow" class="external text" href="http://www.cs.au.dk/~gerth/papers/stoc12.pdf"><i>Strict Fibonacci heaps</i></a> <span class="cs1-format">(PDF)</span>. Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. <a href="/wiki/CiteSeerX_(identifier)" class="mw-redirect" title="CiteSeerX (identifier)">CiteSeerX</a> <span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.233.1740">10.1.1.233.1740</a></span>. <a href="/wiki/Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1145%2F2213977.2214082">10.1145/2213977.2214082</a>. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/978-1-4503-1245-5" title="Special:BookSources/978-1-4503-1245-5"><bdi>978-1-4503-1245-5</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=conference&rft.btitle=Strict+Fibonacci+heaps&rft.pages=1177-1184&rft.date=2012&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.233.1740%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1145%2F2213977.2214082&rft.isbn=978-1-4503-1245-5&rft.aulast=Brodal&rft.aufirst=Gerth+St%C3%B8lting&rft.au=Lagogiannis%2C+George&rft.au=Tarjan%2C+Robert+E.&rft_id=http%3A%2F%2Fwww.cs.au.dk%2F~gerth%2Fpapers%2Fstoc12.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-23"><span class="mw-cite-backlink"><b><a href="#cite_ref-23">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFBrodal1996" class="citation cs2"><a href="/wiki/Gerth_St%C3%B8lting_Brodal" class="mw-redirect" title="Gerth Stølting Brodal">Brodal, Gerth S.</a> (1996), <a rel="nofollow" class="external text" href="http://www.cs.au.dk/~gerth/papers/soda96.pdf">"Worst-Case Efficient Priority Queues"</a> <span class="cs1-format">(PDF)</span>, <i>Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms</i>, pp. 52–58</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=Worst-Case+Efficient+Priority+Queues&rft.btitle=Proc.+7th+Annual+ACM-SIAM+Symposium+on+Discrete+Algorithms&rft.pages=52-58&rft.date=1996&rft.aulast=Brodal&rft.aufirst=Gerth+S.&rft_id=http%3A%2F%2Fwww.cs.au.dk%2F~gerth%2Fpapers%2Fsoda96.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> <li id="cite_note-24"><span class="mw-cite-backlink"><b><a href="#cite_ref-24">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222"><cite id="CITEREFGoodrichTamassia2004" class="citation book cs1"><a href="/wiki/Michael_T._Goodrich" title="Michael T. Goodrich">Goodrich, Michael T.</a>; <a href="/wiki/Roberto_Tamassia" title="Roberto Tamassia">Tamassia, Roberto</a> (2004). "7.3.6. Bottom-Up Heap Construction". <i>Data Structures and Algorithms in Java</i> (3rd ed.). pp. 338–341. <a href="/wiki/ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <a href="/wiki/Special:BookSources/0-471-46983-1" title="Special:BookSources/0-471-46983-1"><bdi>0-471-46983-1</bdi></a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rft.genre=bookitem&rft.atitle=7.3.6.+Bottom-Up+Heap+Construction&rft.btitle=Data+Structures+and+Algorithms+in+Java&rft.pages=338-341&rft.edition=3rd&rft.date=2004&rft.isbn=0-471-46983-1&rft.aulast=Goodrich&rft.aufirst=Michael+T.&rft.au=Tamassia%2C+Roberto&rfr_id=info%3Asid%2Fen.wikipedia.org%3ABinomial+heap" class="Z3988"></span></span> </li> </ol></div></div> <div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Binomial_heap&action=edit&section=14" title="Edit section: External links"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://www.cs.unc.edu/~bbb/#binomial_heaps">Two C implementations of binomial heap</a> (a generic one and one optimized for integer keys)</li> <li><a rel="nofollow" class="external text" href="http://hackage.haskell.org/packages/archive/TreeStructures/latest/doc/html/src/Data-Heap-Binomial.html">Haskell implementation of binomial heap</a></li> <li><a rel="nofollow" class="external text" href="https://github.com/vy/binomial-heap">Common Lisp implementation of binomial heap</a></li></ul> <div class="navbox-styles"><style data-mw-deduplicate="TemplateStyles:r1129693374">.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}</style><style data-mw-deduplicate="TemplateStyles:r1236075235">.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}</style></div><div role="navigation" class="navbox" aria-labelledby="Data_structures" style="padding:3px"><table class="nowraplinks hlist mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1129693374"><style data-mw-deduplicate="TemplateStyles:r1239400231">.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}</style><div class="navbar plainlinks hlist navbar-mini"><ul><li class="nv-view"><a href="/wiki/Template:Data_structures" title="Template:Data structures"><abbr title="View this template">v</abbr></a></li><li class="nv-talk"><a href="/wiki/Template_talk:Data_structures" title="Template talk:Data structures"><abbr title="Discuss this template">t</abbr></a></li><li class="nv-edit"><a href="/wiki/Special:EditPage/Template:Data_structures" title="Special:EditPage/Template:Data structures"><abbr title="Edit this template">e</abbr></a></li></ul></div><div id="Data_structures" style="font-size:114%;margin:0 4em"><a href="/wiki/Data_structure" title="Data structure">Data structures</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Types</th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Collection_(abstract_data_type)" title="Collection (abstract data type)">Collection</a></li> <li><a href="/wiki/Container_(abstract_data_type)" title="Container (abstract data type)">Container</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Abstract_data_type" title="Abstract data type">Abstract</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Associative_array" title="Associative array">Associative array</a> <ul><li><a href="/wiki/Multimap" title="Multimap">Multimap</a></li> <li><a href="/wiki/Retrieval_Data_Structure" title="Retrieval Data Structure">Retrieval Data Structure</a></li></ul></li> <li><a href="/wiki/List_(abstract_data_type)" title="List (abstract data type)">List</a></li> <li><a href="/wiki/Stack_(abstract_data_type)" title="Stack (abstract data type)">Stack</a></li> <li><a href="/wiki/Queue_(abstract_data_type)" title="Queue (abstract data type)">Queue</a> <ul><li><a href="/wiki/Double-ended_queue" title="Double-ended queue">Double-ended queue</a></li></ul></li> <li><a href="/wiki/Priority_queue" title="Priority queue">Priority queue</a> <ul><li><a href="/wiki/Double-ended_priority_queue" title="Double-ended priority queue">Double-ended priority queue</a></li></ul></li> <li><a href="/wiki/Set_(abstract_data_type)" title="Set (abstract data type)">Set</a> <ul><li><a href="/wiki/Set_(abstract_data_type)#Multiset" title="Set (abstract data type)">Multiset</a></li> <li><a href="/wiki/Disjoint-set_data_structure" title="Disjoint-set data structure">Disjoint-set</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Array_(data_structure)" title="Array (data structure)">Arrays</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Bit_array" title="Bit array">Bit array</a></li> <li><a href="/wiki/Circular_buffer" title="Circular buffer">Circular buffer</a></li> <li><a href="/wiki/Dynamic_array" title="Dynamic array">Dynamic array</a></li> <li><a href="/wiki/Hash_table" title="Hash table">Hash table</a></li> <li><a href="/wiki/Hashed_array_tree" title="Hashed array tree">Hashed array tree</a></li> <li><a href="/wiki/Sparse_matrix" title="Sparse matrix">Sparse matrix</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Linked_data_structure" title="Linked data structure">Linked</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Association_list" title="Association list">Association list</a></li> <li><a href="/wiki/Linked_list" title="Linked list">Linked list</a></li> <li><a href="/wiki/Skip_list" title="Skip list">Skip list</a></li> <li><a href="/wiki/Unrolled_linked_list" title="Unrolled linked list">Unrolled linked list</a></li> <li><a href="/wiki/XOR_linked_list" title="XOR linked list">XOR linked list</a></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Tree_(data_structure)" class="mw-redirect" title="Tree (data structure)">Trees</a></th><td class="navbox-list-with-group navbox-list navbox-odd" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/B-tree" title="B-tree">B-tree</a></li> <li><a href="/wiki/Binary_search_tree" title="Binary search tree">Binary search tree</a> <ul><li><a href="/wiki/AA_tree" title="AA tree">AA tree</a></li> <li><a href="/wiki/AVL_tree" title="AVL tree">AVL tree</a></li> <li><a href="/wiki/Red%E2%80%93black_tree" title="Red–black tree">Red–black tree</a></li> <li><a href="/wiki/Self-balancing_binary_search_tree" title="Self-balancing binary search tree">Self-balancing tree</a></li> <li><a href="/wiki/Splay_tree" title="Splay tree">Splay tree</a></li></ul></li> <li><a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">Heap</a> <ul><li><a href="/wiki/Binary_heap" title="Binary heap">Binary heap</a></li> <li><a class="mw-selflink selflink">Binomial heap</a></li> <li><a href="/wiki/Fibonacci_heap" title="Fibonacci heap">Fibonacci heap</a></li></ul></li> <li><a href="/wiki/R-tree" title="R-tree">R-tree</a> <ul><li><a href="/wiki/R*_tree" class="mw-redirect" title="R* tree">R* tree</a></li> <li><a href="/wiki/R%2B_tree" title="R+ tree">R+ tree</a></li> <li><a href="/wiki/Hilbert_R-tree" title="Hilbert R-tree">Hilbert R-tree</a></li></ul></li> <li><a href="/wiki/Trie" title="Trie">Trie</a> <ul><li><a href="/wiki/Hash_tree_(persistent_data_structure)" title="Hash tree (persistent data structure)">Hash tree</a></li></ul></li></ul> </div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="/wiki/Graph_(abstract_data_type)" title="Graph (abstract data type)">Graphs</a></th><td class="navbox-list-with-group navbox-list navbox-even" style="width:100%;padding:0"><div style="padding:0 0.25em"> <ul><li><a href="/wiki/Binary_decision_diagram" title="Binary decision diagram">Binary decision diagram</a></li> <li><a href="/wiki/Directed_acyclic_graph" title="Directed acyclic graph">Directed acyclic graph</a></li> <li><a href="/wiki/Deterministic_acyclic_finite_state_automaton" title="Deterministic acyclic finite state automaton">Directed acyclic word graph</a></li></ul> </div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div> <ul><li><a href="/wiki/List_of_data_structures" title="List of data structures">List of data structures</a></li></ul> </div></td></tr></tbody></table></div>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?type=1x1&useformat=desktop" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Retrieved from "<a dir="ltr" href="https://en.wikipedia.org/w/index.php?title=Binomial_heap&oldid=1221086681">https://en.wikipedia.org/w/index.php?title=Binomial_heap&oldid=1221086681</a>"</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Help:Category" title="Help:Category">Category</a>: <ul><li><a href="/wiki/Category:Heaps_(data_structures)" title="Category:Heaps (data structures)">Heaps (data structures)</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Hidden categories: <ul><li><a href="/wiki/Category:Articles_with_short_description" title="Category:Articles with short description">Articles with short description</a></li><li><a href="/wiki/Category:Short_description_is_different_from_Wikidata" title="Category:Short description is different from Wikidata">Short description is different from Wikidata</a></li><li><a href="/wiki/Category:Use_dmy_dates_from_May_2018" title="Category:Use dmy dates from May 2018">Use dmy dates from May 2018</a></li><li><a href="/wiki/Category:All_articles_with_unsourced_statements" title="Category:All articles with unsourced statements">All articles with unsourced statements</a></li><li><a href="/wiki/Category:Articles_with_unsourced_statements_from_October_2019" title="Category:Articles with unsourced statements from October 2019">Articles with unsourced statements from October 2019</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> This page was last edited on 27 April 2024, at 20:02<span class="anonymous-show"> (UTC)</span>.</li> <li id="footer-info-copyright">Text is available under the <a href="/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License" title="Wikipedia:Text of the Creative Commons Attribution-ShareAlike 4.0 International License">Creative Commons Attribution-ShareAlike 4.0 License</a>; additional terms may apply. By using this site, you agree to the <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use" class="extiw" title="foundation:Special:MyLanguage/Policy:Terms of Use">Terms of Use</a> and <a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy" class="extiw" title="foundation:Special:MyLanguage/Policy:Privacy policy">Privacy Policy</a>. Wikipedia® is a registered trademark of the <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, a non-profit organization.</li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy">Privacy policy</a></li> <li id="footer-places-about"><a href="/wiki/Wikipedia:About">About Wikipedia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikipedia:General_disclaimer">Disclaimers</a></li> <li id="footer-places-contact"><a href="//en.wikipedia.org/wiki/Wikipedia:Contact_us">Contact Wikipedia</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code of Conduct</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Developers</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/en.wikipedia.org">Statistics</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Cookie statement</a></li> <li id="footer-places-mobileview"><a href="//en.m.wikipedia.org/w/index.php?title=Binomial_heap&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Mobile view</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-67847f4bfd-pwtdw","wgBackendResponseTime":129,"wgPageParseReport":{"limitreport":{"cputime":"0.469","walltime":"0.727","ppvisitednodes":{"value":3158,"limit":1000000},"postexpandincludesize":{"value":75642,"limit":2097152},"templateargumentsize":{"value":3822,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":5,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":99656,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 488.675 1 -total"," 39.71% 194.057 2 Template:Reflist"," 18.39% 89.848 5 Template:Cite_book"," 16.49% 80.598 2 Template:Introduction_to_Algorithms"," 15.75% 76.970 1 Template:Data_structures"," 15.30% 74.772 1 Template:Navbox"," 14.12% 69.021 1 Template:Short_description"," 9.97% 48.723 1 Template:Heap_Running_Times"," 7.58% 37.057 2 Template:Pagetype"," 7.27% 35.546 7 Template:Cite_journal"]},"scribunto":{"limitreport-timeusage":{"value":"0.257","limit":"10.000"},"limitreport-memusage":{"value":6007419,"limit":52428800}},"cachereport":{"origin":"mw-web.eqiad.main-7678f45bf4-8rzm4","timestamp":"20241203070004","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Binomial heap","url":"https:\/\/en.wikipedia.org\/wiki\/Binomial_heap","sameAs":"http:\/\/www.wikidata.org\/entity\/Q864032","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q864032","author":{"@type":"Organization","name":"Contributors to Wikimedia projects"},"publisher":{"@type":"Organization","name":"Wikimedia Foundation, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2003-06-28T00:19:07Z","dateModified":"2024-04-27T20:02:46Z","headline":"priority queue made from heap-ordered trees with power-of-two sizes"}</script> </body> </html>