AU logo

Algoritmer og Datastrukturer

Multiple-choice opgaver

Heaps

Spørgsmål 1

For hvert af følgende arrays, angiv om det er en gyldig min-heap eller max-heap.
Min-heap Max-heap Ingen
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 9 5 6 7 8
1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1
1 2 3 4 5 6 7 8 9
1 6 2 8 4 3 5 7 9
1 2 3 4 5 6 7 8 9
9 6 8 4 5 7 1 3 2
1 2 3 4 5 6 7 8 9
4 1 2 3 5 6 7 8 9

Spørgsmål 2

1 2 3 4 5 6 7 8 9
9 5 8 4 1 6 7 2 3

Angiv hvordan ovenstående binære max-heap ser ud efter HEAP-EXTRACT-MAX.
1 2 3 4 5 6 7 8
8 5 7 4 1 6 3 2
1 2 3 4 5 6 7 8
8 7 5 6 1 4 3 2
1 2 3 4 5 6 7 8
5 8 4 1 6 7 2 3
 

Spørgsmål 3

1 2 3 4 5 6 7 8
9 4 8 2 3 6 7 1

Angiv resultatet af at anvende HEAP-INSERT(A, 5) på ovenstående array.
1 2 3 4 5 6 7 8 9
9 5 8 4 3 6 7 1 2
1 2 3 4 5 6 7 8 9
9 4 8 2 3 6 7 1 5
1 2 3 4 5 6 7 8 9
9 6 8 5 3 7 4 1 2
 

Spørgsmål 4

Angiv den binære max-heap efter indsættelse af elementerne 1, 2, 3, 5, 7, 6 og 4 i den givne rækkefølge, startende med den tomme heap.
1 2 3 4 5 6 7
7 5 6 1 3 2 4
1 2 3 4 5 6 7
7 5 6 1 2 3 4
1 2 3 4 5 6 7
7 6 5 4 3 2 1
 

0% besvaret