Хамгийн бага тоог үргэлж root дээрээ барьж, тоо нэмэх ба гаргахыг O(log n) хугацаанд хийдэг tree.

Pre-IntermediateХугацаа: O(log n) нэг үйлдэлдСанах ой: O(n)
HackerRank дээр бодох

Эхлээд жижиг бодлого

Хоосон heap-д 7, 3, 9, 1, 5 тоог нэмээд хамгийн багыг гаргая. Дараа нь 4-ийг нэмээд дахин хамгийн багыг гаргана.

Эхний удаа 1, хоёр дахь удаа 3 хэвлэгдэнэ. Хариу: 1 3.

Энгийн аргаас санаа руу

Энгийн арга: тоонуудыг энгийн array-д хадгалаад, хамгийн багыг хайхдаа бүгдийг шалгана. Нэмэх O(1), гаргах O(n). 10⁵ үйлдэлд 10¹⁰ алхам хүрч болно.

Гол санаа: тоонуудыг бүтэн binary tree хэлбэрээр байрлуулж, parent бүр child-уудаасаа бага байх дүрэм баримтална. Хамгийн бага нь root дээр байна. Нэмэх, гаргах үед дүрэм зөвхөн нэг path дагуу эвдэрдэг тул тэр path-ыг л засна. Tree-ийн өндөр log n.

Нэр томьёо ба тэмдэглэгээ

h[1..sz]
Heap-ийг хадгалах array. Index нь 1-ээс эхэлнэ.
parent, child
h[i]-н parent нь h[i / 2], child-ууд нь h[2i], h[2i + 1].
sift up
Шинэ тоо parent-ээсээ бага л бол байраа сольж дээшлэх.
sift down
Root дээр гарсан тоо бага child-тайгаа байраа сольж доошлох.
sz = 0

Min-heap дотор parent бүр child-уудаасаа бага буюу тэнцүү. Тиймээс хамгийн бага тоо үргэлж root буюу h[1] дээр байна. Дээр нь tree, доор нь яг тэр тоонууд array хэлбэрээр харагдана.

Алхам 1 / 18
Хурд
  • Шинэ эсвэл хөдөлсөн тоо
  • Солигдсон хос
  • Хамгийн бага тоо
Слайд 1 / 6

Хамгийн багыг шууд

Тоо нэмэх, хамгийн багыг нь гаргах ажил олон бодлогод гардаг. Жишээ нь Dijkstra. Binary Heap хоёуланг нь O(log n) хугацаанд хийдэг. C++-ийн priority_queue яг ийм бүтэц.

binary-heap.cpp
#include <bits/stdc++.h>
using namespace std;
int q, sz, h[100005];
int main() {
cin >> q;
while (q--) {
int type;
cin >> type;
if (type == 1) {
int x;
cin >> x;
h[++sz] = x;
int i = sz;
while (i > 1 && h[i / 2] > h[i]) {
swap(h[i], h[i / 2]);
i /= 2;
}
} else {
cout << h[1] << '\n';
h[1] = h[sz--];
int i = 1;
while (2 * i <= sz) {
int c = 2 * i;
if (c + 1 <= sz && h[c + 1] < h[c]) c++;
if (h[i] <= h[c]) break;
swap(h[i], h[c]);
i = c;
}
}
}
return 0;
}

Юунд хэрэгтэй вэ?

Тоо нэмэх, хамгийн багыг нь авах үйлдэл холилдон олон ирэхэд хоёуланг нь хурдан хийнэ. C++-ийн priority_queue яг ийм бүтэц. Dijkstra, Prim, Huffman зэрэг алгоритмд хэрэглэгдэнэ.

Яаж ажилладаг вэ?

1. Heap бол бүтэн binary tree бөгөөд array-д хадгалагдана: h[i]-н child-ууд нь h[2i], h[2i + 1], parent нь h[i / 2]. 2. Дүрэм: parent бүр child-уудаасаа бага буюу тэнцүү. Тиймээс хамгийн бага тоо h[1] дээр байна. 3. Нэмэх: шинэ тоог төгсгөлд тавиад, parent-ээсээ бага л бол байраа сольж дээшилнэ. 4. Гаргах: h[1]-ийг авч, сүүлийн тоог root дээр зөөнө. Дараа нь хоёр child-ын бага нь өөрөөсөө бага л бол түүнтэй байраа сольж доошилно. Оролт: эхний мөрөнд q, дараа нь q мөр. "1 x" бол x-ийг нэмнэ, "2" бол хамгийн багыг хэвлээд гаргана.

Яагаад зөв, хэр хурдан бэ?

Нэмэх үед дүрэм зөвхөн шинэ тоо ба түүний parent хоёрын хооронд эвдэрч болно. Солих бүрт эвдрэл нэг давхар дээш шилжиж, root-д хүрэх эсвэл parent бага болоход дуусна. Гаргах үед root дээр гарсан тоо бага child-тайгаа солигдох бүрт эвдрэл нэг давхар доош шилжинэ.

Tree-ийн өндөр log₂ n тул нэмэх, гаргах тус бүр O(log n), хамгийн бага тоог харах O(1). n = 10⁵ үед үйлдэл бүр 17 орчим алхам.

Түгээмэл алдаа

  • Index 0-ээс эхлүүлэх. Тэгвэл child-ууд нь 2i + 1, 2i + 2, parent нь (i - 1) / 2 болно. Хоёр томьёог холихгүй бай.
  • Доош явуулахдаа хоёр child-ын багыг сонгохгүй байх. Том child-тай солибол дүрэм эвдэрнэ.
  • c + 1 <= sz шалгалтыг мартах. Тэгвэл байхгүй child-ыг уншина.
  • Хоосон heap-ээс гаргах. Гаргахын өмнө sz > 0 эсэхийг шалга.
  • C++-ийн priority_queue анхдагчаар хамгийн их тоог өгдөг. Хамгийн бага хэрэгтэй бол priority_queue<int, vector<int>, greater<int>>.

Хязгаарын тохиолдол

  • Ганц тоо: гаргахад heap хоосон болж, доош явуулах loop огт эргэхгүй.
  • Ижил тоонууд: h[i / 2] > h[i] хатуу харьцуулалт тул тэнцүү үед солихгүй.
  • Өсөх дарааллаар нэмэх: нэг ч солилт хийхгүй.
  • Буурах дарааллаар нэмэх: шинэ тоо бүр root хүртэл явна.

Өөрийгөө шалга

  1. h[5]-ын parent хэд дэх index вэ?

    Хариу харах

    2. 5 / 2 = 2.

  2. 1, 2, 3 гэж нэмбэл h array ямар болох вэ?

    Хариу харах

    [1, 2, 3]. Нэг ч солилт хийгдэхгүй.

  3. 7 тоотой heap хэдэн давхар вэ?

    Хариу харах

    3 давхар: 1 + 2 + 4 = 7.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.Хоосон heap-д 5, 8, 2, 9, 1 тоог нэмэхэд алхам бүрийн дараах h-ийг бич.

    Hint харах

    Шинэ тоо бүрийг сүүлд тавиад parent-тэй нь харьцуул.

    Хариу ба тайлбар

    [5], [5, 8], [2, 8, 5], [2, 8, 5, 9], [1, 2, 5, 9, 8].

  2. 2.Кодыг max-heap болго, өөрөөр хэлбэл root дээр хамгийн их тоо байдаг болго.

    Hint харах

    Гурван харьцуулалтыг эргүүлнэ.

    Хариу ба тайлбар

    h[i / 2] < h[i] бол дээшилнэ. h[c + 1] > h[c] бол баруун child-ыг сонгоно. h[i] >= h[c] бол зогсоно.

  3. 3.n тоог heap ашиглан O(n log n) хугацаанд эрэмбэл.

    Hint харах

    Бүгдийг нэмээд, дараа нь n удаа гаргана.

    Хариу ба тайлбар

    Бүх тоог нэмээд n удаа хамгийн багыг гаргаж хэвлэнэ. Гарах дараалал өсөх эрэмбэтэй. Үүнийг Heap Sort гэдэг.

Жишээ

Оролт

8
1 7
1 3
1 9
1 1
1 5
2
1 4
2

Гаралт

1
3

Одоо өөрөө бодоод үз

Бодлого

Хичээл

Энэ сэдвийн хичээл удахгүй нэмэгдэнэ.