\(d\)-kopcem typu MIN, \( d \ge 2\), nazywamy zupełne drzewo \(d\)-arne z kluczami rozmieszczonymi w porządku kopcowym typu MIN.
Drzewem lewicowym nazywamy drzewo binarne, w którym dla każdego wierzchołka długość skrajnie prawej ścieżki w jego lewym poddrzewie jest nie mniejsza od długości skrajnie prawej ścieżki w jego prawym poddrzewie. Kopcem lewicowym typu MIN nazywamy drzewo lewicowe z kluczami rozmieszczonym w porządku kopcowym typu MIN.
Zaproponuj efektywne implementacje operacji kolejki priorytetowej (Build, Min, DeleteMin, DecraseKey) z użyciem kopców lewicowych.
Dana jest rodzina \(n\) niepustych podzbiorów zbioru \( \{1, 2, \ldots, n \}\), z których każdy to całkowitoliczbowy przedział postaci \([i,j]\), \(i \le j\). Zaprojektuj efektywny algorytm sprawdzania, czy zadana rodzina posiada system różnych reprezentantów, a jeśli tak, to podaje jeden z nich.
W algorytmie Dijkstry ciąg wartości otrzymywanych w wyniku wywołań funkcji Min jest niemalejący. Wykorzystaj ten fakt i zaproponuj implementację implementację algorytmu Dijkstry w czasie \( O(m + kn) \), gdy wagi krawędzi są liczbami całkowitym z przedziału \( [1..k ] \).
Dane jest drzewo z wyróżnionym wierzchołkiem \(s \) - źródłem rozgłaszania.