// Lista V // Kopce lewicowe // Kopiec (kolejka priorytetowa) jest trzecim rodzajem drzew, ktory spotkamy. // Aksjomatyczna definicja kopca to struktura, w ktorej dopuszczalne sa nastepujace operacje: // insert (wklada element do kopca) // findMin (znajduje minimum dotychczas wlozonych elementow) // deleteMin (usuwa minimum z kopca) // Oczywiscie mozemy zaadoptowac liste lub drzewo BST do obslugi operacji kopcowych, // ale takie implementacje beda malo wydajne. // W kilku kolejnych zadaniach zajmiemy sie implementacja kopcow lewicowych. // Kopce lewicowe to drzewa binarne, ktore spelniaja dwa warunki: // 1. elementy zachowuja porzadek kopca, tzn dzieci kazdego wierzcholka maja wiekszy priorytet od niego // 2. w kazdym wezle skrajnie prawa sciezka jest najkrotsza droga do liscia // 3. Lewy syn kazdego wierzcholka ma range co najmniej taka jak prawy syn (range definiujemy jako liczbe przejsc do prawego syna, ktore musimy wykonac by dojsc do liscia). // Powyzsze warunki gwarantuja, ze operacje kopcowe dzialaja w czasie O(log n), gdzie n jest liczba elementow. // priorytetem bedzie po prostu liczba naturalna type Priority = int // ranga rowniez jest liczba naturalna type Rank = int type Heap = | Empty // pusty kopiec | Node of Heap * Priority * Heap * Rank // wezel zawierajacy dwa drzewa, priorytet oraz informacje o randze // funkcja wypisujaca drzewo (taka jak poprzednie) // nie musisz jej czytac let print (tree:Heap) : unit = let rec print2 (pref:string) (tree:Heap) : unit = match tree with | Empty -> printfn "%s|" pref | Node (left, x, right, _) -> let spref = " " + pref print2 spref right printfn "%s%O" pref x print2 spref left print2 "" tree // pomocnicza funkcja obliczajaca range drzewa let rank (heap:Heap) : Rank = match heap with | Empty -> 0 // puste drzewo ma range 0 | Node(left, prio, right, r) -> r // wezel wewnetrzny przechowuje informacje o randze, ktora zwracamy // Zdefiniuj funkcje, ktora sprawdzi czy kopiec jest pusty let isEmpty (heap:Heap) : bool = failwith "Usun ten wiersz" // zdefiniuj funkcje, ktora zwroci element minimalny // jesli kopiec jest pusty, postaraj sie o sensowny komunikat o bledzie let findMin (heap:Heap) : Priority = failwith "Usun ten wiersz" // Zdefiniuj funkcje, ktora przyjmie jako argument priorytet oraz dwa kopce, a nastepnie polaczy to w jeden kopiec // nie sprawdzaj warunku kopca, zadbaj tylko o poprawne rangi let makeTree (p:Priority) (h1:Heap) (h2:Heap) : Heap = failwith "Usun ten wiersz" // Zdefiniuj funkcje, ktora laczy dwa kopce lewicowe. // precyzyjny opis laczenia drzew lewiowych mozna znalezc pod adresem // http://smurf.mimuw.edu.pl/wstep_do_programowania_funkcyjny?q=wstep_do_programowania_funkcyjny_lab_zad_1 let rec merge left right = failwith "Usun ten wiersz" // Wykorzystaj funkcje merge do wlozenia pojedynczego elementu do kopca let insert (heap:Heap) (p:Priority) : Heap = failwith "Usun ten wiersz" // wykorzystaj funkcje merge do usuniecia elementu minimalnego z kopca let deleteMin (heap:Heap) : Heap = failwith "Usun ten wiersz" // Funkcja pomocnicza przy sortowaniu let tryDelete (heap:Heap) = if isEmpty heap then None else let m = findMin heap let h = deleteMin heap Some (m, h) // utworz kopiec z listy let fromList lst = lst |> List.fold insert Empty // posortuj liste tworzac kopiec a nastepnie usuwajac z niego minima let heapSort lst = let heap = fromList lst List.unfold tryDelete heap // sprawdz wydajnosc sortowania let test2 n = let r = System.Random() let input = [1..n] |> List.map (fun _ -> r.Next() % n) let sw = System.Diagnostics.Stopwatch.StartNew() input |> heapSort |> ignore sw.Stop() printfn "%d elems. Total time:%O" n (sw.Elapsed.TotalSeconds)