Implementierung von Heap (ADT) mit Array Vs. LinkedList

Question

In meiner Daten-Struktur natürlich muss ich mit der folgenden Zeit einen binären Heap implementieren - Komplexitätsanforderungen:

• Max finden - O (1)
• Einfügen - O (lg n)
• Max löschen - O (lg n)

Jetzt dachte ich, das ein Array in der folgenden Art und Weise verwendet implementieren: die Wurzel des Haufens ist in Arr [1] (dem ersten Index). Die Kinder von Arr [i] sind in Arr [2i] und Arr [2i + 1] (2 Kinder). Mit dieser Implementierung bekomme ich Find Max in O (1), Löschen Max in O (n) und Einfügen in O (lg n) mit einer Ausnahme - wenn ich einfügen muss, wenn das Array voll ist, muss ich die Größe ändern Array und "kostet" mich O (n), so dass die Gesamtkosten des Einfügens mit allen Randfällen O (n) anstelle von O (log n) wie erforderlich sein wird.

Gibt es eine andere Art der Implementierung, die alle komplexen Anforderungen erfüllt? Ich dachte vielleicht zu versuchen, mit einer LinkedList anstelle eines Arrays zu implementieren, aber einfügen wird immer noch O (n). Vorschläge für eine Implementierung sind sehr willkommen.

Answer 1

Ihre Implementierung kann die Anforderungen erfüllen. Ich nehme an, dass, wenn Sie sagen, delete max nimmt O (n), Sie denken, dass Sie das gesamte Array über eine Position verschieben müssen? Was Sie in diesem Fall tatsächlich tun müssen, ist, haben Sie das nächste größte Element "schwimmen" an die Spitze, wie sie sagen. Dies erfordert nur O (lgn) Zeit.

Auch die Größenänderung passiert nicht oft, so dass die amortisiert Laufzeit ist immer noch O (lgn). See here.