Advertisement
exnon

Heapfinal_sami

Dec 9th, 2020
3,943
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Erlang 2.97 KB | None | 0 0
  1. -module(heapsortCarl).
  2. -export([hsort/1]).
  3. % Kodierung des Feldes: Nachfolger von Position i ist 2*i links und 2*i+1 rechts
  4. % berechnet den Pfad zur ersten leeren Position
  5. % l steht fuer links, r fuer rechts
  6. % Beispiel: sort:calcPath(1). --> []
  7. %       sort:calcPath(2). --> [l]
  8. %       sort:calcPath(3). --> [r]
  9. %       sort:calcPath(4). --> [l,l]
  10. %       sort:calcPath(5). --> [l,r]
  11. %       sort:calcPath(6). --> [r,l]
  12. %       sort:calcPath(7). --> [r,r]
  13. calcPath(Number) -> calcPath(Number,[]).
  14. % aktuelle Position ist Wurzel
  15. calcPath(1,Accu) -> Accu;
  16. % aktuelle Position ist gerade
  17. calcPath(Number,Accu) when Number rem 2 =:= 0 -> calcPath(Number div 2,[l|Accu]);
  18. % aktuelle Position ist ungerade
  19. calcPath(Number,Accu) when Number rem 2 =/= 0 -> calcPath((Number-1) div 2,[r|Accu]).  
  20.  
  21. hsort(Liste) ->
  22.     {Heap, N} = createHeap(Liste),
  23.     createList(Heap, N+1).
  24.  
  25.  
  26. createList({}, _N)
  27. ->[];
  28. createList(Heap={Z, _L, _R}, N)
  29. -> HeapNeu = removeMin(Heap, calcPath(N-1)), createList(HeapNeu, N-1)++[Z].
  30.  
  31.    
  32. createHeap(Liste=[H|T]) ->
  33.     Heap = {H, {}, {}},
  34.     createHeap(Heap, T, 1).
  35.  
  36. createHeap(Heap, [], N) -> {Heap, N};
  37.  
  38. createHeap(Heap, Liste=[H|T], N) ->
  39.     NewHeap = insertHeap(Heap, H,calcPath(N+1)),
  40.     createHeap(NewHeap, T, N+1).
  41. % 4 8 3 9 6
  42. %insertHeap({}, E,[]) -> {E,{}, {}};
  43. insertHeap(Heap={Zh, L, R}, E, Steps = [l|[]]) when E > Zh ->
  44.     {E, Lneu={Zh, {},{} }, {}};
  45. insertHeap(Heap={Zh, L, R}, E, Steps = [r|[]]) when E > Zh ->
  46.     {E, L, {Rneu=Zh,{},{}}};
  47.    
  48. insertHeap(Heap={Zh, L, R}, E, Steps = [l|[]]) when E =< Zh ->
  49.     {Zh, Lneu={E, {},{} }, {}};
  50. insertHeap(Heap={Zh, L, R}, E, Steps = [r|[]]) when E =< Zh ->
  51.     {Zh, L, {Rneu=E,{},{}}};
  52.    
  53. insertHeap(Heap={Zh, L, R}, E, Steps = [l|T]) when E > Zh ->
  54.     {E, insertHeap(L,Zh, T), R};
  55. insertHeap(Heap={Zh, L, R}, E, Steps = [r|T]) when E > Zh ->
  56.     {E, L, insertHeap(R,Zh, T)};    
  57.  
  58. insertHeap(Heap={Zh, L, R}, E, Steps = [l|T]) when E =< Zh ->
  59.     {Zh, insertHeap(L,E, T), R};
  60. insertHeap(Heap={Zh, L, R}, E, Steps = [r|T]) when E =< Zh ->
  61.     {Zh, L, insertHeap(R,E, T)}.
  62.  
  63. peekLast(_Heap={Z, L, R}, [r | []])
  64. -> {E, _, _ } = R,
  65.    {{Z, L, {}}, E};
  66. peekLast(_Heap={Z, L, _R}, [l | []])
  67. -> {E, _, _ } = L,
  68.    {{Z, {}, {}}, E};
  69. peekLast(_Heap={Z, L, R}, [l | Schritte])
  70. -> {Lneu, E} = peekLast(L, Schritte),
  71.    {{Z, Lneu, R}, E};
  72. peekLast(_Heap={Z, L, R}, [r | Schritte])
  73. -> {Rneu, E} = peekLast(R, Schritte),
  74.    {{Z, L, Rneu}, E}.
  75.  
  76. removeMin(_Heap={_Z, {}, {}}, [])
  77. -> {};
  78. removeMin(Heap={_Z, _L ,_R}, Schritte)
  79. -> {{_Zneu, Lneu, Rneu}, E} = peekLast(Heap, Schritte),
  80.    toHeap ({E, Lneu, Rneu}).
  81.  
  82. toHeap(_Heap={Z, _L={LZ, _, _}, {} }) when LZ>Z
  83. -> {LZ, {Z, {}, {}}, {}};
  84.  
  85. toHeap(_Heap={Z, L={LZ, _LL, _LR}, _R={RZ, RL, RR}}) when RZ>LZ, RZ>Z
  86. -> {RZ, L, toHeap({Z, RL, RR})};
  87.  
  88. toHeap(_Heap={Z, _L={LZ, LL, LR}, R={RZ, _RL, _RR}}) when LZ>RZ, LZ>Z %links ist am grossten
  89. -> {LZ, toHeap({Z, LL, LR}), R};
  90.  
  91. toHeap(Heap) %%ende, Z ist am grossten
  92. -> Heap.
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement