Heap - performante sortierte Datenstruktur

    • VB.NET

      Heap - performante sortierte Datenstruktur

      Heap als Baum
      Ein binärer Heap ist eine sortierte, balancierte binäre Baumstruktur, die in einem Array angelegt wird.
      Dabei besteht keine explizite Verknüpfung zwischen einem Parent-Node und seinen beiden Children, sondern auf die Children wird einfach über ihre Position im Array zugegriffen:
      Die beiden Children eines Parent-Nodes liegen immer genau hinter dem doppelten Index des Parents.
      Daher braucht ein Parent-Node keine extra Children-Property oder sowas, sondern man kann einfach den Parent-Index verdoppeln, und dahinter liegen seine beiden Children.

      Oooh - jetzt habichmich so verkünstelt...
      ... Heap zu erklären, und dann finde ich den englischen Wiki-Artikel ;(
      Und dort wird auch noch verlinkt, auf eine gscheite Animation. ;( ;(
      Worauf ich noch hinweise ist das Collections.Generic.SortedSet(Of T), mit dem man teilweise auch Anforderungen einer PrioritätenListe abdecken kann. ;( ;( ;(

      Das einzige an meinem Rad noch besonders Runde ist die Besonderheit, dassich auf unnötige Tausch-Operationen verzichte (simmerhier bei BubbleSort oderwas?).
      Bei mir wird nicht geswapt - sondern einfach "aufgerückt": Denn was soll man den leeren Platz jedesmal ausfüllen, wenner inne nächsten Iteration doch wieder überschrieben wird?


      Heap-Bedingung
      Ein Heap ist balanciert, wenn für jeden (Parent-)Node gilt: beide Children eines Parents sind größer als ihr Parent. Diese Bedingung stellt sicher, dass der Root-Node bei Index #0 immer der kleinste ist. (Bei MaxHeap ist die Bedingung umgekehrt, und dann ist Root das Maximum).
      Durch Entnahme (Heap.Pop()) oder Zufügen (Heap.Push()) gerät die Struktur in Unordnung ("verletzte" Heap-Bedingung), daher schließt sich an diese Operationen immer ein "Re-Balancing" an.

      Zwei Beispiele
      Also die Zahlenmenge "1 2 3 4 5 6 7 8 9" könnte simpelstenfalls im Heap-Array folgendermaßen angelegt sein:

      Quellcode

      1. Index 0 1 2 3 4 5 6 7 8
      2. Heap 1 2 3 4 5 6 7 8 9

      Aber ein gültiger Heap präsentiert sich normalerweise dem Auge als total unordentlich (heap: Haufen eben)- etwa so:

      Quellcode

      1. Index 0 1 2 3 4 5 6 7 8
      2. Heap 1 4 2 6 5 9 3 8 7
      Auch hier ist die Heap-Bedingung erfüllt, nämlich die beiden Kinder jedes Nodes sind größer - beachte genau die Indicees - rechne jeweils:

      VB.NET-Quellcode

      1. iChild1 = iParent * 2 + 1
      2. iChild2 = iChild1 + 1

      Heap.Pop()
      Entnommen wird immer der TopNode bei Index #0, und das Re-Balancing erfolgt durch ein lustiges "Aufrücken" der ChildNodes, da der Platz des TopNodes ja neu zu besetzen ist.
      Beim Aufrücken wird von den beiden Children immer der jeweils kleinere ausgewählt, und das stellt die Heap-Bedingung (beide Children sind größer) wieder her.
      Der allerletzte Node wird außerdem gewissermaßen "heimatlos", denn bei Entnahme verkleinert sich der Heap ja um eins.
      Aber sein neuer Platz ergibt sich wie selbstverständlich: Er wird auf diejenige frei werdende Stelle gesetzt, deren kleineres Child immer noch größer ist als der "Heimatlose".
      Meist kommt er aber einfach auf den letzte Platz, der beim Aufrücken frei wird.

      Poppen wir den o.g. "unordentlichen" Heap einfach mal leer:

      Quellcode

      1. Index 0 1 2 3 4 5 6 7 8
      2. Heap 1 4 2 6 5 9 3 8 7 1) -> 1 entnehmen
      3. 2 4 3 6 5 9 7 8 2) -> 2 entnehmen
      4. 3 4 7 6 5 9 8 3) -> 3
      5. 4 5 7 6 8 9 4) -> 4
      6. 5 6 7 9 8 5) -> 5
      7. 6 8 7 9 6) -> 6
      8. 7 8 9 7) -> 7
      9. 8 9 8) -> 8
      10. 9 9) -> 9
      Das Aufrücken im Einzelnen:

      Quellcode

      1. 1) (2) rückt von Index #2->#0. ChildIndizees von #2 sind #5 und #6.
      2. Gewählt wird (3 #6), rückt also von #6->#2.
      3. "Heimatlos" (7 #8) kommt also auf #6.
      4. 2) (3 #2)->#0 (7 #6)->#2 (8 #7)->#6
      5. 3) (4 #1)->#0 (5 #4)->#1 (8 #6)->#4
      6. 4) (5 #1)->#0 (6 #3)->#1 (9 #5)->#3
      7. 5) (6 #1)->#0 (8 #4)->#1
      8. 6) (7 #2)->#0 (9 #3)->#2
      9. 7) (8 #1)->#0 (9 #2)->#1
      10. 8) (9 #1)->#0
      11. 9) (leer)
      Also eine Entnahme führt beim Heap mit 9 Nodes zu maximal 3 Zuweisungen. Bei sehr großen Heaps steigt die Anzahl der Zuweisungen aber nur noch geringfügig an, denn nach jedem Aufrücken verdoppelt sich die Schrittweite im Heap, und dadurch isser sehr schnell durchschritten und wieder ausbalanciertt.
      ZB. in einem Heap mit 32000 Nodes muß pro Entnahme maximal 16 mal gerückt werden.

      Heap.Push(itm)
      Das Zufügen verursacht ein Aufrücken in die andere Richtung, und ist noch performanter, denn der Heap muß nur in seltenen Fällen komplett durchschritten werden:
      Zunächst wird am Ende des Heaps ein neuer Platz geschaffen.
      Dessen Parent errechnet sich durch (childIndex-1)/2, und dieser Parent rückt nach hinten, auf die leere Stelle.
      Das wiederholt sich so lange, bis ein Parent gefunden ist, der kleiner als das NewItem ist. Dann rückt nicht der Parent an diese Stelle, sondern NewItem wird dort eingesetzt und fertig.
      Während bei Entnahme die Schrittweite mit 1 (oder 2) beginnt und sich jeweils verdoppelt, beginnt man beim Poppen mit der größtmöglichen Schrittweite, nämlich mit der halben Gesamtlänge des Heaps, und halbiert pro Schritt, bis ein geeignetes Plätzchen für NewItem gefunden ist (oder NewItem gelangt auf Index #0 - Root des Baumes).
      Bauen wirmal mit der Zahlenfolge 3 2 6 1 9 8 4 7 5 einen Heap auf:

      Quellcode

      1. Index 0 1 2 3 4 5 6 7 8
      2. (leer) 1) <- 3
      3. 3 2) <- 2
      4. 2 3 3) <- 6
      5. 2 3 6 4) <- 1
      6. 1 2 6 3 5) <- 9
      7. 1 2 6 3 9 6) <- 8
      8. 1 2 6 3 9 8 7) <- 4
      9. 1 2 4 3 9 8 6 8) <- 7
      10. 1 2 4 3 9 8 6 7 9) <- 5
      11. 1 2 4 3 9 8 6 7 5
      Das Aufrücken im Einzelnen:

      Quellcode

      1. 1) (3)->#0
      2. 2) (3: #0)->#1 (2)->#0
      3. 3) (6)->#2
      4. 4) (3: #1)->#3 (2: #0)->#1 (1)->#0
      5. 5) (9)->#4
      6. 6) (8)->#5
      7. 7) (6)->#6
      8. 8) (7)->#7
      9. 9) (5)->#8
      Maximal 3 Schritte, aber überwiegend seehr viel weniger :)

      Zum Spaß könnermer auch diesen Heap wieder leer-poppen:

      Quellcode

      1. Index 0 1 2 3 4 5 6 7 8
      2. 1 2 4 3 9 8 6 7 5 1) -> 1
      3. 2 3 4 5 9 8 6 7 2) -> 2
      4. 3 5 4 7 9 8 6 3) -> 3
      5. 4 5 6 7 9 8 4) -> 4
      6. 5 7 6 8 9 5) -> 5
      7. 6 7 9 8 6) -> 6
      8. 7 8 9 7) -> 7
      9. 8 9 8) -> 8
      10. 9 9) -> 9
      Das Aufrücken im Einzelnen:

      Quellcode

      1. 1) (2: #1)->#0 (3: #3)->#1 (5: #8)->#3
      2. 2) (3: #1)->#0 (5: #3)->#1 (7: #7)->#3
      3. 3) (4: #2)->#0 (6: #6)->#2
      4. 4) (5: #1)->#0 (7: #3)->#1 (8: #5)->#3
      5. 5) (6: #2)->#0 (9: #4)->#2
      6. 6) (7: #1)->#0 (8: #3)->#1
      7. 7) (8: #1)->#0 (9: #2)->#1
      8. 8) (9: #1)->#0
      9. 9) (leer)
      Man sieht: Unglaublicherweise geht das tatsächlich auf.
      Programmier-Tipps:   allgemeine Tipps                                   Tipps zu DB-Programmierung
      Helferlein:                  Online Code-Übersetzer (c# <=> vb)   Decompiler ILSpy

      Dieser Beitrag wurde bereits 22 mal editiert, zuletzt von „ErfinderDesRades“ ()

      Heap-Klasse

      VB.NET-Quellcode

      1. Imports System.Collections
      2. <Diagnostics.DebuggerDisplay("Count={Count}, MinHeap={MinHeap}")> _
      3. Public Class Heap(Of T)
      4. 'ein Heap ist ein sortierter, balancierter binärer Baum, im Array (hier: List(of T)) abgebildet.
      5. 'Die beiden Children eines Parents liegen immer genau hinter dem doppelten Index der Parents.
      6. 'Heap-Bedingung (bei MinHeap): beide Children eines Parents müssen größer sein.
      7. ''' <summary>return 1, 0, -1, depending on (IComparable) key should be parent, equal or child of an item</summary>
      8. Public ReadOnly CompareKey As Func(Of IComparable, T, Integer)
      9. Public ReadOnly Selector As Func(Of T, IComparable)
      10. Public ReadOnly MinHeap As Boolean = True
      11. Private _InnerList As New List(Of T)()
      12. Public Sub New(ByVal Selector As Func(Of T, IComparable), ByVal minHeap As Boolean)
      13. Me.Selector = Selector
      14. Me.MinHeap = minHeap
      15. CompareKey = If(minHeap, _
      16. Function(value As IComparable, item As T) value.CompareTo(Selector(item)), _
      17. Function(value As IComparable, item As T) Selector(item).CompareTo(value))
      18. End Sub
      19. Public Sub Clear()
      20. _InnerList.Clear()
      21. End Sub
      22. ''' <summary>clear Heap and return (MinHeap: descending) sorted List</summary>
      23. Public Function GetListSorted() As List(Of T)
      24. 'in-place-sortierung:
      25. 'die Schleife entnimmt vorne immer den TopNode, und schreibt ihn ans Ende.
      26. 'Die Heap-Struktur verkürzt sich dabei jeweils um ein Element
      27. For cnt = _InnerList.Count - 1 To 1 Step -1
      28. _InnerList(cnt) = PopCore(cnt)
      29. Next
      30. GetListSorted = _InnerList
      31. _InnerList = New List(Of T)()
      32. End Function
      33. ''' <summary>Insert Item</summary>
      34. Public Overridable Sub Push(ByVal item As T)
      35. _InnerList.Add(Nothing) ' leeren Platz am Ende schaffen
      36. 'Durch "Aufrücken" wird die korrekte EinfügePosition für item bereitgestellt
      37. 'läuft, ausgehend von letzter Position, von Parent zu Parent, bis einer kleiner ist als key
      38. Dim key = Selector(item)
      39. Dim iChild = _InnerList.Count - 1
      40. While iChild <> 0
      41. Dim iParent = (iChild - 1) >> 1
      42. If CompareKey(key, _InnerList(iParent)) >= 0 Then Exit While 'Parent ist kleiner
      43. _InnerList(iChild) = _InnerList(iParent) 'bisherigen Parent auf iChild schreiben
      44. iChild = iParent
      45. End While
      46. _InnerList(iChild) = item
      47. End Sub
      48. ''' <summary>remove Top-Item and return it</summary>
      49. Public Function Pop() As T
      50. Dim heapLength = _InnerList.Count - 1
      51. Pop = PopCore(heapLength)
      52. _InnerList.RemoveAt(heapLength)
      53. End Function
      54. ''' <summary>return Top-Item without remove it</summary>
      55. Public Function Peek() As T
      56. Return _InnerList(0)
      57. End Function
      58. Public ReadOnly Property Count() As Integer
      59. Get
      60. Return _InnerList.Count
      61. End Get
      62. End Property
      63. ''' <summary>(MinHeap): if bigger than TopNode - take item, and - in exchange - overwrite ByRef-Parameter with popped TopNode</summary>
      64. Public Function TryExchange(ByRef item As T) As Boolean
      65. If CompareKey(Selector(item), _InnerList(0)) <= 0 Then Return False 'ablehnen, wenn item kleiner
      66. Dim itm = Pop()
      67. Push(item)
      68. item = itm
      69. Return True
      70. End Function
      71. Private Function PopCore(ByVal uBound As Integer) As T
      72. 'entnimmt das TopItem, ohne die Innerlist zu verkürzen
      73. PopCore = _InnerList(0) 'der erste, Rückgabewert - sein Platz wird frei
      74. If uBound = 0 Then Exit Function
      75. Dim homeless = _InnerList(uBound) 'der letzte wird "obdachlos"
      76. Dim key = Selector(homeless)
      77. 'es wird der Platz gesucht, wo homeless einzusetzen ist
      78. 'Suche mittels Aufrücken: immer das kleinere der beiden Kinder übernimmt den Parent-Platz
      79. 'Bis ein Platz gefunden ist, an dem homeless noch kleiner ist, oder uBound erreicht
      80. 'Da mit jedem Loop sich die Schrittweite verdoppelt, geht das sehr schnell
      81. Dim iParent = 0
      82. Dim iChild = 1
      83. Do
      84. ' Heap - binärer Baum im Array: die beiden Children eines Knotens
      85. ' liegen genau hinter der Verdopplung des Parent-Index'
      86. Dim child = _InnerList(iChild)
      87. Dim iChild2 = iChild + 1
      88. If iChild2 < uBound Then
      89. Dim child2 = _InnerList(iChild2)
      90. If CompareKey(Selector(child2), child) < 0 Then 'child2 < child
      91. iChild = iChild2
      92. child = child2
      93. End If
      94. End If
      95. If CompareKey(key, child) <= 0 Then Exit Do 'homeless < child
      96. _InnerList(iParent) = child
      97. iParent = iChild
      98. iChild = (iChild << 1) + 1
      99. Loop Until iChild >= uBound 'uBound erreicht oder überschritten
      100. _InnerList(iParent) = homeless
      101. End Function
      102. End Class
      Dateien
      • HeapTester01.zip

        (22,05 kB, 27 mal heruntergeladen, zuletzt: )
      Programmier-Tipps:   allgemeine Tipps                                   Tipps zu DB-Programmierung
      Helferlein:                  Online Code-Übersetzer (c# <=> vb)   Decompiler ILSpy

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „ErfinderDesRades“ ()

      Wie man sieht ist der Code vom Algorithmus her nicht so einfach, und verwendet TypParameter, Delegaten, anonyme Methoden und Zeugs - das mute ich mir und euch erstmal lieber nicht zu, es ausführlich zu erklären.

      Das Teil ist jdfs. strikt generisch gehalten, und kann somit alle Arten von Objekten sortieren.
      Man muß nur einen Selector angeben, der definiert, welche Property der Items für den Vergleich herangezogen werden soll.
      Und man muß angeben, ob der Heap das kleinste Element nach vorne sortieren soll (MinHeap) oder aber das größte (MaxHeap).

      Anhand dieses Threads wurde mir bewußt, dass so ein Heap auch einen recht guten SortierAlgorithmus darstellt, mit der Besonderheit, dasser keinerlei zusätzlichen Speicherbedarf hat.
      Denn der Heap kann sich selbst leerpoppen, und seine Elemente der Reihenfolge nach in die innere Liste schreiben - dieselbe Liste, wo er vorher drin die Heap-Struktur aufgebaut hatte. Denn das LeerPoppen schafft hinten immer einen Platz, wo man das Item wieder hinschreiben kann, und da (beim MinHeap) immer das kleinste Item runtergepoppt wird, baut sich von hinten her eine abwärts sortierte Liste auf.
      Nettes Feature, diese Sortiererei, und kostet nichts, aber die normale Sort-Funktion einer List(Of T) ist ca. 3 mal schneller.

      Aber ich habe noch einen LimitedHeap erfunden, den kann man auf eine bestimmte Anzahl von Elementen begrenzen, und als MinHeap nimmt er dann nur Items auf, die größer sind als das kleinste enthaltene Item. Das bisher kleinste Item wird dann verworfen - oder aber zurückgegeben - quasi im Austausch fürs neue Item. (MaxHeap funktioniert entsprechend umgekehrt).
      Damit kann man nun aus 10000 eingehenden Daten blitzgeschwind die 100 größten ausfiltern.
      Vor allem kann man die Items sukzessive hineinschmeißen, und muß dabei nicht jedesmal alle 100 Items durchsuchen nach demjenigen, welches durch das neue zu ersetzen wäre.

      Der LimitedHeap ist eine nur kleine Abwandlung des normalen Heaps, die nur modifiziert pushen tut:

      VB.NET-Quellcode

      1. ''' <summary>note: limited MinHeap selects biggest values</summary>
      2. Public Class LimitedHeap(Of T) : Inherits Heap(Of T)
      3. Public ReadOnly Limit As Integer
      4. Public Sub New(ByVal Selector As Func(Of T, IComparable), ByVal minHeap As Boolean, ByVal limit As Integer)
      5. MyBase.New(Selector, minHeap)
      6. Me.Limit = limit
      7. End Sub
      8. Public Overrides Sub Push(ByVal item As T)
      9. If Count < Limit Then
      10. MyBase.Push(item)
      11. Else
      12. TryExchange(item)
      13. End If
      14. End Sub
      15. End Class



      Wenn ich schon nicht die Innereien meines Heaps erläutere, so kann ich doch wenigstens zeigen, wie man damit arbeiten kann ;)

      VB.NET-Quellcode

      1. Public Class frmHeapTester
      2. Private _Input As New List(Of Point)
      3. Private _Rnd As New Random
      4. Private _PopHeap As LimitedHeap(Of Point)
      5. Private Sub btGenerate_Click(ByVal sender As Object, ByVal e As EventArgs) Handles btGenerate.Click, btGo.Click, btPop.Click
      6. Select Case True
      7. Case sender Is btGenerate
      8. 'generiere einen Haufen Points, mit zufälligem X-Wert
      9. _Input.Clear()
      10. For i = 0 To CInt(numInput.Value) - 1
      11. _Input.Add(New Point(_Rnd.Next, i))
      12. Next
      13. lstInput.DataSource = Nothing
      14. lstInput.DataSource = _Input
      15. Case sender Is btGo
      16. 'lese die Points in 3 heaps ein - 2 davon limitiert
      17. Dim isMinHeap = ckIsMinHeap.Checked
      18. Dim pointSelector = Function(p As Point) p.X
      19. 'normaler Heap
      20. Dim hp = Heap.FromSelector(pointSelector, isMinHeap)
      21. For Each pt In _Input
      22. hp.Push(pt)
      23. Next
      24. lstAllResults.DataSource = hp.GetListSorted 'Ausgabe
      25. 'limited Heap
      26. Dim limit = CInt(numOutput.Value)
      27. Dim limitedHeap = Heap.FromSelector(pointSelector, isMinHeap, limit)
      28. For Each pt In _Input
      29. limitedHeap.Push(pt)
      30. Next
      31. lstLimitedResults.DataSource = limitedHeap.GetListSorted 'Ausgabe
      32. 'limited Heap für Einzel-Ausgabe per btPop - selector gleich als Func(Of T, TKey) mitgegeben
      33. _PopHeap = Heap.FromSelector(Function(p As Point) p.X, isMinHeap, limit)
      34. For Each pt In _Input
      35. _PopHeap.Push(pt)
      36. Next
      37. Dim sHeap = If(isMinHeap, "MinHeap", "MaxHeap")
      38. GroupBox1.Text = String.Concat(sHeap, ".GetSortedList() - note: limited ", sHeap, _
      39. " selects ", If(isMinHeap, "biggest", "smallest"), " Items")
      40. Case sender Is btPop
      41. lbPopped.Text = _PopHeap.Pop.ToString 'einzelne Ausgabe
      42. End Select
      43. End Sub
      44. End Class
      Programmier-Tipps:   allgemeine Tipps                                   Tipps zu DB-Programmierung
      Helferlein:                  Online Code-Übersetzer (c# <=> vb)   Decompiler ILSpy

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „ErfinderDesRades“ ()

      nicht wahr - die praktische Anwendung ist doch erträglich kompliziert, oder? ;)

      Es gibt 3 Buttons: btGenerate, btGo und btPop

      Alle Klicks werden in nur einer Sub verarbeitet, die je nach geklickstem Button verschiedenes tut:
      1. btGenerate erzeugt zunächstmal einen Haufen Daten. Als Daten-Item nehme ich nicht einfach Integer, sondern was komplexeres, nämlich System.Drawing.Point.
        Die Heap-Klasse ist nämlich nicht fürs Verarbeiten von einfachem ZahlenSalat designed, sondern für bisserl anspruchsvolleres Suchen in "richtigen" Daten, und dass ein DatenObjekt einfach aus einer Zahl besteht, ist inne Praxis ziemlich selten (kann aber auch vom Heap abgedeckt wern).
        Jedenfalls die Property, nach der sortiert werden soll, ist die X-Property der Points. In die Y-Property schreibe ich einfach fortlaufende Nummern.
      2. btGo füllt dann gleich 3 Heaps damit ab, die die Points also nach ihrem X-Wert sortieren:
        Der erste Heap nimmt alle Points auf, und gibt sie in lstAllResults aus.
        Der zweite Heap ist limitiert, und gibt nur die limitierte Anzahl der größen/kleinsten Points in lstLimitedResults aus.
        Der dritte Heap - _PopHeap - behält seine Points erstmal für sich.
      3. btPop nun gibt sukzessive jeweils den Point aus, der in _PopHeap grade dran ist.
      Des weiteren gibts noch die Checkbox ckIsMinHeap, die entscheidet, ob die Heaps MinHeaps oder MaxHeaps sein sollen - und das ist schon das ganze Testprojekt ;).

      Wesentlich bei der Benutzung des Heaps ist die Definition des Selectors, damit der Heap weiß, welche Property ühaupt verglichen werden soll.
      Dass in diesem Fall die X-Property gefragt ist, ist mittels einer winzigen anonymen Methode definiert:

      VB.NET-Quellcode

      1. Dim pointSelector = Function(p As Point) p.X
      Diese anonyme Methode erwartet einen Point, und returnt seine X-Property - steht da ja ;).
      Also wann immer der Heap zwei Points miteinander vergleicht, ruft er für jeden Point diese Methode auf, und erhält so 2 Integers, die er schön miteinander vergleichen kann.
      Diese Sortierung ergibt also eine Reihenfolge, die nach Entfernung zur Y-Achse sortiert (nur fürs Vorstellungsvermögen - Geometrie hat im Sample keine Bedeutung).

      Ich hätte auch einen anderen Selector definieren können, zB:

      VB.NET-Quellcode

      1. Dim pointSelector = Function(p As Point) p.X^2 + p.Y^2
      Dieser Selector würde nun das Quadrat der Beträge der Points vergleichen - daraus ergäbe sich eine annere Reihenfolge, nämlich sortiert nach Entfernung zum Nullpunkt.
      Programmier-Tipps:   allgemeine Tipps                                   Tipps zu DB-Programmierung
      Helferlein:                  Online Code-Übersetzer (c# <=> vb)   Decompiler ILSpy

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ErfinderDesRades“ ()

      Die Benchmarks zeigen, dass die Sortierung per Heap ca. 3-mal langsamer ist als List(Of T).Sort().
      Das ist kein soo schlechtes Ergebnis, denn es gilt ungefähr für jedes Datenvolumen.
      Damit ist auch gezeigt, dass die Komplexität beider Verfahren (List.Sort() verwendet "IntroSort") gleich ist:
      Die Sortier-Dauer wächst natürlich überproportional zur Anzahl der Elemente, aber die Überproportionalität ist die geringste, die ühaupt möglich ist.
      Siehe Vergleich der SortierVerfahren.

      mein Test-Projekt

      VB.NET-Quellcode

      1. Imports System.Drawing
      2. Public Module modMain
      3. Private _Rnd As New Random
      4. Private _Selector As Func(Of Point, IComparable) = Function(pt As Point) pt.X
      5. Private _PointComparer As Comparison(Of Point) = Function(p1 As Point, p2 As Point) p1.X.CompareTo(p2.X)
      6. Sub Main()
      7. ValidateManyHeaps()
      8. Benchmarks()
      9. Console.ReadLine()
      10. End Sub
      11. Private Sub ValidateManyHeaps()
      12. Dim maxSize = 300
      13. 'erstellt maxSize Heaps in den Längen von 1 bis maxSize, und jagt sie in die Validierung
      14. Console.WriteLine(" ".Between("Erstelle und validiere", maxSize, "Heaps in Längen von 1 bis", maxSize))
      15. For n = 1 To maxSize
      16. Dim hp = GetHeap(n)
      17. ValidateHeap(hp)
      18. Next
      19. Console.WriteLine(maxSize & " Validierungen erfolgreich")
      20. Console.WriteLine()
      21. End Sub
      22. Private Function GetHeap(ByVal n As Integer) As Heap(Of Point)
      23. Dim hp = Heap.FromSelector(_Selector, True)
      24. Dim numbs = (From numb In Enumerable.Range(1, n) Order By _Rnd.Next).ToList 'unsortierte Zahlenmenge mit n Elementen
      25. For i = 0 To n - 1
      26. hp.Push(New Point(numbs(i), i))
      27. Next
      28. Return hp
      29. End Function
      30. Private Function GetList(ByVal n As Integer) As List(Of Point)
      31. Dim lst = New List(Of Point)
      32. Dim numbs = (From numb In Enumerable.Range(1, n) Order By _Rnd.Next).ToList 'unsortierte Zahlenmenge mit n Elementen
      33. For i = 0 To n - 1
      34. lst.Add(New Point(numbs(i), i))
      35. Next
      36. Return lst
      37. End Function
      38. Private Sub ValidateHeap(ByVal hp As Heap(Of Point))
      39. Dim p1 = New Point(-1, -1) 'default-Point, der nicht aussm Heap kommt
      40. Dim p2 = p1
      41. Do
      42. p1 = p2
      43. p2 = hp.Pop
      44. 'hier kann man im Haltemodus sehen, dass jedes X von einem größeren X gefolgt wird.
      45. 'Validierungsbeginn eines neuen Heaps erkennt man daran, dass p1 noch den default-Wert hat
      46. If p1.X > p2.X Then Stop 'oh, oh! - wenn Stop kommt, dann läuft was falsch
      47. Loop Until hp.Count = 0
      48. End Sub
      49. Private Sub Benchmarks()
      50. Dim runTime = 3000 '3 Sekunden
      51. Dim minSize = 1920
      52. Dim maxSize = 2000
      53. Console.WriteLine(" ".Between("Sortiere", maxSize - minSize, "Punkte-Mengen in Größen von", minSize, "bis", maxSize))
      54. While MyStopWatch.Until(runTime, "Wie oft hats List geschafft")
      55. For n = minSize To maxSize
      56. Dim lst = GetList(n)
      57. lst.Sort(_PointComparer)
      58. Next
      59. End While
      60. While MyStopWatch.Until(runTime, "Wie oft hats Heap geschafft")
      61. For n = minSize To maxSize
      62. Dim hp = GetHeap(n)
      63. Dim sorted = hp.GetListSorted
      64. Next
      65. End While
      66. Console.WriteLine()
      67. End Sub
      68. End Module



      Wie gesagt: Einsatzgebiet eines Heaps ist nicht das Sortieren gegebener Daten-Mengen, sondern er ist eine Prioritäten-Liste.
      Also eine Auflistung, die jederzeit weitere Items aufnimmt und bewertet, und der jederzeit das best-bewertete Item entnommen werden kann (und danach das zweitbeste, und danach...) - ohne die ganze Liste jedesmal komplett absuchen zu müssen.

      Die LimitedHeap - Erweiterung hingegen dient dazu, eine begrenzte Anzahl best-bewerteter Items zu ermitteln, und alle anderen zu verwerfen.
      Dateien
      Programmier-Tipps:   allgemeine Tipps                                   Tipps zu DB-Programmierung
      Helferlein:                  Online Code-Übersetzer (c# <=> vb)   Decompiler ILSpy

      Dieser Beitrag wurde bereits 3 mal editiert, zuletzt von „ErfinderDesRades“ ()