Біріктірілген үйінді - Mergeable heap

Жылы Информатика, а біріктірілетін үйінді (а деп те аталады жиналатын үйінді) болып табылады деректердің дерексіз түрі, бұл а үйінді біріктіру операциясын қолдау.

Анықтама

Біріктірілетін үйме кәдімгі үйінді операцияларын қолдайды:[1]

  • Үйме (), бос үйінді жасау.
  • Кірістіру (H, x), элементті салыңыз х үйіндіге H.
  • Мин (H), минималды элементті қайтарыңыз немесе Жоқ егер мұндай элемент болмаса.
  • Сығынды-мин (H), шығарыңыз және минималды элементті қайтарыңыз немесе Жоқ егер мұндай элемент болмаса.

Мұны ерекшелейтін тағы бір нәрсе:[1]

  • Біріктіру (H1, H2), элементтерін біріктіру H1 және H2 бір үйіндіге.

Ұсақ-түйек іске асыру

Қарапайым үйіндімен біріктірілетін үйінді жүзеге асыру өте қарапайым:

Біріктіру (H1, H2):

  1. х ← Сығынды-Мин (H2)
  2. уақыт x ≠ жоқ
    1. Кірістіру (H1, x)
    2. х ← Сығынды-Мин (H2)

Бұл әрқайсысы үшін ысырап етуі мүмкін Сығынды-мин (H) және Кірістіру (H, x) әдетте сақтау керек үйінді мүлік.

Іске асырудың тиімділігі

Біріктірілген үйінді деректер құрылымының мысалдары:

Өнімділікті салыстырумен толық тізімді мына жерден табуға болады Үйме (мәліметтер құрылымы) § Нұсқалардың теориялық шекараларын салыстыру.

Біріктірілетін үйінді құрылымдардың көпшілігінде біріктіру басқаларға негізделген негізгі операция болып табылады. Кірістіру жаңа бір элементті үйінді бар үйіндімен біріктіру арқылы жүзеге асырылады. Жою жойылған түйіннің балаларын біріктіру арқылы жүзеге асырылады.

Сондай-ақ қараңыз

Әдебиеттер тізімі

  1. ^ а б Кормен, Томас Х.; Лейзерсон, Чарльз Э.; Ривест, Рональд Л.; Штайн, Клиффорд (2009) [1990]. Алгоритмдерге кіріспе (3-ші басылым). MIT Press және McGraw-Hill. 505–506 бет. ISBN  0-262-03384-4.