Kont 2017, oppg. 3

Burde ikke det siste elementet være 7 i oppgave 3, her? Mulig jeg har misforstått noe, men jeg skjønner ikke hvor den siste toeren kommer fra.

Basert på et Piazza-spørsmål fra 2019

Her får du oppgitt tabellen $A = \langle 1, 7, 2, 3, 5, 4, 6\rangle$ og blir bedt om å først utføre Build-Max-Heap og deretter Heap-Extract-Max. Det er verdt å merke seg følgende fra oppgaven:

Merk: I svaret så er $A.\textit{heap-size} = A.\textit{length}-1$. Det spørres her om hele $A$, ikke bare heapen.

Da er det nok rett som det står, at $A$ etterpå er

$\langle 6,5,4,3,1,2,2\rangle$

Hvor kommer den siste toeren fra? Prøv å utføre algoritmen akkurat som den er definert (s. 163 i boka), og ta med hele tabellen etterpå, ikke bare haugen. Det er kanskje spesielt viktig å merke seg linje 4 i Heap-Extract-Max.

Det at du tenker 7 er kanskje fordi du tenker på den lignende extract-aktige operasjonen fra Heapsort, der man tar vare på det som plukkes ut?

Får du det ikke til å bli rett? Se trinnvis simulering her.