Үймеге жаңа элемент қосу

                    Үймеге жаңа элемент қосу

Ең бірінші біз үйме дегеніміз не? Оған не жатады? Оны қайда қолдануға болады деген сұрақтарға жауап бере кетейік.

Үйме (ағылш. heap) - ағаштарға негізделген қарапайым мәліметтер құрылымының бірі. Үйме бізге көптеген элементтірдің максимум мен минимум мәндерін тез табуға көмектеседі.

Классикалық үйме келесі әрекеттерді қолдайды:

Элемент қосу (қиындық: О(logN))

Максимумды табыңыз(қиындық: O(1))

Максималды элементті шығарыңыз(қиындық: O(logN))

Үйіндідегі элементтер толық екілік ағаш түрінде сақталады. Оның негізгі қасиеті (үйінді инварианты) келесідей тұжырымдалған:

әр шыңдағы элемент барлық еншілес шыңдардағы элементтерден үлкен немесе оған тең.

Бұл қасиеттен минималды элемент әрқашан ағаштың түбінде болады деген тұжырымға келуге болады

[pic 1]

Үйіндіге жаңа элемент қосылған кезде оған бірінші қол жетімді индекс тағайындалады. Яғни, екілік ағаш солдан оңға қарай деңгейлер бойынша толтырылады. Элементті қосқаннан кейін, үйінді инварианты жұмысын тоқтатуы мүмкін, өйткені жаңа элемент өзінің тікелей ата-бабасынан үлкен болады. Мұндай жағдайларда біз элементті тікелей ата-бабасы бар жерлерде өзгертеміз. Егер үйінді инварианты әлі орындалмаса, үйінді қалыпқа келгенше оны жаңа ата-бабамен ауыстырыңыз. Мұндай операция жоғары итеру деп аталады.

Максималды элементті алу кезінде біз келесі трюкті қолданамыз: үйіндідегі соңғы элементті (соңғы деңгейдегі оң жақ) ағаштың тамырына алыстағы максимумның орнына жылжытыңыз. Бұл инвариантты бұзады, өйткені жаңа "максимум" еншілес шыңдардағы элементтерден аз болады. Біз екі баланы салыстырамыз, олардың үлкенін таңдап, оны ағымдағы "максимуммен"ауыстырамыз. Инвариант қалпына келгенше осы әрекетті қайталаңыз. Мұны төмен итеру деп атайды.

Жалпы сіздерге түсініктірек болу үшін екілік үйме(ағаш) терминін қарастырайық.

Үйме - бұл үйінді қасиетін қанағаттандыратын толық екілік ағаш: Егер А түйіні В түйінінің ата-анасы болса, онда А түйінінің кілті ≥ В түйінінің кілті.

Егер кез-келген түйін әрқашан баланың түйінінен (түйіндерінен) үлкен болса, ал түбірлік түйіннің кілті барлық басқа түйіндердің ішіндегі ең үлкені болса, онда бұл максимум үйме.

Егер кез-келген түйін әрқашан баланың түйінінен (түйіндерінен) кіші болса, ал түбірлік түйіннің кілті барлық басқа түйіндердің ішіндегі ең кішісі болса, онда бұл минимум үйме.

[pic 2]

Бізге үймемен жұмыс жасау барысында біршақты операциялар қажет. Бұл операцияларға мыналар жатады:

make_heap () элементтер ауқымын үйіндіге айналдырады.

push_heap () үйіндіге бір элемент қосады.

pop_heap () үйіндіден келесі элементті жояды.

sort_heap () үйіндіні сұрыпталған коллекцияға айналдырады, содан кейін үйінді енді үйінді емес.

is_cheap () элементтер ауқымы үйінді екенін тексереді.

Жалпы бізге үймеге жаңа элемент қоспай тұрып үйменің өзің құрып алу қажет.

Heapify - екілік ағаштан үйінді жасау әдісі. Ол min үймесін немесе max үймесін жасау үшін қолданылады.