Сливаемая куча

Сливаемая куча (англ. Mergeable heap) — структура данных, которая поддерживает следующие пять операций:

Создание пустой кучи $H$ (англ. Make heap);
Вставка узла $x$ в кучу $H$ (англ. Insert);
Поиск узла в куче $H$ , который обладает минимальным ключом (англ. Minimum);
Удаление узла с минимальным ключом из кучи $H$ (англ. Extract minimum);
Создание новой кучи $H$ , которая содержит все узлы куч $H_{1}$ и $H_{2}$ (англ. Union).

Реализации

Следующие две структуры данных являются реализациями сливаемой кучи:

Эти структуры данных так же поддерживают еще 2 операции:

Присваивание узлу $x$ в куче $H$ нового значения ключа (англ. Decrease key) (предполагается, что новое значение ключа не превосходит текущего);
Удаление узла $x$ из кучи $H$ (англ. Delete).

Время выполнения операций у разных реализаций сливаемых пирамид
Операция	Биномиальная куча	Фибоначчиева куча
Make heap	Θ(1)	Θ(1)
Insert	O(lgn)	Θ(1)
Minimum	O(lgn)	Θ(1)
Extract minimum	Θ(lgn)	O(lgn)
Union	Ω(lgn)	Θ(1)
Decrease key	Θ(lgn)	Θ(1)
Delete	Θ(lgn)	O(lgn)

Примечание: для Биномиальной кучи время в наихудшем случае, для Фибоначчиевой кучи амортизированное время.

Замечание. По умолчанию сливаемые кучи являются неубывающими сливаемыми кучами (англ. Mergeable min-heap). Также существуют невозрастающие сливаемые кучи (англ. Mergeable max-heap), которые поддерживают следующие операции:

Создание пустой кучи $H$ (англ. Make heap);
Вставка узла $x$ в кучу $H$ (англ. Insert);
Поиск узла в куче $H$ , который обладает максимальныи ключом (англ. Maximum);
Удаление узла с максимальныи ключом из кучи $H$ (англ. Extract maximum);
Создание новой кучи $H$ , которая содержит все узлы куч $H_{1}$ и $H_{2}$ (англ. Union).
Присваивание узлу $x$ в куче $H$ нового значения ключа (англ. Increase key);
Удаление узла $x$ из кучи $H$ (англ. Delete).

Литература

Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. — М.: Издательский дом «Вильямс», 2007. — С. 1296. — ISBN 5-8459-0857-4.

Read other articles:

Amis-amisan

Amis-amisan Houttuynia cordata TumbuhanJenis buahkapsul TaksonomiDivisiTracheophytaSubdivisiSpermatophytesKladAngiospermaeKladmagnoliidsOrdoPiperalesFamiliSaururaceaeGenusHouttuyniaSpesiesHouttuynia cordata Thunb. lbs Houttuynia cordata, juga dikenal sebagai amis-amisan, daun ikan, atau rumput ikan Cina, adalah salah satu dari dua spesies dalam genus Houttuynia (yang lainnya adalah H. emeiensis ). Ini adalah tanaman berbunga asli Asia Tenggara . [1] Tumbuh di lokasi yang lem...

Cat Fanciers' Association

Cat Fanciers' AssociationLogo CFASingkatanCFATanggal pendirian1906Tujuanuntuk melestarikan dan meningkatkan keturunan-keturunan kucing dan untuk meningkatkan kesejahteraan semua kucingLokasiAlliance, Ohio, Amerika SerikatWilayah layanan Seluruh negaraBahasa resmi InggrisSitus webwww.cfa.org CFA International Cat Show di Atlanta pada 22 November 2008. Cat Fanciers' Association (atau CFA, bahasa Indonesia: Perhimpunan Penyayang Kucing) adalah organisasi kucing yang didirikan di Amerika Serikat ...

Cultural depictions of George Washington

Washington at Princeton, by Charles Willson Peale, 1779 This article is part of a series aboutGeorge Washington Early life Family Military career Electoral history American Revolution Virginia Association Commander in Chiefof the Continental Army Valley Forge Battle of Trenton Mount Vernon Conference 1787 Constitutional Convention 1st President of the United States Presidency (Timeline) First term 1788–89 election 1st inauguration Judiciary Act Whiskey Rebellion Thanksgiving Presidential t...

St Joseph's F.C.

St Joseph's FCNama lengkapSt Joseph's Football Club GibraltarJulukanThe SaintsBerdiri20 January 1912; 112 tahun lalu (20 January 1912)StadionStadion Victoria,Winston Churchill Avenue, Gibraltar(Kapasitas: 2,000)PemilikMike GarlickManajerAbraham PazLigaLiga Sepak Bola Gibraltar2022–23Grup Kejuaraan: 5Secara keseluruhan: peringkat ke-5Situs webSitus web resmi klub Kostum kandang Kostum tandang St Joseph's FC adalah klub sepak bola yang berbasis di Gibraltar. Sejarah Pada Juni 2022, ...

Couche électronique

Pour un article plus général, voir Configuration électronique. Modèle de Bohr d'un atome à trois couches électroniques. En chimie et en physique atomique, une couche électronique d'un atome est l'ensemble des orbitales atomiques partageant un même nombre quantique principal n ; les orbitales partageant en plus un même nombre quantique azimutal ℓ forment une sous-couche électronique. Les termes couche et sous-couche sont hérités de la théorie des quanta du début du XXe...

Coral bleaching

Phenomenon where coral expel algae tissue Healthy coralBleached coral Coral bleaching is the process when corals become white due to loss of symbiotic algae and photosynthetic pigments. This loss of pigment can be caused by various stressors, such as changes in temperature, light, or nutrients.[1][2] Bleaching occurs when coral polyps expel the zooxanthellae (dinoflagellates that are commonly referred to as algae) that live inside their tissue, causing the coral to turn white....

The Great Stone Face (Hawthorne)

The Great Stone Face as it appeared in The Snow-Image, and Other Twice-Told Tales The Great Stone Face is a short story published by Nathaniel Hawthorne in 1850. The story reappeared in a full-length book, The Snow-Image, and Other Twice-Told Tales, published by Ticknor, Reed & Fields in 1852. It has since been republished and anthologized many times.[1] Plot summary Hawthorne sets the scene in a rural valley located in an unnamed U.S. state that resembles New Hampshire. A rock fo...

Антитринитаризм

ХристианствоБиблия Ветхий Завет Новый Завет Евангелие Десять заповедей Нагорная проповедь Апокрифы Бог, Троица Бог Отец Иисус Христос Святой Дух История христианства Апостолы Хронология христианства Раннее христианство Гностическое христианство Вселенские соборы Н...

Династія Мін

大明 Велика Мін 1368 – 1644 ↓ Династія Мін: історичні кордони на картіМінський Китай за правління імператора Юн Ле Столиця Нанкін(1368—1421)Пекін(1421—1644) 39°54′ пн. ш. 116°23′ сх. д.H G O Мови китайська Форма правління монархія Імператор - 1368-1398 імператор Хун У - 1627-...

بطولة ويمبلدون 1936 - فردي السيدات

بطولة ويمبلدون 1936 - فردي السيدات جزء من بطولة ويمبلدون 1936 البلد المملكة المتحدة التاريخ 1936 الرياضة كرة المضرب البطل(ة) هيلين جاكوبز الوصيف(ة) هيلدا كراهوينكيل سبيرلنغ النتيجة 6–2، 4–6، 7–5 بطولة ويمبلدون 1935 - فردي السيدات بطولة ويمبلدون 1937 - فردي السيدات ت...

مذبحة الطنطورة

مذبحة الطنطورة جزء من الصراع العربي الإسرائيلي الصراع العربي الإسرائيلي المعلومات البلد فلسطين الموقع جنوب حيفا التاريخ 22-23 مايو 1948 نوع الهجوم الاعدام الخسائر الوفيات 90 المنفذون كتيبة 33 لواء اسكندروني تعديل مصدري - تعديل مذبحة الطنطورة ومجزرة الطنطورة [1] �...

2019 Rugby World Cup final

Final 2019 Rugby World Cup match won by South Africa Football match2019 Rugby World Cup finalInternational Stadium Yokohama hosted the matchEvent2019 Rugby World Cup England South Africa 12 32 Date2 November 2019VenueInternational Stadium Yokohama, YokohamaPlayer of the matchDuane Vermeulen (South Africa)RefereeJérôme Garcès (France)[1]Attendance70,103← 2015 2023 → The 2019 Rugby World Cup final was a rugby union match played on 2 November 2019 at the International Stad...

Expressed emotion

Expressed emotion (EE), is a measure of the family environment that is based on how the relatives of a psychiatric patient spontaneously talk about the patient.[1] It specifically measures three to five aspects of the family environment: the most important are critical comments, hostility, emotional over-involvement, with positivity and warmth sometimes also included as indications of a low-EE environment.[2] The psychiatric measure of expressed emotion is distinct from the ge...

2011 in India

List of events ← 2010 2009 2008 2011 in India → 2012 2013 2014 Centuries: 19th 20th 21st Decades: 1990s 2000s 2010s 2020s See also:List of years in IndiaTimeline of Indian history Events in the year 2011 in the Republic of India. Incumbents Photo Post Name President Pratibha Patil Vice President Mohammad Hamid Ansari Prime Minister Manmohan Singh Chief Justice S. H. Kapadia Governors Post Name Andhra Pradesh E. S. L. Narasimhan Arunachal Pradesh Joginder Jaswant Singh Assam Janak...

العلاقات الألمانية الجورجية

العلاقات الألمانية الجورجية ألمانيا جورجيا ألمانيا جورجيا تعديل مصدري - تعديل العلاقات الألمانية الجورجية هي العلاقات الثنائية التي تجمع بين ألمانيا وجورجيا.[1][2][3][4][5] مقارنة بين البلدين هذه مقارنة عامة ومرجعية للدولتين: وجه المقارن...

Hicksbeachia

Genus of trees in the family Proteaceae from eastern Australia Hicksbeachia Hicksbeachia pinnatifolia Scientific classification Kingdom: Plantae Clade: Tracheophytes Clade: Angiosperms Clade: Eudicots Order: Proteales Family: Proteaceae Subfamily: Grevilleoideae Tribe: Macadamieae Subtribe: Gevuininae Genus: HicksbeachiaF.Muell.[1][2] Species See text Hicksbeachia is a genus of two species of trees in the family Proteaceae. They are native to rainforests of northern New South ...

Liste des monarques britanniques

Cet article concerne les monarques de Grande-Bretagne puis du Royaume-Uni depuis 1707. Pour la période antérieure, voir Liste des monarques d'Angleterre et Liste des monarques d'Écosse. La liste des monarques britanniques rassemble les souverains des royaumes de Grande-Bretagne puis du Royaume-Uni depuis 1707. Charles III est le roi du Royaume-Uni depuis le 8 septembre 2022. Histoire Le 1er mai 1707, les actes d'Union fusionnent les royaumes d'Angleterre et d'Écosse au sein d'une...

Saraba Kamen Rider Den-O: Final Countdown

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Saraba Kamen Rider Den-O: Final Countdown – news · newspapers · books · scholar · JSTOR (September 2015) (Learn how and when to remove this message) 2008 Japanese filmSaraba Kamen Rider Den-O the Movie: Final CountdownJapanese nameKanji劇場版さらば仮�...

Yugambeh–Bundjalung languages

Language branch spoken in Australia Yugambeh–BandjalangicEthnicityBundjalung people (Minyungbal, Widjabal), Western Bundjalung people, Githabul, Yugambeh peopleGeographicdistributionQueensland and New South Wales, AustraliaNative speakers670 (2021 census)[1]Linguistic classificationPama–NyunganSoutheasternNorth CoastYugambeh–BandjalangicSubdivisions Wahlubal Yugambeh Lower Richmond Githabul Language codesISO 639-3bdyGlottologband1339ELPBandjalangBandjalangic languages (gree...

Old Toronto

This article is about the former city of Toronto in 1834–1997. For the city of Toronto in 1793–1834, see York, Upper Canada. For the neighbourhood in Toronto, see Old Town, Toronto. Dissolved city in Ontario, CanadaOld TorontoDissolved (core) city (lower-tier)Skyline of Old Toronto from the Toronto Harbour FlagCoat of armsLogoNickname(s): Toronto the Good, Queen City, HogtownMotto(s): Industry, Intelligence, IntegrityCity of Toronto before 1998 in redCoordinates: 43°39′09″N...