Ja, sie können. Sie können darüber in "Einführung in Algorithmen" (von Charles E. Leiserson, Clifford Stein, Thomas H. Cormen und Ronald Rivest) lesen. Nach der Definition von binären Haufen in Wikipedia:
Alle Knoten sind entweder [größer als oder gleich] ( max heaps ) oder [weniger als oder gleich] ( min heaps ) jedes seiner Kinder, entsprechend zu einem für den Heap definierten Vergleichsprädikat.
Ja, sie können Duplikate haben. Von wikipedia Definition von Heap:
Entweder sind die Schlüssel der übergeordneten Knoten immer größer oder gleich zu denen der Kinder und der höchste Schlüssel ist im Wurzelknoten (this Art von Heap heißt Max Heap) oder die Schlüssel der Elternknoten sind kleiner oder gleich als die der untergeordneten Elemente und der niedrigste Schlüssel im Stammknoten (minimaler Heap)
Wenn sie also untergeordnete Knoten haben, bedeutet das, dass sie dupliziert haben können.
Ja, aber ich würde nein sagen. Aus Gründen der Effizienz sollten sie keine verschiedenen Knoten mit doppelten Werten haben oder sie verlieren ihren Zweck ein wenig (Sie müssten untergeordnete Knoten und ähnliches suchen). Sie könnten jedoch jeden Knoten so entwerfen, dass er eine Variable enthält, die angibt, wie viele Kopien dieses Werts Sie in Ihren Daten haben.
Das ist wieder meine Meinung. Wenn dies eine schlechte Art ist, es zu tun, würde ich mich freuen, wenn jemand erklären könnte, warum. Ich muss vielleicht nur etwas Effizienz testen. Wenn Sie einfache Datentypen wie Ints speichern, würde ich sehen, dass es weniger effizient ist, aber für größere Objektknoten, die ids haben, war es nett, scheint es.
Tags und Links java binary-tree heapsort min-heap max-heap