CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-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-sticky-header-enabled vector-toc-available" lang="en" dir="ltr"> <head> <meta charset="UTF-8"> <title>Skew 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-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-sticky-header-enabled 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":"622c29a7-3c3e-4fa1-b385-4b5c6c11898b","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Skew_heap","wgTitle":"Skew heap","wgCurRevisionId":1226233567,"wgRevisionId":1226233567,"wgArticleId":3707999,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Articles with short description","Short description is different from Wikidata","All articles with unsourced statements","Articles with unsourced statements from September 2020","Wikipedia articles needing clarification from July 2023","Binary trees","Heaps (data structures)"],"wgPageViewLanguage":"en","wgPageContentLanguage":"en","wgPageContentModel":"wikitext","wgRelevantPageName":"Skew_heap","wgRelevantArticleId":3707999,"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":7000,"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q4893208","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":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","ext.pygments":"ready","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready"};RLPAGEMODULES=["ext.cite.ux-enhancements","ext.pygments.view","site","mediawiki.page.ready","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"];</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.pygments%7Cext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediamessages.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.21"> <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="Skew 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/Skew_heap"> <link rel="alternate" type="application/x-wiki" title="Edit this page" href="/w/index.php?title=Skew_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/Skew_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-Skew_heap rootpage-Skew_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" title="Main menu" > <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><li id="n-specialpages" class="mw-list-item"><a href="/wiki/Special:SpecialPages"><span>Special pages</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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=Skew+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=Skew+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/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=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=Skew+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=Skew+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-Definition" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Definition"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Definition</span> </div> </a> <ul id="toc-Definition-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Operations" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Operations"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Operations</span> </div> </a> <button aria-controls="toc-Operations-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 Operations subsection</span> </button> <ul id="toc-Operations-sublist" class="vector-toc-list"> <li id="toc-Merging_two_heaps" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Merging_two_heaps"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.1</span> <span>Merging two heaps</span> </div> </a> <ul id="toc-Merging_two_heaps-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Non-recursive_merging" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Non-recursive_merging"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.2</span> <span>Non-recursive merging</span> </div> </a> <ul id="toc-Non-recursive_merging-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Adding_values" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Adding_values"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.3</span> <span>Adding values</span> </div> </a> <ul id="toc-Adding_values-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Removing_values" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Removing_values"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.4</span> <span>Removing values</span> </div> </a> <ul id="toc-Removing_values-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Implementation" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Implementation"> <div class="vector-toc-text"> <span class="vector-toc-numb">2.5</span> <span>Implementation</span> </div> </a> <ul id="toc-Implementation-sublist" class="vector-toc-list"> </ul> </li> </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">3</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">4</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" title="Table of Contents" > <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">Skew 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 5 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-5" 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">5 languages</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Skew_Heap" title="Skew Heap – German" lang="de" hreflang="de" data-title="Skew Heap" data-language-autonym="Deutsch" data-language-local-name="German" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D9%87%D8%B1%D9%85_%D9%85%D9%88%D8%B1%D8%A8" 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-sr mw-list-item"><a href="https://sr.wikipedia.org/wiki/Skew_%D1%85%D0%B8%D0%BF" title="Skew хип – Serbian" lang="sr" hreflang="sr" data-title="Skew хип" data-language-autonym="Српски / srpski" data-language-local-name="Serbian" class="interlanguage-link-target"><span>Српски / srpski</span></a></li><li class="interlanguage-link interwiki-th mw-list-item"><a href="https://th.wikipedia.org/wiki/%E0%B8%AE%E0%B8%B5%E0%B8%9B%E0%B8%AA%E0%B8%84%E0%B8%B4%E0%B8%A7" title="ฮีปสคิว – Thai" lang="th" hreflang="th" data-title="ฮีปสคิว" data-language-autonym="ไทย" data-language-local-name="Thai" class="interlanguage-link-target"><span>ไทย</span></a></li><li class="interlanguage-link interwiki-zh mw-list-item"><a href="https://zh.wikipedia.org/wiki/%E6%96%9C%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/Q4893208#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/Skew_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:Skew_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/Skew_heap"><span>Read</span></a></li><li id="ca-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Skew_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=Skew_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/Skew_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=Skew_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=Skew_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/Skew_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/Skew_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="//en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard" title="Upload files [u]" accesskey="u"><span>Upload file</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Skew_heap&oldid=1226233567" 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=Skew_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=Skew_heap&id=1226233567&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%2FSkew_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%2FSkew_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=Skew_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=Skew_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 id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q4893208" 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">Binary tree heap data structure</div> <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">Not to be confused with <a href="/wiki/Skew_binomial_heap" title="Skew binomial heap">Skew binomial heap</a>.</div> <p>A <b>skew heap</b> (or <b>self-adjusting heap</b>) is a <a href="/wiki/Heap_(data_structure)" title="Heap (data structure)">heap</a> <a href="/wiki/Data_structure" title="Data structure">data structure</a> implemented as a <a href="/wiki/Binary_tree" title="Binary tree">binary tree</a>. Skew heaps are advantageous because of their ability to merge more quickly than binary heaps. In contrast with <a href="/wiki/Binary_heap" title="Binary heap">binary heaps</a>, there are no structural constraints, so there is no guarantee that the height of the tree is logarithmic. Only two conditions must be satisfied: </p> <ul><li>The general heap order must be enforced</li> <li>Every operation (add, remove_min, merge) on two skew heaps must be done using a special <i>skew heap merge</i>.</li></ul> <p>A skew heap is a self-adjusting form of a <a href="/wiki/Leftist_tree" title="Leftist tree">leftist heap</a> which attempts to maintain balance by unconditionally swapping all nodes in the merge path when merging two heaps. (The merge operation is also used when adding and removing values.) With no structural constraints, it may seem that a skew heap would be horribly inefficient. However, <a href="/wiki/Amortized_analysis" title="Amortized analysis">amortized complexity analysis</a> can be used to demonstrate that all operations on a skew heap can be done in O(log <i>n</i>).<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> In fact, 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="{\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="false" scriptlevel="0"> <mi>φ</mi> <mo>=</mo> <mrow class="MJX-TeXAtom-ORD"> <mfrac> <mrow> <mn>1</mn> <mo>+</mo> <mrow class="MJX-TeXAtom-ORD"> <msqrt> <mn>5</mn> </msqrt> </mrow> </mrow> <mn>2</mn> </mfrac> </mrow> </mstyle> </mrow> <annotation encoding="application/x-tex">{\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/e6ec20261b84c788b9c79ee985daca395a9c54c4" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:9.746ex; height:4.176ex;" alt="{\textstyle \varphi ={\frac {1+{\sqrt {5}}}{2}}}" /></span> denoting the <a href="/wiki/Golden_ratio" title="Golden ratio">golden ratio</a>, the exact amortized complexity is known to be log<sub>φ</sub> <i>n</i> (approximately 1.44 log<sub>2</sub> <i>n</i>).<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><sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Skew_heap&action=edit&section=1" title="Edit section: Definition"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Skew heaps may be described with the following <a href="/wiki/Recursion" title="Recursion">recursive</a> definition:<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. (September 2020)">citation needed</span></a></i>]</sup><sup class="noprint Inline-Template" style="margin-left:0.1em; white-space:nowrap;">[<i><a href="/wiki/Wikipedia:Please_clarify" title="Wikipedia:Please clarify"><span title="The text near this tag may need clarification or removal of jargon. (July 2023)">clarification needed</span></a></i>]</sup> </p> <ul><li>A heap with only one element is a skew heap.</li> <li>The result of <i>skew merging</i> two skew heaps <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 sh_{1}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <msub> <mi>h</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>1</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle sh_{1}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/b2a78028702a9bb7199ca2bcb492fffda2c8c429" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.484ex; height:2.509ex;" alt="{\displaystyle sh_{1}}" /></span> and <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 sh_{2}}"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mi>s</mi> <msub> <mi>h</mi> <mrow class="MJX-TeXAtom-ORD"> <mn>2</mn> </mrow> </msub> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle sh_{2}}</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/a31f40a52029879bc4913c02890f31ea9eef8fb8" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.484ex; height:2.509ex;" alt="{\displaystyle sh_{2}}" /></span> is also a skew heap.</li></ul> <div class="mw-heading mw-heading2"><h2 id="Operations">Operations</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Skew_heap&action=edit&section=2" title="Edit section: Operations"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Merging_two_heaps">Merging two heaps</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Skew_heap&action=edit&section=3" title="Edit section: Merging two heaps"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>When two skew heaps are to be merged, we can use a similar process as the merge of two <a href="/wiki/Leftist_tree" title="Leftist tree">leftist heaps</a>: </p> <ul><li>Compare roots of two heaps; let <var style="padding-right: 1px;">p</var> be the heap with the smaller root, and q be the other heap. Let <var style="padding-right: 1px;">r</var> be the name of the resulting new heap.</li> <li>Let the root of r be the root of <var style="padding-right: 1px;">p</var> (the smaller root), and let r's right subtree be p's left subtree.</li> <li>Now, compute r's left subtree by recursively merging p's right subtree with q.</li></ul> <p><br /> </p> <div class="mw-highlight mw-highlight-lang-cpp mw-content-ltr" dir="ltr"><pre><span></span><span class="k">template</span><span class="o"><</span><span class="k">class</span><span class="w"> </span><span class="nc">T</span><span class="p">,</span><span class="w"> </span><span class="k">class</span><span class="w"> </span><span class="nc">CompareFunction</span><span class="o">></span> <span class="n">SkewNode</span><span class="o"><</span><span class="n">T</span><span class="o">>*</span><span class="w"> </span><span class="n">CSkewHeap</span><span class="o"><</span><span class="n">T</span><span class="p">,</span><span class="w"> </span><span class="n">CompareFunction</span><span class="o">>::</span><span class="n">Merge</span><span class="p">(</span><span class="n">SkewNode</span><span class="o"><</span><span class="n">T</span><span class="o">>*</span><span class="w"> </span><span class="n">root_1</span><span class="p">,</span><span class="w"> </span><span class="n">SkewNode</span><span class="o"><</span><span class="n">T</span><span class="o">>*</span><span class="w"> </span><span class="n">root_2</span><span class="p">)</span> <span class="p">{</span> <span class="w"> </span><span class="n">SkewNode</span><span class="o"><</span><span class="n">T</span><span class="o">>*</span><span class="w"> </span><span class="n">firstRoot</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">root_1</span><span class="p">;</span> <span class="w"> </span><span class="n">SkewNode</span><span class="o"><</span><span class="n">T</span><span class="o">>*</span><span class="w"> </span><span class="n">secondRoot</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">root_2</span><span class="p">;</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">firstRoot</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">secondRoot</span><span class="p">;</span> <span class="w"> </span><span class="k">else</span><span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">secondRoot</span><span class="w"> </span><span class="o">==</span><span class="w"> </span><span class="nb">NULL</span><span class="p">)</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">firstRoot</span><span class="p">;</span> <span class="w"> </span><span class="k">if</span><span class="w"> </span><span class="p">(</span><span class="n">sh_compare</span><span class="o">-></span><span class="n">Less</span><span class="p">(</span><span class="n">firstRoot</span><span class="o">-></span><span class="n">key</span><span class="p">,</span><span class="w"> </span><span class="n">secondRoot</span><span class="o">-></span><span class="n">key</span><span class="p">))</span> <span class="w"> </span><span class="p">{</span> <span class="w"> </span><span class="n">SkewNode</span><span class="o"><</span><span class="n">T</span><span class="o">>*</span><span class="w"> </span><span class="n">tempHeap</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">firstRoot</span><span class="o">-></span><span class="n">rightNode</span><span class="p">;</span> <span class="w"> </span><span class="n">firstRoot</span><span class="o">-></span><span class="n">rightNode</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">firstRoot</span><span class="o">-></span><span class="n">leftNode</span><span class="p">;</span> <span class="w"> </span><span class="n">firstRoot</span><span class="o">-></span><span class="n">leftNode</span><span class="w"> </span><span class="o">=</span><span class="w"> </span><span class="n">Merge</span><span class="p">(</span><span class="n">secondRoot</span><span class="p">,</span><span class="w"> </span><span class="n">tempHeap</span><span class="p">);</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">firstRoot</span><span class="p">;</span> <span class="w"> </span><span class="p">}</span> <span class="w"> </span><span class="k">else</span> <span class="w"> </span><span class="k">return</span><span class="w"> </span><span class="n">Merge</span><span class="p">(</span><span class="n">secondRoot</span><span class="p">,</span><span class="w"> </span><span class="n">firstRoot</span><span class="p">);</span> <span class="p">}</span> </pre></div> <p>Before: <span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:SkewHeapMerge1.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/1/19/SkewHeapMerge1.svg/360px-SkewHeapMerge1.svg.png" decoding="async" width="360" height="116" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/19/SkewHeapMerge1.svg/540px-SkewHeapMerge1.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/19/SkewHeapMerge1.svg/720px-SkewHeapMerge1.svg.png 2x" data-file-width="360" data-file-height="116" /></a></span> </p><p><br /> after <span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:SkewHeapMerge7.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4d/SkewHeapMerge7.svg/279px-SkewHeapMerge7.svg.png" decoding="async" width="279" height="255" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4d/SkewHeapMerge7.svg/419px-SkewHeapMerge7.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4d/SkewHeapMerge7.svg/558px-SkewHeapMerge7.svg.png 2x" data-file-width="279" data-file-height="255" /></a></span> </p> <div class="mw-heading mw-heading3"><h3 id="Non-recursive_merging">Non-recursive merging</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Skew_heap&action=edit&section=4" title="Edit section: Non-recursive merging"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Alternatively, there is a non-recursive approach which is more wordy, and does require some sorting at the outset. </p> <ul><li>Split each heap into subtrees by cutting every path. (From the root node, sever the right node and make the right child its own subtree.) This will result in a set of trees in which the root either only has a left child or no children at all.</li> <li>Sort the subtrees in ascending order based on the value of the root node of each subtree.</li> <li>While there are still multiple subtrees, iteratively recombine the last two (from right to left). <ul><li>If the root of the second-to-last subtree has a left child, swap it to be the right child.</li> <li>Link the root of the last subtree as the left child of the second-to-last subtree.</li></ul></li></ul> <p><span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:SkewHeapMerge1.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/1/19/SkewHeapMerge1.svg/360px-SkewHeapMerge1.svg.png" decoding="async" width="360" height="116" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/1/19/SkewHeapMerge1.svg/540px-SkewHeapMerge1.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/1/19/SkewHeapMerge1.svg/720px-SkewHeapMerge1.svg.png 2x" data-file-width="360" data-file-height="116" /></a></span> </p><p><span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:SkewHeapMerge2.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/9/90/SkewHeapMerge2.svg/351px-SkewHeapMerge2.svg.png" decoding="async" width="351" height="125" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/9/90/SkewHeapMerge2.svg/527px-SkewHeapMerge2.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/9/90/SkewHeapMerge2.svg/702px-SkewHeapMerge2.svg.png 2x" data-file-width="351" data-file-height="125" /></a></span> </p><p><span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:SkewHeapMerge3.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/a/ad/SkewHeapMerge3.svg/334px-SkewHeapMerge3.svg.png" decoding="async" width="334" height="125" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/a/ad/SkewHeapMerge3.svg/501px-SkewHeapMerge3.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/a/ad/SkewHeapMerge3.svg/668px-SkewHeapMerge3.svg.png 2x" data-file-width="334" data-file-height="125" /></a></span> </p><p><span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:SkewHeapMerge4.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4b/SkewHeapMerge4.svg/278px-SkewHeapMerge4.svg.png" decoding="async" width="278" height="125" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4b/SkewHeapMerge4.svg/417px-SkewHeapMerge4.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4b/SkewHeapMerge4.svg/556px-SkewHeapMerge4.svg.png 2x" data-file-width="278" data-file-height="125" /></a></span> </p><p><span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:SkewHeapMerge5.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/SkewHeapMerge5.svg/276px-SkewHeapMerge5.svg.png" decoding="async" width="276" height="171" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/c9/SkewHeapMerge5.svg/414px-SkewHeapMerge5.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/c9/SkewHeapMerge5.svg/552px-SkewHeapMerge5.svg.png 2x" data-file-width="276" data-file-height="171" /></a></span> </p><p><span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:SkewHeapMerge6.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/7/7d/SkewHeapMerge6.svg/250px-SkewHeapMerge6.svg.png" decoding="async" width="250" height="219" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/7/7d/SkewHeapMerge6.svg/375px-SkewHeapMerge6.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/7/7d/SkewHeapMerge6.svg/500px-SkewHeapMerge6.svg.png 2x" data-file-width="250" data-file-height="219" /></a></span> </p><p><span class="mw-default-size" typeof="mw:File"><a href="/wiki/File:SkewHeapMerge7.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/4/4d/SkewHeapMerge7.svg/279px-SkewHeapMerge7.svg.png" decoding="async" width="279" height="255" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/4/4d/SkewHeapMerge7.svg/419px-SkewHeapMerge7.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/4/4d/SkewHeapMerge7.svg/558px-SkewHeapMerge7.svg.png 2x" data-file-width="279" data-file-height="255" /></a></span> </p> <div class="mw-heading mw-heading3"><h3 id="Adding_values">Adding values</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Skew_heap&action=edit&section=5" title="Edit section: Adding values"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Adding a value to a skew heap is like merging a tree with one node together with the original tree. </p> <div class="mw-heading mw-heading3"><h3 id="Removing_values">Removing values</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Skew_heap&action=edit&section=6" title="Edit section: Removing values"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Removing the first value in a heap can be accomplished by removing the root and merging its child subtrees. </p> <div class="mw-heading mw-heading3"><h3 id="Implementation">Implementation</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Skew_heap&action=edit&section=7" title="Edit section: Implementation"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>In many functional languages, skew heaps become extremely simple to implement. Here is a complete sample implementation in Haskell. </p> <div class="mw-highlight mw-highlight-lang-haskell mw-content-ltr" dir="ltr"><pre><span></span><span class="kr">data</span><span class="w"> </span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="kt">Empty</span> <span class="w"> </span><span class="o">|</span><span class="w"> </span><span class="kt">Node</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="p">(</span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span><span class="p">)</span><span class="w"> </span><span class="p">(</span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span><span class="p">)</span> <span class="nf">singleton</span><span class="w"> </span><span class="ow">::</span><span class="w"> </span><span class="kt">Ord</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">=></span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">-></span><span class="w"> </span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span> <span class="nf">singleton</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="kt">Node</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="kt">Empty</span><span class="w"> </span><span class="kt">Empty</span> <span class="nf">union</span><span class="w"> </span><span class="ow">::</span><span class="w"> </span><span class="kt">Ord</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">=></span><span class="w"> </span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">-></span><span class="w"> </span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">-></span><span class="w"> </span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span> <span class="kt">Empty</span><span class="w"> </span><span class="p">`</span><span class="n">union</span><span class="p">`</span><span class="w"> </span><span class="n">t2</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">t2</span> <span class="nf">t1</span><span class="w"> </span><span class="p">`</span><span class="n">union</span><span class="p">`</span><span class="w"> </span><span class="kt">Empty</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">t1</span> <span class="nf">t1</span><span class="o">@</span><span class="p">(</span><span class="kt">Node</span><span class="w"> </span><span class="n">x1</span><span class="w"> </span><span class="n">l1</span><span class="w"> </span><span class="n">r1</span><span class="p">)</span><span class="w"> </span><span class="p">`</span><span class="n">union</span><span class="p">`</span><span class="w"> </span><span class="n">t2</span><span class="o">@</span><span class="p">(</span><span class="kt">Node</span><span class="w"> </span><span class="n">x2</span><span class="w"> </span><span class="n">l2</span><span class="w"> </span><span class="n">r2</span><span class="p">)</span> <span class="w"> </span><span class="o">|</span><span class="w"> </span><span class="n">x1</span><span class="w"> </span><span class="o"><=</span><span class="w"> </span><span class="n">x2</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="kt">Node</span><span class="w"> </span><span class="n">x1</span><span class="w"> </span><span class="p">(</span><span class="n">t2</span><span class="w"> </span><span class="p">`</span><span class="n">union</span><span class="p">`</span><span class="w"> </span><span class="n">r1</span><span class="p">)</span><span class="w"> </span><span class="n">l1</span> <span class="w"> </span><span class="o">|</span><span class="w"> </span><span class="n">otherwise</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="kt">Node</span><span class="w"> </span><span class="n">x2</span><span class="w"> </span><span class="p">(</span><span class="n">t1</span><span class="w"> </span><span class="p">`</span><span class="n">union</span><span class="p">`</span><span class="w"> </span><span class="n">r2</span><span class="p">)</span><span class="w"> </span><span class="n">l2</span> <span class="nf">insert</span><span class="w"> </span><span class="ow">::</span><span class="w"> </span><span class="kt">Ord</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">=></span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">-></span><span class="w"> </span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">-></span><span class="w"> </span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span> <span class="nf">insert</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="n">heap</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="n">singleton</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="p">`</span><span class="n">union</span><span class="p">`</span><span class="w"> </span><span class="n">heap</span> <span class="nf">extractMin</span><span class="w"> </span><span class="ow">::</span><span class="w"> </span><span class="kt">Ord</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">=></span><span class="w"> </span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span><span class="w"> </span><span class="ow">-></span><span class="w"> </span><span class="kt">Maybe</span><span class="w"> </span><span class="p">(</span><span class="n">a</span><span class="p">,</span><span class="w"> </span><span class="kt">SkewHeap</span><span class="w"> </span><span class="n">a</span><span class="p">)</span> <span class="nf">extractMin</span><span class="w"> </span><span class="kt">Empty</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="kt">Nothing</span> <span class="nf">extractMin</span><span class="w"> </span><span class="p">(</span><span class="kt">Node</span><span class="w"> </span><span class="n">x</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="n">r</span><span class="p">)</span><span class="w"> </span><span class="ow">=</span><span class="w"> </span><span class="kt">Just</span><span class="w"> </span><span class="p">(</span><span class="n">x</span><span class="p">,</span><span class="w"> </span><span class="n">l</span><span class="w"> </span><span class="p">`</span><span class="n">union</span><span class="p">`</span><span class="w"> </span><span class="n">r</span><span class="p">)</span> </pre></div> <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=Skew_heap&action=edit&section=8" title="Edit section: References"><span>edit</span></a><span class="mw-editsection-bracket">]</span></span></div> <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"> <div class="mw-references-wrap"><ol class="references"> <li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></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="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): <span class="nowrap">52–</span>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=%3Cspan+class%3D%22nowrap%22%3E52-%3C%2Fspan%3E69&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%3ASkew+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="CITEREFKaldewaijSchoenmakers1991" class="citation journal cs1">Kaldewaij, Anne; Schoenmakers, Berry (1991). <a rel="nofollow" class="external text" href="https://www.win.tue.nl/~berry/papers/topskew.pdf">"The Derivation of a Tighter Bound for Top-Down Skew Heaps"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a></i>. <b>37</b> (5): <span class="nowrap">265–</span>271. <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.56.8717">10.1.1.56.8717</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%2F0020-0190%2891%2990218-7">10.1016/0020-0190(91)90218-7</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+Processing+Letters&rft.atitle=The+Derivation+of+a+Tighter+Bound+for+Top-Down+Skew+Heaps&rft.volume=37&rft.issue=5&rft.pages=%3Cspan+class%3D%22nowrap%22%3E265-%3C%2Fspan%3E271&rft.date=1991&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.56.8717%23id-name%3DCiteSeerX&rft_id=info%3Adoi%2F10.1016%2F0020-0190%2891%2990218-7&rft.aulast=Kaldewaij&rft.aufirst=Anne&rft.au=Schoenmakers%2C+Berry&rft_id=https%3A%2F%2Fwww.win.tue.nl%2F~berry%2Fpapers%2Ftopskew.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASkew+heap" class="Z3988"></span></span> </li> <li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><link rel="mw-deduplicated-inline-style" href="mw-data:TemplateStyles:r1238218222" /><cite id="CITEREFSchoenmakers1997" class="citation journal cs1">Schoenmakers, Berry (1997). <a rel="nofollow" class="external text" href="https://www.win.tue.nl/~berry/papers/lowskew.pdf">"A Tight Lower Bound for Top-Down Skew Heaps"</a> <span class="cs1-format">(PDF)</span>. <i><a href="/wiki/Information_Processing_Letters" title="Information Processing Letters">Information Processing Letters</a></i>. <b>61</b> (5): <span class="nowrap">279–</span>284. <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.47.447">10.1.1.47.447</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%2FS0020-0190%2897%2900028-8">10.1016/S0020-0190(97)00028-8</a>. <a href="/wiki/S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:11288837">11288837</a>.</cite><span title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rft.genre=article&rft.jtitle=Information+Processing+Letters&rft.atitle=A+Tight+Lower+Bound+for+Top-Down+Skew+Heaps&rft.volume=61&rft.issue=5&rft.pages=%3Cspan+class%3D%22nowrap%22%3E279-%3C%2Fspan%3E284&rft.date=1997&rft_id=https%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fsummary%3Fdoi%3D10.1.1.47.447%23id-name%3DCiteSeerX&rft_id=https%3A%2F%2Fapi.semanticscholar.org%2FCorpusID%3A11288837%23id-name%3DS2CID&rft_id=info%3Adoi%2F10.1016%2FS0020-0190%2897%2900028-8&rft.aulast=Schoenmakers&rft.aufirst=Berry&rft_id=https%3A%2F%2Fwww.win.tue.nl%2F~berry%2Fpapers%2Flowskew.pdf&rfr_id=info%3Asid%2Fen.wikipedia.org%3ASkew+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=Skew_heap&action=edit&section=9" 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.cse.yorku.ca/~aaw/Pourhashemi/">Animations comparing leftist heaps and skew heaps, York University</a></li> <li><a rel="nofollow" class="external text" href="http://people.cis.ksu.edu/~rhowell/viewer/heapviewer.html">Java applet for simulating heaps, Kansas State University</a></li></ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" 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=Skew_heap&oldid=1226233567">https://en.wikipedia.org/w/index.php?title=Skew_heap&oldid=1226233567</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">Categories</a>: <ul><li><a href="/wiki/Category:Binary_trees" title="Category:Binary trees">Binary trees</a></li><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: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_September_2020" title="Category:Articles with unsourced statements from September 2020">Articles with unsourced statements from September 2020</a></li><li><a href="/wiki/Category:Wikipedia_articles_needing_clarification_from_July_2023" title="Category:Wikipedia articles needing clarification from July 2023">Wikipedia articles needing clarification from July 2023</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 29 May 2024, at 10:42<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=Skew_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"><picture><source media="(min-width: 500px)" srcset="/static/images/footer/wikimedia-button.svg" width="84" height="29"><img src="/static/images/footer/wikimedia.svg" width="25" height="25" alt="Wikimedia Foundation" lang="en" loading="lazy"></picture></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"><picture><source media="(min-width: 500px)" srcset="/w/resources/assets/poweredby_mediawiki.svg" width="88" height="31"><img src="/w/resources/assets/mediawiki_compact.svg" alt="Powered by MediaWiki" lang="en" width="25" height="25" loading="lazy"></picture></a></li> </ul> </footer> </div> </div> </div> <div class="vector-header-container vector-sticky-header-container"> <div id="vector-sticky-header" class="vector-sticky-header"> <div class="vector-sticky-header-start"> <div class="vector-sticky-header-icon-start vector-button-flush-left vector-button-flush-right" aria-hidden="true"> <button class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-sticky-header-search-toggle" tabindex="-1" data-event-name="ui.vector-sticky-search-form.icon"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Search</span> </button> </div> <div role="search" class="vector-search-box-vue vector-search-box-show-thumbnail vector-search-box"> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail"> <form action="/w/index.php" id="vector-sticky-search-form" class="cdx-search-input cdx-search-input--has-end-button"> <div 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"> <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> <div class="vector-sticky-header-context-bar"> <nav aria-label="Contents" class="vector-toc-landmark"> <div id="vector-sticky-header-toc" class="vector-dropdown mw-portlet mw-portlet-sticky-header-toc vector-sticky-header-toc vector-button-flush-left" > <input type="checkbox" id="vector-sticky-header-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-sticky-header-toc" class="vector-dropdown-checkbox " aria-label="Toggle the table of contents" > <label id="vector-sticky-header-toc-label" for="vector-sticky-header-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-sticky-header-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div class="vector-sticky-header-context-bar-primary" aria-hidden="true" ><span class="mw-page-title-main">Skew heap</span></div> </div> </div> <div class="vector-sticky-header-end" aria-hidden="true"> <div class="vector-sticky-header-icons"> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-talk-sticky-header" tabindex="-1" data-event-name="talk-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbles mw-ui-icon-wikimedia-speechBubbles"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-subject-sticky-header" tabindex="-1" data-event-name="subject-sticky-header"><span class="vector-icon mw-ui-icon-article mw-ui-icon-wikimedia-article"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-history-sticky-header" tabindex="-1" data-event-name="history-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-history mw-ui-icon-wikimedia-wikimedia-history"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only mw-watchlink" id="ca-watchstar-sticky-header" tabindex="-1" data-event-name="watch-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-star mw-ui-icon-wikimedia-wikimedia-star"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-edit-sticky-header" tabindex="-1" data-event-name="wikitext-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-wikiText mw-ui-icon-wikimedia-wikimedia-wikiText"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-ve-edit-sticky-header" tabindex="-1" data-event-name="ve-edit-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-edit mw-ui-icon-wikimedia-wikimedia-edit"></span> <span></span> </a> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only" id="ca-viewsource-sticky-header" tabindex="-1" data-event-name="ve-edit-protected-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-editLock mw-ui-icon-wikimedia-wikimedia-editLock"></span> <span></span> </a> </div> <div class="vector-sticky-header-buttons"> <button class="cdx-button cdx-button--weight-quiet mw-interlanguage-selector" id="p-lang-btn-sticky-header" tabindex="-1" data-event-name="ui.dropdown-p-lang-btn-sticky-header"><span class="vector-icon mw-ui-icon-wikimedia-language mw-ui-icon-wikimedia-wikimedia-language"></span> <span>5 languages</span> </button> <a href="#" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive" id="ca-addsection-sticky-header" tabindex="-1" data-event-name="addsection-sticky-header"><span class="vector-icon mw-ui-icon-speechBubbleAdd-progressive mw-ui-icon-wikimedia-speechBubbleAdd-progressive"></span> <span>Add topic</span> </a> </div> <div class="vector-sticky-header-icon-end"> <div class="vector-user-links"> </div> </div> </div> </div> </div> <div class="mw-portlet mw-portlet-dock-bottom emptyPortlet" id="p-dock-bottom"> <ul> </ul> </div> <script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.eqiad.main-75687f9f4b-vmlb2","wgBackendResponseTime":156,"wgPageParseReport":{"limitreport":{"cputime":"0.240","walltime":"0.764","ppvisitednodes":{"value":818,"limit":1000000},"postexpandincludesize":{"value":14222,"limit":2097152},"templateargumentsize":{"value":1445,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":6,"limit":500},"unstrip-depth":{"value":1,"limit":20},"unstrip-size":{"value":26145,"limit":5000000},"entityaccesscount":{"value":0,"limit":400},"timingprofile":["100.00% 618.432 1 -total"," 22.34% 138.177 1 Template:Short_description"," 19.74% 122.091 1 Template:Reflist"," 16.86% 104.295 3 Template:Cite_journal"," 16.31% 100.897 1 Template:Citation_needed"," 13.87% 85.760 1 Template:Fix"," 13.22% 81.759 2 Template:Pagetype"," 11.19% 69.211 4 Template:Category_handler"," 9.48% 58.651 1 Template:Confusion"," 6.99% 43.207 4 Template:Main_other"]},"scribunto":{"limitreport-timeusage":{"value":"0.127","limit":"10.000"},"limitreport-memusage":{"value":4114495,"limit":52428800}},"cachereport":{"origin":"mw-api-ext.eqiad.main-df448499c-h7pkj","timestamp":"20250318160118","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Skew heap","url":"https:\/\/en.wikipedia.org\/wiki\/Skew_heap","sameAs":"http:\/\/www.wikidata.org\/entity\/Q4893208","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q4893208","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":"2006-01-13T11:45:57Z","dateModified":"2024-05-29T10:42:16Z","headline":"heap data structure implemented as a binary tree"}</script> </body> </html>