Rozwiązanie wielu problemów zależy od możliwości szybkiego wybrania największego lub najmniejszego elementu ze zbioru, z którego elementy często są usuwane i do którego są wstawiane. Jednym ze sposobów rozwiązania tego problemu jest zachowanie uporządkowania zbioru, dzięki czemu element najmniejszy lub największy jest zawsze dostępny. Jednak stałe porządkowanie zbioru jest rozwiązaniem kosztownym, poza tym naszym celem nie jest trzymanie w kolejności wszystkich elementów, wobec czego robimy coś, co nie jest nam potrzebne. Lepszym rozwiązaniem jest zastosowanie stert.
Sterty (kopce) są to drzewa (zwykle binarne) zorganizowane tak, że można szybko pobrać węzeł o największej wartości. Koszty takiego rozwiązania są mniejsze od kosztów zachowywania uporządkowania danych. Każdy węzeł dziecko ma wartość mniejszą (lub równą) od rodzica. Węzeł główny ma wartość największą w całym drzewie.
Ograniczenie porządku kopcowego można nałożyć na każde drzewo, ale jest ono szczególnie wygodne w przypadku pełnego drzewa binarnego. Sterty są zrównoważone lewostronnie, czyli poziomy wypełniamy kolejno od lewej strony. Szczególnie dobrym sposobem zapisu stert jest zapisywanie ich w ciągłej tablicy. Przy założeniu, że tablica jest indeksowana od zera, rodzic elementu z pozycji i znajduje się na pozycji |_(i-1)/2_|, gdzie |_ _| oznacza część całkowitą. Lewe i prawe dziecko danego węzła znajdują się w miejscach (2i+1) i (2i+2). Jest to ważne przy naszej implementacji stert.
Interfejs sterty ma 4 funkcje: __init__(), is_empty(), insert(), remove(). Czasem dodaje się funkcję count(). Musimy umieć porównywać elementy wkładane na stertę.
Numeracja węzłów na stercie. Te numery są też indeksami do tablicy. poziom 1 | 0 .........| / \ poziom 2 | 1 2 .........| / \ / \ poziom 3 | 3 4 5 6 .........| / \ / \ / \ / \ poziom 4 | 7 8 9 10 11 12 13 14 .........| / \ / \ / \ / \ / \ / \ / \ / \ poziom 5 |15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30
Implementacja oparta jest na założeniu, że indeksy tablicy przechowującej elementy sterty są numerowane od zera. Na początku definiujemy funkcje, króre dla elementu o indeksie n obliczają odpowiednio: indeks rodzica (heap_parent), indeks lewego potomka (heap_left) i indeks prawego potomka (heap_right). Następnie definiujemy funkcje, które przywracają strukturę sterty, jeżeli zmienił się element o indeksie najmniejszym (fix_down) lub największym (fix_up). W końcu określamy klasę Heap z metodami wymaganymi dla stery.
def heap_parent(n):
return (n-1) // 2
def heap_left(n):
return (2*n+1)
def heap_right(n):
return (2*n+2)
def swap(L, left, right):
# L[left], L[right] = L[right], L[left]
item = L[left]
L[left] = L[right]
L[right] = item
# Naprawa kopca, gdy na pozycji ipos zwiększył się priorytet.
def fix_up(L, ipos):
ppos = heap_parent(ipos)
# tu widać, że korzeń ma nr 0
while (ipos > 0) and (L[ppos] < L[ipos]):
swap(L, ppos, ipos)
# przesunięcie węzła w górę
ipos = ppos
ppos = heap_parent(ipos)
# Naprawa kopca, gdy na pozycji ipos zmniejszył się priorytet.
def fix_down(L, ipos, n):
# n - rozmiar tablicy, nie możemy przekroczyć
# UWAGA indeksy tablicy są mniejsze od n
while True:
# wybór dziecka do zamiany z bieżącym węzłem
lpos = heap_left(ipos)
rpos = heap_right(ipos)
if lpos < n and L[lpos] > L[ipos]:
mpos = lpos
else:
mpos = ipos
if rpos < n and L[rpos] > L[mpos]:
mpos = rpos
if mpos == ipos:
break # drzewo to sterta
else: # trzeba zamienić z dzieckiem
swap(L, mpos, ipos)
# przesuwam węzeł o jeden poziom w dół
ipos = mpos
class Heap:
"""Implementacja sterty (kopca max)."""
def __init__(self):
self.items = [] # tu trzymamy elementy sterty
def __str__(self): # podglądamy stertę
return str(self.items)
def is_empty(self):
#return self.items == []
#return len(self.items) == 0
return not self.items
def insert(self, item): # nie zwraca wartości
self.items.append(item) # dodajemy na koniec tablicy
# ponowne przekształcenie drzewa w stertę
fix_up(self.items, len(self.items)-1)
def remove(self): # zwraca element największy
k = len(self.items)-1
# najpierw największy na koniec
swap(self.items, 0, k)
# trzeba poprawić drzewo, zaczynam od góry
# znowu widać, że zaczynam od korzenia nr 0
fix_down(self.items, 0, k)
return self.items.pop()
def count(self): # liczba elementów na stercie
return len(self.items)
Po zapisaniu kodu do osobnego modułu heap.py, możemy w dowolnym programie korzystać ze sterty.
import heap
aheap = heap.Heap()
for item in [5, 10, 20, 1, 25, 22, 9]:
aheap.insert(item)
# Zdejmowanie elementów ze sterty od największego do najmniejszego.
while not aheap.is_empty():
print(aheap.remove())
Jeżeli na stercie jest N elementów, to ścieżka od korzenia do najniższego poziomu ma około log(N) węzłów. Daje to dobrą wydajność kolejki priorytetowej zaimplementowanej za pomocą sterty. Operacja wstawiania elementu do sterty wymaga nie więcej niż log(N) porównań elementów. Operacja usuwania elementu maksymalnego wymaga nie więcej niż 2*log(N) porównań elementów.
Konstrukcja sterty o liczności N elementów zajmuje czas proporcjonalny do N*log(N) elementów w przypadku najgorszym, jeśli każdy nowy element jest największym, jaki dotąd pojawił się na stercie. W przypadku przeciętnym, gdy napływają losowo uporządkowane elementy, czas budowy kopca jest liniowy.
Algorytm sortowania przez kopcowanie (sortowanie stogowe) wykorzystuje strukturę danych zwaną kopcem. Jest to poprawione sortowanie przez wybór. Algorytm jest klasy O(N*log(N)) i jest niestabilny. Ważną zaletą algorytmu jest działanie w miejscu, czyli bez dodatkowej pamięci. Wykorzystujemy wcześniej zdefiniowane funkcje.
def heapsort(L):
"""Sortowanie listy przez kopcowanie."""
n = len(L)
# Najpierw budujmy pierwotny kopiec.
for k in range(heap_parent(n-1),-1,-1):
fix_down(L, k, n)
while n > 1: # pobieranie danych z kopca
L[0], L[n-1] = L[n-1], L[0] # swap(L, 0, n-1)
n = n - 1
fix_down(L, 0, n)
Konstrukcja wstępująca kopca ma liniową złożoność obliczeniową, ponieważ przetwarzane kopce są w większości małe.
Dla kopca o rozmiarze 7=2^3-1 mamy 2 kopce o rozmiarze 3 i jeden kopiec o rozmiarze 7. Maksymalna liczba promocji (porównań jest dwa razy więcej) wynosi 2*1+1*2=4.
| 0 | / \ | 1 2 | / \ / \ | 3 4 5 6
Dla kopca o rozmiarze 15=2^4-1 mamy 4 kopce o rozmiarze 3, dwa kopce o rozmiarze 7 i jeden kopiec o rozmiarze 15. Maksymalna liczba promocji (porównań jest dwa razy więcej) 4*1+2*2+1*3=11.
| 0 | / \ | 1 2 | / \ / \ | 3 4 5 6 | / \ / \ / \ / \ |7 8 9 10 11 12 13 14
Dla kopca o rozmiarze N=2^m-1 mamy oszacowanie liczby promocji
sum_{s=1}^{m-1} s*pow(2,m-1-s) = 2^m-m-1 < N.
Zachodzi twierdzenie [Sedgewick s.356], że algorytm sortowania przez kopcowanie do uporządkowania N elementów wymaga mniej niż 2*N*ln(N) porównań.
Jednym ze sposobów usprawnienia algorytmu sortowania przez kopcowanie jest zbudowanie kopca opartego na tablicowej reprezentacji pełnego drzewa trynarnego (trójkowego) uporządkowanego kopcowo.
Kopce nadają się do rozwiązywania problemów selekcji, czyli wybierania k największych elementów spośród N elementów, szczególnie dla małych k. Wystarczy zatrzymać algorytm sortowania przez kopcowanie po wybraniu z kopca k elementów.
import heapq
import random
H = [] # creates an empty heap
for item in [0, 2, 6, 5, 1, 4, 3]:
heapq.heappush(H, item) # pushes a new item on the heap
# item = heapq.heappop(H) # pops the smallest item from the heap
# item = H[0] # smallest item on the heap without popping it
# item1 = heapq.heapreplace(H, item2)
# pops and returns smallest item1, and adds new item2;
# the heap size is unchanged
# Można wystartować z niepustej listy.
L = list(range(7))
random.shuffle(L)
heapq.heapify(L) # linear time, in-place
# Ciekawe, ze po L.sort() jest poprawna sterta.
# heapq.merge(*iterables, key=None, reverse=False) - zwraca generator
# Łączenie posortowanych list (iterables) w jedną listę.
list(heapq.merge([1,3,5,7], [0,2,4,8], [5,10,15,20], [], [25]))
# [0, 1, 2, 3, 4, 5, 5, 7, 8, 10, 15, 20, 25]
list(heapq.merge(['dog', 'horse'], ['cat', 'fish', 'kangaroo'], key=len))
# ['dog', 'cat', 'fish', 'horse', 'kangaroo']
# heapq.nlargest(n, iterable, key=None)
# Znajduje n największych elementów w iterable.
# Równoważne:
# sorted(iterable, key=key, reverse=True)[:n]
# heapq.nsmallest(n, iterable, key=None)
# Znajduje n najmniejszych elementów w iterable.
# Równoważne:
# sorted(iterable, key=key)[:n]
def heapsort(L):
heapq.heapify(L) # mamy kopiec
M = []
while L: # pobieranie danych z kopca
M.append(heapq.heappop(L))
return M