Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


11. Prioritätswarteschlangen



Übungen

  1. Skizzieren Sie den Heap, der sich ergibt, wenn die folgenden Operationen mit einem ursprünglich leeren Heap ausgeführt werden: insert(10), insert(5), insert(2), replace(4), insert(6), insert(8), remove, insert(7), insert(3).
  2. Ist eine Datei in umgekehrt sortierter Reihenfolge ein Heap?
  3. Geben Sie den Heap an, der durch sukzessive Anwendung von insert auf die Schlüssel E A S Y Q U E S T I O N aufgebaut wird.
  4. Welche Positionen können von dem drittgrößten Schlüssel in einem Heap der Größe 32 eingenommen werden? Welche Positionen können von dem drittkleinsten Schlüssel in einem Heap der Größe 32 nicht eingenommen werden?
  5. Warum wird keine Marke verwendet, um den Test j<N in downheap zu vermeiden?
  6. Zeigen Sie, wie die Funktionen von Stapeln und normalen Schlangen als Spezialfälle von Prioritätswarteschlangen erhalten werden können.
  7. Wie groß ist die minimale Anzahl von Schlüsseln, die während einer remove-Operation (Entfernen des größten Elementes) in einem Heap bewegt werden müssen? Skizzieren Sie einen Heap der Größe 15, für den das Minimum erreicht wird.
  8. Schreiben Sie ein Programm zum Löschen des auf Position d befindlichen Elementes in einem Heap.
  9. Führen Sie einen empirischen Vergleich von Bottom-Up- und Top-Down-Konstruktion von Heaps durch, indem Sie Heaps mit 1000 zufälligen Schlüsseln aufbauen.
  10. Geben Sie den Inhalt des Feldes q an, nachdem pqconstruct auf die Schlüssel E A S Y Q U E S T I O N angewandt wurde.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]