Купа (структура даних)




Приклад повної бінарної купи


Купа, стіс[1][2] або піраміда (англ. heap) в інформатиці — спеціалізована деревовидна структура даних, в якій існують певні властивості впорядкованості: якщо В — вузол нащадок A — тоді ключ(A) ≥ ключ(B). З цього випливає, що елемент з найбільшим ключем завжди є кореневим вузлом. Не існує ніяких обмежень щодо максимальної кількості елементів-нащадків повинна мати кожна ланка, однак, на практиці, зазвичай, кожен елемент має не більше двох нащадків. Купа є однією із найефективніших реалізацій абстрактного типу даних, який має назву черга з пріоритетом. Купи відіграють критичну роль у низці ефективних алгоритмів роботи з графами, як то в алгоритмі Дейкстри та в алгоритмі сортування пірамідальне сортування. Найуживанішим класом куп є бінарні купи.


Базові операції з купою такі:


  • підтримка основної властивості купи

  • побудова купи з невпорядкованого масиву

  • сортування купи

  • видалення найменшого елемента

  • отримання найбільшого елемента

  • додавання елемента

Купи часто використовуються для моделювання черг з пріоритетами.



Див. також |


  • Стек

  • Бінарна купа


  • d-арна купа

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

  • Фібоначчієва купа


Примітки |




  1. ↑ heap // Англійсько-український словник з математики та інформатики / Уклад. Є. Мейнарович, М. Кратко — 2010.


  2. ↑ Кочерга О., Мейнарович Є. Англійсько-українсько-англійський словник наукової мови (фізика та споріднені науки). — Вінниця: Нова книга, 2010.















  • п

  • о

  • р



Деревні структури даних


Дерева пошуку
(динамічні множини/асоціативні масиви)


  • 2–3[en]


  • 2–3–4[en]


  • АА[en]


  • (a,b)[en]

  • АВЛ

  • Б

  • Б+


  • Б*[en]


  • Бx[en]

  • (Оптимальний[en]) Двійковий пошук


  • Збалансоване за вагою[en]


  • Інтервальне[en]


  • Порядкова статистика[en]


  • Рандомізований двійковий пошук[en]

  • Розширюване


  • Т[en]


  • Танцювальне[en]


  • ХДерево[en]


  • Цап-відбувайло[en]

  • (Лівобічне[en]) Червоно-чорне


  • UB[en]


Купи

  • Бінарна

  • Біноміальна

  • Ван Емде Боаса


  • Лівацька[en]


  • Скошена[en]


  • Спарена[en]

  • Фібоначчієва



Префіксні дерева

  • Базисне

  • Суфіксне


  • Тернарного пошуку[en]


  • Хеш[en]


  • X-швидке[en]


  • Y-швидке[en]


Дерева просторового розбиття даних


  • БВП[en]


  • БК[en]

  • БРП

  • Відрізків


  • ВП[en]


  • Гільбертове R[en]

  • Декартове


  • k-вимірне (неявне k-вимірне[en])

  • Дерево квадрантів


  • М[en]


  • Метричне[en]

  • Октодерево


  • Пріоритетизоване R[en]

  • R


  • R+[en]


  • R*


  • X[en]


Інші дерева


  • Експоненційне[en]


  • Двозв'язкове[en]


  • Динамічне[en]


  • Діапазонне[en]


  • Злиття[en]


  • iDistance[en]


  • k-арне[en]


  • LSM[en]

  • Дерево Меркла


  • Над[en]


  • Пальцеве[en]


  • PQ[en]


  • Покриттів[en]


  • SPQR[en]

  • Фенвіка


  • Хеш-календар[en]



-

Popular posts from this blog

AWS Lex not identifying response if by a variable The 2019 Stack Overflow Developer Survey Results Are In Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 17/18, 2019 at 00:00UTC (8:00pm US/Eastern) The Ask Question Wizard is Live! Data science time! April 2019 and salary with experienceEnforcing custom enumeration in AWS LEX for slot valuesHow to give response based on user response in Amazon Lex?Intercepting AWS Lambda Response to a AWS Lex QueryLex chat bot error: Reached second execution of fulfillment lambda on the same utteranceamazon lex showing invalid responseLambda response send back to Lex slot?Response card in Amazon lexAmazon Lex - Lambda response return HTML to botHow can I solve 424 (Failed Dependency) (python) obtained from Amazon lex?

Image
Do working physicists consider Newtonian mechanics to be "falsified"? Match Roman Numerals Derivation tree not rendering How can I protect witches in combat who wear limited clothing? Is above average number of years spent on PhD considered a red flag in future academia or industry positions? Relations between two reciprocal partial derivatives? Take groceries in checked luggage He got a vote 80% that of Emmanuel Macron’s Why not take a picture of a closer black hole? Is every episode of "Where are my Pants?" identical? Problems with Ubuntu mount /tmp Why is superheterodyning better than direct conversion? Are spiders unable to hurt humans, especially very small spiders? Can undead you have reanimated wait inside a portable hole? What is special about square numbers here? Python - Fishing Simulator Is this wall load bearing? Blueprints and photos attached Can a 1st-level character have an ability score above 18? Semisimplicity of ...
Read more

Property … does not exist on type 'IntrinsicAttributes & …'property does not exists on type ''Angular 2 beta.17: Property 'map' does not exist on type 'Observable<Response>'Can't bind to 'ngModel' since it isn't a known property of 'input'TypeScript TS2339 error in React component: Property 'xyz' does not exist on type 'IntrinsicAttributes…'property of type forEach does not exist on type voidAdd onclick listener reactjsProperty 'pictures' does not exist on type 'IntrinsicAttributes & IntrinsicClassAttributesTypescript redux connected component type errorTypescript+React+Redux+reactrouter:“property does not exist on type IntrinsicAttributes & IntrinsicClassAttributes” passing props from parent to childUnable to set ref due to error “TS2339: Property 'X' does not exist on type 'Y' ” inside a react component

Image
How to have a sharp product image? Overlay of two functions leaves gaps A ​Note ​on ​N! Why does Mind Blank stop the Feeblemind spell? Can SQL Server create collisions in system generated constraint names? Can someone publish a story that happened to you? As an international instructor, should I openly talk about my accent? How can I print the prosodic symbols in LaTeX? Why does nature favour the Laplacian? Is it idiomatic to construct against `this` How to denote matrix elements succinctly? Can I grease a crank spindle/bracket without disassembling the crank set? How to display Aura JS Errors Lightning Out What is the philosophical significance of speech acts/implicature? Is there any official lore on the Far Realm? Minor Revision with suggestion of an alternative proof by reviewer How would 10 generations of living underground change the human body? Do I have an "anti-research" personality? can anyone help me with this awful query ...
Read more

C# Print list of string array The Next CEO of Stack OverflowUseless output to console when printing result of ReadAllLinesC# & very new Programming in generalWhat is the difference between String and string in C#?How do I check if a list is empty?Create ArrayList from arrayFinding the index of an item given a list containing it in PythonHow to append something to an array?How to make a flat list out of list of lists?How to check if an object is an array?How do I remove a particular element from an array in JavaScript?For-each over an array in JavaScript?Why not inherit from List<T>?

Image
Is there such a thing as a proper verb, like a proper noun? Is there an equivalent of cd - for cp or mv Why don't programming languages automatically manage the synchronous/asynchronous problem? Is there a difference between "Fahrstuhl" and "Aufzug"? Is it ok to trim down a tube patch? Lucky Feat: How can "more than one creature spend a luck point to influence the outcome of a roll"? From jafe to El-Guest (How) Could a medieval fantasy world survive a magic-induced "nuclear winter"? Is it OK to decorate a log book cover? Is French Guiana a (hard) EU border? What is the process for purifying your home if you believe it may have been previously used for pagan worship? Why do we say 'Un seul M' and not 'Une seule M' even though M is a "consonne" IC has pull-down resistors on SMBus lines? TikZ: How to fill area with a special pattern? Strange use of "whether ... than ..." in official...
Read more