Min heap-г өөрсдөө бичих - C++

Өмнө нь priority queue-н талаар болон queue, vector-г хэрхэн өөрсдөө бичих тухай ярьсан билээ. Одоо priority queue буюу min heap бүтцийн тухай дэлгэрэнгүй бичье. Эргэн санавал энэхүү өгөгдлийн бүтэц нь үндсэн 4 үйлдэлтэй ба:

• size() - heap-н хэмжээг буцаах
• front() - хамгийн бага элементийг буцаах
• pop() - хамгийн бага элементийг устгах
• push(element) - heap-д элемент нэмэх

Үүнийг хэрхэн бичих вэ? Бид зүгээр л энгийн array ашиглаад хийж болох уу? Хэрвээ энгийн array-с хамгийн багыг нь олоод устгах үед дараагийн хамгийн багыг нь олоод явна гэвэл O(N) үйлдэл устгах бүртээ хийж таарах ба энэ нь ашиггүй. Учир нь heap дээр pop, push() үйлдлийг O(logN)-үйлдлээр хийдэг ба front()-г O(1) үйлдлээр хийдгээрээ давуу.

Гол санаа

Заа тэгэхээр зүгээр л энгийн array ашиглаад дараагийн багыг O(N)-д олдгоор хийж болохгүй байх нь. Хэрвээ array-г эрэмбэлсэн гэж үзвэл дараагийн багыг шууд олно. Тэгээд эрэмбэлэгдсэн тул элемент нэмэхэд бид хаана нэмэх вэ гэдгийг хоёртын хайлт ашиглаад олж болно. Гэхдээ array-н дунд элемент нэмэхийн тулд бид зарим элементийг хойшлуулах тул энэ нь өөрөө O(N) болно. Тиймээс энэ санаа бүтэхгүй байх нь.

Өмнө нь граф-н тухай бичиж байсан ба энэ удаа модны тухай ярьцгаая. Мод цикл агуулаагүй граф бөгөө нэг оройгоос гараад өөрдээрээ дуусах зам олддог бол түүнийг цикл гэнэ. Тэгхээр энэхүү мод бүтцийг яаж ашиглах вэ? Бид мөн rooted tree-н тухай ярих болно. Энэ нь нэг оройгоос унжуулсан гэж төсөөлж болно.

Одоо rooted tree байгаа гэж үзээд тэр мод нь 2 энгийн дүрэмтэй байдаг гэе

• Ямар ч оройг сонгосон түүний хүүхдүүдийнх нь утга тухайн оройн утгаас их байдаг
• Ямар ч орой хамгийн ихдээ 2 хүүхэдтэй байж болно. (2тын мод гэдэг)

Энэхүү дүрмийг барьснаар нэмэх болон хасах үйлдэл хялбар болох боломжтой. Жишээ нь хамгийн бага гэдэг бол манай модны язгуур буюу root оройн утга байна. Энэхүү бүтцийг ашигтай болгож байгаа зүйл нь тухайн мод нь balanced буюу жигд өндөртэй байх юм. Ингэснээр модны өндөр нь log(N) болно. Жишээ модыг доорх зурагт харуулав

Энэхүү мод бүтцийг яаж санах ойд дүрслэх вэ? Бид энгийн array ашиглаж болох ба үүний i-р оройн зүүн хүүхэд нь (i+2 + 1)-р элемент, баруун хүүхэд нь i*2 + 2-р элемент гэж дүрслээд хамгийн дээд оройг 0-р элементээр дүрлий. Жишээ зургийг доор харуулав

Модонд элемент нэмэх

Энэхүү модонд элемент нэмэхдээ дараах дүрмийн дагуу нэмнэ

• Модны байх боломжтой сүүлийн навч болгож нэмнэ. (өндрийг хадгалах)
• Heapify Up: Тухайн сүүлд нэмэгдсэн оройг эцэг оройн утгатай шалгах ба хэрвээ бага байдаг бол эцэгтэй нь солино. Энэхүү үйлдлийг хамгийн дээр очих эсвэл биелэхгүй нөхцөл хүртэл хийнэ. Ингэснээр бидний модны 1-р дүрэм биелсээр байх болно.

Энэ 2 дүрэм нь модыг тэнцвэртэй болон дүрмийг дагаснаар үүснэ. Үүний дагуу жишээ модонд 2 гэсэн утгыг нэмснийг зургаар харуулав

Модноос багыг устгах

Энэхүү модноос хамгийн бага буюу дээд элементийг устгахдаа дараах дүрмийн дагуу устгана

• Хамгийн сүүлийн оройтой эхний оройг солино
• Хамгийн сүүлийн оройг устгана (энэ нь хуучин хамгийн эхний орой)
• Heapify Down: Одоо хамгийн дээр байх оройг өөрөөс нь бага байх 2 хүүхдийн багатай нь солино. Энэхүү үйлдлийг тухайн нөхцөл биелэхгүй болтол хийнэ. Ингэснээр модны 1-р дүрэм биелсээр байх болно

Энэ дүрмийн дагуу хамгийн багыг устгасан жишээг доор харуулав

Хэрэгжүүлэлт

Хэрхэн үүнийг бичих талаар гэвэл heap-н бүтцийг тодорхойлъё. Бидэнд утгыг хадгалах vector болон хэмжээг хадгалах утга байхад болно

class MinHeap {
private:
    vector<int> a; // модны утгуудыг хадгална
    int s; // модны хэмжээ
}

Элемэнт нэмэхдээ

void push(int x) {
    a.push_back(x); // хамгийн ард нэмнэ
    int index = s; // одоо байгаа оройн дугаар
    s++; // // хэмжээг шинэчлээнэ
    while(index && a[parent(index)] > a[index]) { // хэрвээ эцгийн утгаасаа бага байдаг бол
        swap(a[index], a[parent(index)]); // тухайн эцэгтэй нь солино
        index = parent(index); // тухайн оройн дугаарыг шинэчлэнэ
    }
}

Элемент хасахдаа

void pop() {
    if(s == 0) return;
    a[0] = a[s-1]; // хамгийн дээд утгыг солино
    a.pop_back(); // хамгийн сүүлийн элемэнтийг хасна
    s--; // хэмжээг шинэчлэлэнэ
    int index = 0;
    while(left_child(index) < s) {
        // тухайн оройн хүүхдүүдээс багыг нь олно
        int min_index = left_child(index);
        if(right_child(index) < s && a[min_index] > a[right_child(index)]) {
            min_index = right_child(index);
        }

        if(a[min_index] >= a[index]) break; // хэрвээ бага нь одоо байгаа утгаас их бол солих шаардлагагүй
        swap(a[index], a[min_index]); // багатай нь тухайн оройг солино
        index = min_index; // дугаарыг өөрчилнө
    }
}

Дүгнэлт

Энэ удаа min-heap буюу priority queue-г хэрхэн бичигдсэн талаар бичлээ. Энэхүү өгөгдлийн бүтэц нь олон зүйлээр ашиглагддаг. Энэхүү бүтцийг бий болгож буй 2тын мод болон тухайн мод дээр доторхойлсон дүрэм нь ашигтай болгож байгааг харж болно. 2тын модыг тэгш хэмтэй үүсгэснээр модны өндөр нь 2н логрифм суурьтай болж байгаа ба ингэснээр устгах нэмэх үйлдлүүдийг log(N) үйлдлээр хийх боломжтой болгож байна. Харин бидний тодорхойлсон дүрэм нь нэмэх болон хасахад хялбар болгож байгааг харж болно.