Struktury danycheasy

Na czym polega własność kopca (heap property) w kopcu binarnym?

Tagi

#heap#binary-heap#priority-queue#big-o

Odpowiedź

W min-heap każdy węzeł jest ≤ swoich dzieci (najmniejszy element jest w korzeniu). W max-heap każdy węzeł jest ≥ swoich dzieci. Dzięki temu peek jest O(1), a insert/remove O(log n).

Powiązane pytania

Struktury danych

Kopiec binarny vs drzewo BST: które operacje są wydajne?

#heap#bst#priority-queue

Struktury danych

Co to jest segment tree i jaką złożoność daje dla zapytań i aktualizacji zakresowych?

#segment-tree#range-query#updates

Struktury danych

Jakie operacje wspiera kolejka priorytetowa i jak jest zwykle zaimplementowana?

#priority-queue#heap#ordering

Struktury danych

Budowanie kopca z tablicy: dlaczego może być O(n), a nie O(n log n)?

#heap#heapify#complexity

Struktury danych

Dlaczego resize tablicy haszującej może powodować skoki latencji i jak temu zapobiegać?

#hash-table#rehash#latency

Struktury danych

Co to jest sparse table i do jakich problemów się nadaje?

#sparse-table#rmq#preprocessing