Използвах структура от данни, която първоначалният програмист наричаше heap, той се използва за изпълнение на приоритетна опашка.
Докато има много неща за двоичните дървета, (мин / макс) купчините изглеждат по-малко дефинирани (подробностите се различават в отделните изпълнения).
Някои характеристики, които съм забелязал, че не задължително се отнасят за структури от бинарни дървета.
- Същият елемент може да бъде в опашката няколко пъти, без да се усложняват при изпълнението или изпълнението.
- търсене (възможно и по-бързо от изчерпателно търсене), не е толкова ефективна (тъй като детските елементи на всеки възел не трябва да бъдат балансирани).
- Тъй като търсенето не е ефективно и има потенциал за дублиране, премахването може да изисква запаметяване на препратка към
node, вместо да използвате akeyда се търси в възела (което е обичайна практика за двоични дървета). - Промяната на приоритетите в купчината е тривиално, в сравнение с двойно дърво където най-често се изтрива + вмъкване.
(с по-добър и най-лош случай в сравнение с двоичните дървета)
Има ли по-подробна терминология за структури от данни, които съответстват на тези характеристики?
Или просто е min/max heap който се случва да бъде използван като priority-queue?
Забележете, че тук има връзка към мин-купчина който има описаните по-горе характеристики.
Отговори:
2 за отговор № 1А двойна купчина е конкретно изпълнение на. \ t приоритетна опашка абстрактна структура на данните. Той е популярен, защото е лесен за изпълнение, памет е ефективна и е сравнително бърза: O (log n) вмъкване, и O (log n) отстраняване на корена (най-малък в купчина мин., Най-големият в макс куп) , Повечето изпълнения също така предоставят метод на поглед, който позволява разглеждането на основния елемент, без да го премахва.
А двоичен куп не прави нищо другоособено добре. Противно на вашето наблюдение, намирането на конкретен елемент в двоичен куп изисква последователно сканиране. Въпреки че възлите са подредени (не са сортирани), поръчката не се поддава на търсене.
Типичната реализация на двоичен куп е в масив. Поради форма на имота (структурата може да се разглежда като перфектна (илибинарното дърво), което означава, че връзката между родител и дете се представя косвено. Елементите се съхраняват в масива в широк-първи ред.
Както потребителят templatetypedef посочи в своятаОтговор, двоичен куп е специфичен вид двоично дърво и не бива да се бърка с двоично дърво за търсене, което е специално предназначено за бързо вмъкване и изтриване на елементи и локализиране на елементи по ключ.
Въпреки че промяната на приоритета на даден елемент в купчината или премахването на произволен елемент от купа, е много лесна, проблемът, който посочихте, е локализиране елемента, който ще се използва. В типичен двоичен куп, намирането на елемента, който ще бъде модифициран, изисква последователно търсене. Ако имате нужда от възможността да премествате елементи в купчината, обикновено бихте се оженили за двоичния файл с речник или хеш карта, която е индексирана от ключа на елемента. Стойността е индексът на елемента в масива. Този индекс се актуализира при всяко преместване на даден елемент. Това забавя операциите на купчината с постоянен фактор, но ви дава възможност да локализирате елемент в O (1).
Има и нещо, наречено a Мин-макс, което е тип двоичен куп, който ви дава достъп O (1) и до елемента min и max. Изпълнението е много подобно на прилагането на стандартна двоична мини купчина.
За да се объркат още повече, съществува и такаваd-aary heap, който е куп, който съдържа повече от две деца на възел. Например триканален куп има три деца на възел. Те също се изпълняват в масиви с неявни детски указатели.
Има и други структури от данни, които обикновено санаречени "купчини", но всъщност не са наистина свързани с купчината, с изключение на това, че те са "различни изпълнения на структурата за данни за приоритетната опашка. да се реализира с двоични дървета. (Отново не бинарни дървета за търсене.)
Аз написах донякъде направлявано въведение в двоичните купчини (и d-ary heaps) в моя блог преди няколко години. Ако се интересувате, проверете този запис, в който са изброени всички статии от тази поредица.
2 за отговор № 2
Мисля, че вие обърквате двоичните файлове Търсене дървета и двоични дървета. Двоичното дърво е по-скоро форма, отколкото нещо друго - това е дърво, където всеки възел има най-много две деца. Възлите не е задължително да имат стойности в тях, и ако го направят, няма изискване те да се подчиняват на определени правила.
Двоичен Търсене tree е двоично дърво, където всеки възел държи aи всеки възел се подчинява на правилото, че всички ключове в лявото поддърво са по-малко от ключа на възела и всички ключове в дясното поддърво са по-големи от ключа на възела. (Някои дефиниции отпускат изискването за допускане на по-малко от или равно на вместо вместо само по-малко от и т.н.)
Има много други структури от данни, изградени от двоични дървета, които не са BST. k-d Дървета съхраняват многомерни данни. Binary се опитва да съхранява низове от битове.
Така че мисля, че най-доброто описание тук е “двоично”купчини са двоични дървета, които са пълни и се подчиняват на свойствата на купчината, което не е същото като двоично дърво за търсене, въпреки че те имат една и съща основна форма (повече или по-малко). "