Біноміальна купа

Біноміальні дерева ступенів від 0 до 3: Кожне дерево має кореневий вузол з піддеревами всіх нижчих ступенів. Наприклад, біноміальне дерево порядку 3 зв'язане з біноміальними деревами ступенів 2, 1 і 0 (підсвіченими відповідно синім, зеленим і червоним).

Біноміальна купа (англ. binomial heap) — це множина біноміальних дерев, що задовольняє властивостям біноміальної купи:

  1. Кожне біноміальне дерево у купі підпорядковується властивості неспадної купи (англ. min-heap property): ключ вузла не менший за ключ його батьківського вузла.
  2. Для будь-якого невід'ємного цілого k в купі існує не більше одного біноміального дерева, чий корінь має ступінь k.

З даних властивостей випливає, що біноміальна купа, що має n вузлів, складається з не більше ніж біноміальних дерев.

Завдяки своїй структурі, біноміальне дерево ступеня k можна побудувати з двох дерев ступеня k−1 тривіальним приєднанням одного з них до іншого, як найлівішого підпорядкованого дерева. Ця властивість є центральною для операції злиття біноміальних дерев, яка становить їхню основну перевагу над звичайними купами.

Ім'я походить від того факту, що біноміальне дерево ступеня має вузлів на глибині .

Структура біноміальної купи

Біноміальна купа втілена як множина біноміальних дерев які задовольняють властивостям біноміальної купи:

  • Наявні одне або нуль біноміальних дерев для кожного ступеня, включно з нульовим ступенем.

Перша властивість гарантує те, що корінь кожного дерева містить найменший ключ у дереві.

Друга властивість тягне за собою те, що біноміальна купа з n вузлами складається з не більше ніж log n + 1 біноміальних дерев. Насправді, кількість і ступені дерев однозначно визначаються кількістю вузлів n: кожне біноміальне дерево відповідає одному числу двійкового представлення числа n. Наприклад, число 13 є 1101 у двійковому форматі, , отже біноміальна купа з 13 вузлами складається з трьох біноміальних дерев ступенів 3, 2 і 0.

Приклад біноміальної купи
Приклад біноміальної купи, що містить 13 вузлів з різними ключами.
Купи складається з біноміальних дерев ступенів 0, 2 і 3.

Джерела

  • Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Розділ 6.1: Купи. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.

Read other articles:

François Moubandje

François Moubandje Brasil dan Swiss sedang mempersiapkan pertemuan tatap muka di Rostov Arena, 2018Informasi pribadiNama lengkap François MoubandjeTanggal lahir 21 Juni 1990 (umur 33)Tempat lahir Douala, KamerunTinggi 180 cm (5 ft 11 in)Posisi bermain BekInformasi klubKlub saat ini ToulouseNomor 29Karier senior*Tahun Tim Tampil (Gol)2013 – Toulouse 111 (0)Tim nasional2014 – Swiss 18 (0) * Penampilan dan gol di klub senior hanya dihitung dari liga domestik François ...

 

العلاقات الأفغانية الإماراتية

العلاقات الأفغانية الإماراتية أفغانستان الإمارات العربية المتحدة   أفغانستان   الإمارات العربية المتحدة تعديل مصدري - تعديل   العلاقات الأفغانية الإماراتية هي العلاقات الثنائية التي تجمع بين أفغانستان والإمارات العربية المتحدة.[1][2][3][4][5&#...

 

James I of Scotland

King of Scots from 1406 to 1437 Not to be confused with James VI and I. James I16th-century portrait of JamesKing of ScotsReign4 April 1406 – 21 February 1437Coronation21 May 1424PredecessorRobert IIISuccessorJames IIRegents See list Robert Stewart, Duke of Albany (1406–1420) Murdoch Stewart, Duke of Albany (1420–1424) Bornpossibly 25 July 1394[1][2]Dunfermline Abbey, Fife, ScotlandDied21 February 1437 (aged around 42)[3][4]Blackfriars, Perth, ScotlandBur...

All Angels' Church

Church in Manhattan, New York All Angels' ChurchStreetside view of All Angels'General informationLocationManhattan, New York CityOpened1849Closed1979Demolished1979 All Angels' Church is located on 251 West 80th Street in the Upper West Side of Manhattan in New York City. It is a member of the Episcopal Church in the United States and the Anglican Communion worldwide.[not verified in body] In 2020, it reported 406 members, average attendance of 288, and $1,177,595 in plate and pledge i...

 

Novum Testamentum Graece

 Bagian dari seriAlkitab Kanon Alkitabdan kitab-kitabnya Tanakh(Taurat · Nevi'im · Ketuvim)Kanon Alkitab Kristen · Alkitab IbraniPerjanjian Lama (PL) · Perjanjian Baru (PB) Deuterokanonika · Antilegomena Bab dan ayat dalam Alkitab Apokrifa:(Yahudi · PL · PB) Perkembangan dan Penulisan Penanggalan Kanon Yahudi Perjanjian Lama Kanon Perjanjian Baru Surat-surat Paulus Karya-karya Yohanes Surat-surat Petrus Terjemahandan N...

 

Политиздат

Издательство политической литературы ЦК КПСС (Политиздат) Основано 1918 Ликвидировано 1991 Страна  СССР Адрес 125811, Москва, Миусская площадь, 7[1] Код Госкомиздата СССР 079 Награды Информация в Викиданных ? Изда́тельство полити́ческой литерату́ры ЦК КПСС (Политизда́т) ...

96th Sustainment Brigade (United States)

96th Infantry DivisionShoulder sleeve insigniaActive1918–1919 1921–1946 1946–presentCountry United StatesAllegiance United States ArmyBranchU.S. Army (Reserve)TypeSustainment brigadeNickname(s)Columbia Division Deadeye DivisionEngagementsWorld War IIBattle of OkinawaBattle of LeyteNATO intervention in BosniaSFORKFORGWOTOperation Enduring FreedomOperation Iraqi FreedomDecorationsPresidential Unit CitationCommandersCommanderCOL Charles E. FairbanksNotablecommandersMGen James L....

 

大字 (数字)

この項目には、一部のコンピュータや閲覧ソフトで表示できない文字が含まれています（詳細）。 数字の大字（だいじ）は、漢数字の一種。通常用いる単純な字形の漢数字（小字）の代わりに同じ音の別の漢字を用いるものである。 概要 壱万円日本銀行券（「壱」が大字） 弐千円日本銀行券（「弐」が大字） 漢数字には「一」「二」「三」と続く小字と、「壱」「�...

 

مركز كريستوفر سي. كرافت جونيور للتحكم بالمهمات

مركز كريستوفر سي. كرافت جونيور للتحكم بالمهماتالتسميةنسبة الاسم إلى كريستوفر كولومبوس كرافت الابن معلومات عامةنوع المبنى مركز مراقبة البعثة مبنى[1] العنوان Lyndon B. Johnson Space Flight Center (بالإنجليزية)[1] المنطقة الإدارية هيوستن[1] البلد  الولايات المتحدة[1] الصفة �...

Aviculin

Aviculin Names IUPAC name [(1S,2R,3R)-7-Hydroxy-1-(4-hydroxy-3-methoxyphenyl)-3-(hydroxymethyl)-6-methoxy-1,2,3,4-tetrahydronaphthalen-2-yl]methyl α-L-rhamnopyranoside Systematic IUPAC name (2R,3R,4R,5R,6S)-2-{[(1S,2R,3R)-7-Hydroxy-1-(4-hydroxy-3-methoxyphenyl)-3-(hydroxymethyl)-6-methoxy-1,2,3,4-tetrahydronaphthalen-2-yl]methoxy}-6-methyloxane-3,4,5-triol Other names isolariciresinol-9'-rhamnopyranoside Identifiers CAS Number 156765-33-2[1] N 3D model (JSmol) Interactive image...

 

Mahmoud Ahmed

Ethiopian singer (born 1941) This article is about the Ethiopian singer. For the Egyptian water polo player, see Mahmoud Ahmed (water polo). For the Director General of the Inter-Services Intelligence, see Mahmud Ahmed. This biography of a living person needs additional citations for verification. Please help by adding reliable sources. Contentious material about living persons that is unsourced or poorly sourced must be removed immediately from the article and its talk page, especially if po...

 

Jamie Lee Rattray

Canadian ice hockey player Ice hockey player Jamie Lee Rattray Rattray with PWHL Boston in 2024Born (1992-09-30) September 30, 1992 (age 31)Kanata, Ontario, CanadaHeight 5 ft 6 in (168 cm)Weight 172 lb (78 kg; 12 st 4 lb)Position ForwardShoots LeftPWHL teamFormer teams PWHL BostonMarkham ThunderClarkson Golden KnightsNational team  CanadaPlaying career 2010–present Medal record Women's ice hockey Representing  Canada Olympic Games 2022 B...

Autonomous Orthodox Metropolia of North and South America and the British Isles

True Orthodox jurisdiction This article relies excessively on references to primary sources. Please improve this article by adding secondary or tertiary sources. Find sources: Autonomous Orthodox Metropolia of North and South America and the British Isles – news · newspapers · books · scholar · JSTOR (December 2021) (Learn how and when to remove this message) Autonomous Orthodox Metropolia of North and South America and the British IslesOfficial logo o...

 

جويل أغويلار

جويل أغويلار   معلومات شخصية الميلاد 2 يوليو 1975 (العمر 48 سنة)سان سلفادور الطول 170 سنتيمتر  الجنسية السلفادور  تعديل مصدري - تعديل   جويل أنتونيو أغويلار تشيكاس (بالإسبانية: Joel Antonio Aguilar Chicas)‏ (مواليد 2 يوليو 1975) حكم كرة قدم سلفادوري مقيم في سان سلفادور .[1][2] أصب...

 

Grand Prix sepeda motor Jepang 2019

  Grand Prix Jepang 2019Detail lombaLomba ke 16 dari 19Grand Prix Sepeda Motor musim 2019Tanggal20 October 2019Nama resmiMotul Grand Prix of Japan[1][2]LokasiTwin Ring Motegi, Motegi, JepangSirkuitFasilitas balapan permanen4.801 km (2.983 mi)MotoGPPole positionPembalap Marc Márquez HondaCatatan waktu 1:45.763 Putaran tercepatPembalap Marc Márquez HondaCatatan waktu 1:45.766 di lap 5 PodiumPertama Marc Márquez HondaKedua Fabio Quartararo YamahaKetiga Andr...

Second Gotabaya Rajapaksa cabinet

Government of Sri Lanka Second Gotabaya Rajapaksa cabinetCabinet of Sri LankaDate formed12 August 2020 (2020-08-12)Date dissolved3 April 2022 (2022-04-03)People and organisationsHead of stateGotabaya RajapaksaHead of governmentGotabaya RajapaksaDeputy head of governmentMahinda RajapaksaMember parties  Sri Lanka People's Freedom Alliance  Eelam People's Democratic Party  Sri Lanka Freedom PartyStatus in legislatureMajority coalition 159 / 225 ...

 

Sertão (Rio Grande do Sul)

Questa voce sull'argomento centri abitati del Rio Grande do Sul è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Sertãocomune Sertão – Veduta LocalizzazioneStato Brasile Stato federato Rio Grande do Sul MesoregioneNoroeste Rio-Grandense MicroregionePasso Fundo AmministrazioneSindacoMarcelo D'Agostini TerritorioCoordinate27°59′03″S 52°15′26″W27°59′03″S, 52°15′26″W (Ser...

 

ナタリア・ダイアー

ナタリア・ダイアー 生年月日 (1995-01-13) 1995年1月13日（29歳）出生地 アメリカ合衆国ナッシュビル主な作品 『ストレンジャー・シングス 未知の世界』『ストレンジ・フィーリング アリスのエッチな青春白書』テンプレートを表示 ナタリア・ダイアー（Natalia Dyer、1995年1月13日[1][2] -　）は、アメリカ合衆国の女優。 経歴 アメリカ合衆国のテネシー州ナッシュ...

Casque d'or (Suède)

Pour le film français de 1952, voir Casque d'Or (film). Casque d'or Nom original Guldhjälmen Pays Suède Date de création 1986 Dernier récipiendaire Jacob Josefson modifier  Le Casque d'or — Guldhjälmen en suédois — est un trophée de hockey sur glace de Suède. Il est remis annuellement, depuis la saison 1985-1986 au meilleur joueur de la division élite suédoise, l'Elitserien[1]. Le récipiendaire est désigné chaque année par le vote des joueurs de la ligue entière. Le ...

 

Dominga Ortiz Orzúa

Three-time First Lady of Venezuela, wife of José Antonio Páez In this Spanish name, the first or paternal surname is Ortiz and the second or maternal family name is Orzúa. Dominga Ortiz OrzúaFirst Lady of VenezuelaPresidentJosé Antonio PáezIn role13 January 1830 – 20 January 1835Preceded byPosition createdSucceeded byEncarnación MaitínIn role1 February 1839 – 28 January 1843Preceded byOlalla Buroz y TovarSucceeded byOlalla Buroz y TovarIn role29 August 18...