Kopiec (binarny)

30.11.2009 - Michał Karpiński
Trudność

Kopiec jest to tablicowa struktura danych mająca duże znaczenie w algorytmice, jako że jest podstawą dla bardziej skomplikowanych obiektów. Jeśli chcesz bliżej poznać tą przypominającą drzewo strukturę, to niniejszy artykuł jest dla Ciebie.

Kopiec posiada bardzo przydatną własność – jego największy (lub najmniejszy) element znajduje się zawsze w korzeniu drzewa dzięki czemu odczytanie największej (lub najmniejszej) wartości jest wykonywalne w jednym kroku. Aby zrozumieć znaczenie kopców w algorytmice posłużę się krótką historyjką.

W firmie kurierskiej Bajt-Express główną zasadą jest jak najszybsze dostarczenie przesyłek do wyznaczonego celu. Każda z paczek posiada swój termin ważności, czyli do kiedy najpóźniej ma znaleźć się w rękach adresata. Ponadto paczki dostarczane są pojedynczo – kiedy jedna jest w drodze, cała reszta czeka w magazynie.

Nie trudno jest się domyśleć, że jako pierwszą paczkę najbardziej opłaca się wysłać tę, która najwcześniej traci swój termin ważności. Prezes firmy chce jak za każdym razem jak najefektywniej wyszukiwać taką paczkę ze sterty wszystkich paczek znajdujących się w magazynie, dlatego zatrudnił znanego informatyka Witka, aby pomógł mu rozwiązać to zadanie.

Pierwszy pomysł Witka jest bardzo prosty. Wystarczy zapisać wszystkie terminy ważności w tablicy jednowymiarowej. Pierwszą paczkę do wysyłki można znaleźć przeszukując tą tablicę od lewej do prawej. Po takim przeglądzie Witek na pewno natknie się na najmniejszy element.

W pierwszej metodzie mówimy, że wyszukanie najmniejszego elementu wykona się w czasie O(n), gdzie n jest wielkością tablicy. Więcej o notacji O znajdziesz tutaj.

Ta metoda tylko pozornie wydaje się być skuteczna. Witek nie przewidział, że jednego dnia z magazynu wysyłanych jest aż 4 294 967 296 paczek (2 do potęgi 32). Jakby musiał dla każdej nowej wysyłki przejrzeć całą tablicę, to zabrało by mu to mnóstwo czasu.

Na szczęście Witek nie poddał się tak łatwo i natychmiast wymyślił nowy sposób na rozwiązanie zadania. Tym razem postanowił, że będzie tworzył tablicę tak, żeby najmniejszy element znajdował się na samym początku. Nie istotnym jest w jaki sposób posortował wszystkie paczki. Ważny jest fakt, że teraz wszystkie paczki posortowane są od tej, która najwcześniej traci swój termin ważności do tej, która traci swój termin najpóźniej.

W tym momencie czekało na Witka kolejne rozczarowanie. Co prawda mógł bez problemu wybrać paczkę, która miała być aktualnie wysłana, ale ilość paczek do wysyłki nie pozostawała bez zmian. Co chwile nowe paczki trafiały do magazynu, więc żeby dołączyć je do tablicy należało spisać ponownie cała tablicę wprowadzając przy okazji odpowiednie zmiany. Takie podejście zbyt wiele kosztuje.

Witek wiedział, że musi istnieć metoda, która łączy w sobie zalety dwóch przedstawionych powyżej, więc zadał sobie pytanie:

Czy istnieje taka struktura danych, w której łatwo można osiagnąć dostęp do najmniejszego elementu i przy okazji niskim kosztem dołączać do niej nowe elementy ?

Odpowiedź chyba nikogo nie zaskoczy: TAK. Taką strukturą danych jest KOPIEC!

5
Twoja ocena: Brak Ocena: 5 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com