Data structures·Διάλεξη 10·~36 min

L10 · Δομές Δεδομένων — Σωροί & Ξένα Σύνολα

Χρειάζεσαι:L09 · Γραφήματα IV — MST (Prim, Kruskal)

Τι θα δούμε

Στο L09 αφήσαμε δύο υποσχέσεις. Είπαμε ότι ο Dijkstra και ο Prim τρέχουν σε $O (m lo g n)$ «με έναν δυαδικό σωρό», και ότι ο Kruskal χρειάζεται μια δομή που απαντά γρήγορα «είναι αυτές οι δύο κορυφές ήδη συνδεδεμένες;». Και στις δύο περιπτώσεις είπαμε «θα το δούμε αργότερα».

Αυτή είναι η διάλεξη του «αργότερα». Δύο δομές δεδομένων:

Σωρός (heap) — υλοποιεί μια ουρά προτεραιότητας: «δώσε μου το μικρότερο στοιχείο» σε $O (lo g n)$ . Αυτό κάνει γρήγορους τον Dijkstra και τον Prim.
Ξένα σύνολα (union-find) — απαντά «σε ποιο σύνολο ανήκει το $x$ ;» και «ένωσε δύο σύνολα» σχεδόν σε σταθερό χρόνο. Αυτό κάνει γρήγορο τον Kruskal.

Μέρος Α' — Σωροί (Heaps)

Το πρόβλημα που λύνουν

Φαντάσου μια συλλογή στοιχείων με κλειδιά (αριθμούς) όπου ρωτάς ξανά και ξανά: «ποιο είναι το μικρότερο;» — και μετά το βγάζεις από τη συλλογή. Αυτό ακριβώς κάνει ο Dijkstra: σε κάθε βήμα βγάζει την ανεξερεύνητη κορυφή με το μικρότερο $π (v)$ .

Ποιες είναι οι επιλογές μας;

Δομή	FindMin	Insert / Delete
Μη ταξινομημένος πίνακας	$O (n)$ — σάρωσε όλα	$O (1)$
Ταξινομημένος πίνακας	$O (1)$ — είναι στην άκρη	$O (n)$ — μετατόπιση
Σωρός	$O (1)$	$O (lo g n)$

Ορισμός

Ο ορισμός έχει δύο ανεξάρτητα κομμάτια:

«Ισοσταθμισμένο δυαδικό δέντρο» — αφορά το σχήμα. Κάθε επίπεδο γεμίζει πλήρως πριν αρχίσει το επόμενο, και το τελευταίο γεμίζει από αριστερά. Αυτό εγγυάται ύψος $⌊ lo g_{2} n ⌋$ — εκεί κρύβεται το $O (lo g n)$ κάθε πράξης.
«Ιδιότητα διάταξης» — αφορά τα κλειδιά: κάθε γονιός $\leq$ κάθε παιδί του.

Πρόσεξε τι δεν λέει η ιδιότητα: τίποτα για τη σχέση ανάμεσα σε αδέλφια, ούτε ανάμεσα σε κορυφές διαφορετικών κλάδων. Ο σωρός είναι «χαλαρά» ταξινομημένος — και ακριβώς γι' αυτό συντηρείται φθηνά. Άμεση συνέπεια: η ρίζα έχει πάντα το ελάχιστο κλειδί, οπότε FindMin $= O (1)$ .

Αναπαράσταση με πίνακα

Το ωραιότερο κόλπο: ο σωρός δεν χρειάζεται δείκτες. Αφού το σχήμα είναι αυστηρά ισοσταθμισμένο, αποθηκεύουμε τις κορυφές σε έναν πίνακα $H [1.. n]$ , επίπεδο-επίπεδο από αριστερά προς δεξιά. Τότε για κάθε θέση $i$ :

parent (i) = ⌊ i /2 ⌋, leftChild (i) = 2 i, rightChild (i) = 2 i + 1

«Κατέβα στο παιδί» = πολλαπλασίασε με 2· «ανέβα στον γονέα» = διαίρεσε με 2. Καθαρή αριθμητική, μηδέν δείκτες.

Αυτό ακούγεται αφηρημένο μέχρι να το πιάσεις στα χέρια σου. Πάτησε οποιοδήποτε στοιχείο παρακάτω — δέντρο ή πίνακα — και δες τον γονέα και τα παιδιά του να βγαίνουν από τους τρεις τύπους, για το συγκεκριμένο $i$ που διάλεξες:

Ο σωρός ΕΙΝΑΙ ο πίνακας — δείκτες από καθαρή αριθμητική

H[4] = 9

Πάτησε οποιονδήποτε κόμβο του δέντρου ή κελί του πίνακα — ο γονέας ⌊i/2⌋ και τα παιδιά 2i, 2i+1 ανάβουν ταυτόχρονα και στις δύο όψεις.

Γονέας — ⌊i/2⌋

⌊4/2⌋ = 2

H[2] = 5

Αριστερό παιδί — 2i

2·4 = 8

H[8] = 20

Δεξί παιδί — 2i+1

2·4+1 = 9

H[9] = 21

Επιλεγμένο: H[4] = 9. Ο γονέας του είναι στη θέση ⌊4/2⌋ = 2: το H[2] = 5. Παιδιά: αριστερό στο 2·4 = 8 (H[8] = 20), δεξί στο 2·4+1 = 9 (H[9] = 21).

Δοκίμασε ένα φύλλο (π.χ. το $H [8]$ ): το $2 i$ ξεπερνά το $n$ , άρα «δεν υπάρχει παιδί» — έτσι ακριβώς ξέρει ο αλγόριθμος ότι έφτασε στον πάτο. Και πρόσεξε ότι κάθε γονιός είναι μικρότερος από τα παιδιά του ( $2 \leq 5, 8$ · $5 \leq 9, 11$ · …) — αλλά τα αδέλφια δεν είναι ταξινομημένα μεταξύ τους, και δεν χρειάζεται.

Heapify-up — επιδιόρθωση προς τη ρίζα

Όταν εισάγουμε ένα στοιχείο, το βάζουμε στο τέλος του πίνακα — στην πρώτη ελεύθερη θέση, ώστε το σχήμα να μείνει ισοσταθμισμένο. Αλλά το κλειδί του μπορεί να είναι πολύ μικρό και να παραβιάζει την ιδιότητα — να είναι μικρότερο από τον γονέα του.

ΑλγόριθμοςHeapify-up — επιδιόρθωση προς τη ρίζα

O(log n)

Σπρώξε ένα πολύ μικρό στοιχείο προς τα πάνω, ανταλλάσσοντάς το με τον γονέα όσο είναι μικρότερό του.

Με λόγια. Το νέο, «ελαφρύ» στοιχείο αναδύεται σαν φυσαλίδα. Σε κάθε βήμα το συγκρίνουμε με τον γονέα του· αν είναι μικρότερο, τα ανταλλάσσουμε και συνεχίζουμε από τη νέα του θέση. Σταματάμε μόλις βρει γονέα μικρότερο από αυτό, ή φτάσει το ίδιο στη ρίζα.

Χρόνος. Το μονοπάτι προς τη ρίζα έχει μήκος $\leq lo g_{2} n$ , κάθε βήμα είναι $O (1)$ → $O (lo g n)$ . Η εισαγωγή (Insert) = «βάλε στο τέλος» + Heapify-up, δηλαδή κι αυτή $O (lo g n)$ .

Heapify-down — επιδιόρθωση προς τα φύλλα

Το συμμετρικό πρόβλημα: μια κορυφή έχει κλειδί πολύ μεγάλο — μεγαλύτερο από κάποιο παιδί της. Τη σπρώχνουμε προς τα κάτω.

ΑλγόριθμοςHeapify-down — επιδιόρθωση προς τα φύλλα

O(log n)

Σπρώξε ένα πολύ μεγάλο στοιχείο προς τα κάτω, ανταλλάσσοντάς το με το ΜΙΚΡΟΤΕΡΟ παιδί του.

Με λόγια. Συγκρίνουμε την κορυφή με τα παιδιά της. Αν κάποιο παιδί είναι μικρότερο, ανταλλάσσουμε με το μικρότερο από τα δύο και συνεχίζουμε προς τα κάτω. Σταματάμε όταν και τα δύο παιδιά είναι $\geq$ από αυτήν, ή όταν φτάσει σε φύλλο.

Χρόνος: ίδιο επιχείρημα — μονοπάτι προς τα φύλλα μήκους $\leq lo g_{2} n$ → $O (lo g n)$ .

Δες και τις δύο επιδιορθώσεις να συμβαίνουν — εναλλάξου ανάμεσα στην Insert (που ανεβάζει) και στην ExtractMin (που κατεβάζει), και πρόσεξε πώς δέντρο και πίνακας κινούνται μαζί:

Σωρός βήμα-βήμα — δέντρο και πίνακας συγχρονισμένα

Ένας έγκυρος σωρός 7 στοιχείων — κάθε γονέας ≤ τα παιδιά του. Θα εισάγουμε το 3.

Βήμα 0 / 5

Ουρά προτεραιότητας

Συνδυάζοντας τα παραπάνω παίρνουμε την ουρά προτεραιότητας — μια δομή που πάντα ξέρει «τι έχει σειρά»:

Πράξη	Τι κάνει	Χρόνος
`CreateHeap(H)`	κενός σωρός για $\leq n$ στοιχεία	$O (n)$
`Insert(H, v)`	βάλε στο τέλος, `Heapify-up`	$O (lo g n)$
`FindMin(H)`	επίστρεψε τη ρίζα $H [1]$	$O (1)$
`Delete(H, i)`	βγάλε τη θέση $i$ , `Heapify-down` (ή up)	$O (lo g n)$
`ExtractMin(H)`	`FindMin` + διαγραφή της ρίζας	$O (lo g n)$

Η ουρά προτεραιότητας υποστηρίζει επίσης decreaseKey(H, v, k) — μειώνει το κλειδί ενός στοιχείου και καλεί Heapify-up. Αυτή ακριβώς είναι η πράξη που κάνουν ο Dijkstra και ο Prim όταν βρίσκουν φθηνότερο μονοπάτι ή ακμή προς μια κορυφή.

Δωρεάν μπόνους: Heapsort

Έχοντας την ουρά προτεραιότητας, ένας ολόκληρος αλγόριθμος ταξινόμησης μάς πέφτει στα χέρια χωρίς καμία νέα ιδέα. Σκέψου το: το ExtractMin επιστρέφει πάντα το τρέχον ελάχιστο. Αν το καλέσεις ξανά και ξανά, τα στοιχεία βγαίνουν από το μικρότερο προς το μεγαλύτερο — δηλαδή ταξινομημένα. Αυτός είναι όλος ο αλγόριθμος.

Ο Heapsort έχει λοιπόν δύο φάσεις:

Χτίσιμο σωρού — βάλε και τα $n$ στοιχεία σε έναν σωρό. Με $n$ διαδοχικές Insert αυτό κοστίζει το πολύ $O (n lo g n)$ .
Άδειασμα — κάλεσε ExtractMin $n$ φορές. Κάθε κλήση $O (lo g n)$ , άρα $O (n lo g n)$ συνολικά — και τα στοιχεία βγαίνουν σε αύξουσα σειρά.

Δες το να συμβαίνει: ο σωρός πρώτα γεμίζει, μετά στραγγίζει στοιχείο-στοιχείο σε μια ταξινομημένη έξοδο.

Heapsort — ο σωρός γεμίζει, μετά αδειάζει ταξινομημένος

Έτοιμοι

Ταξινομημένη έξοδος

Δίνονται 6 αριθμοί: 7, 2, 9, 4, 11, 5. Το Heapsort τους ταξινομεί σε δύο φάσεις — πρώτα χτίζει έναν σωρό, μετά τον αδειάζει.

Βήμα 0 / 12

Χρόνος: $O (n lo g n)$ — το ίδιο φράγμα με τη συγχωνευτική ταξινόμηση του L03, αλλά από εντελώς διαφορετικό δρόμο: εκεί «διαίρει και κυρίευε», εδώ «μια δομή που ξέρει πάντα πού είναι το ελάχιστο».

Πώς ο σωρός επιταχύνει τον Dijkstra και τον Prim

Τώρα κλείνει η πρώτη υπόσχεση του L09. Και οι δύο αλγόριθμοι κρατούν μια ουρά προτεραιότητας από ανεξερεύνητες κορυφές:

ExtractMin — διάλεξε την επόμενη κορυφή. Καλείται $n$ φορές → $O (n lo g n)$ .
decreaseKey — όταν μια κορυφή μπει στο $S$ , ενημέρωσε τις προτεραιότητες των γειτόνων της. Συνολικά μέχρι $m$ φορές → $O (m lo g n)$ .

Σύνολο $O (m lo g n)$ — ακριβώς το φράγμα του L09. Χωρίς σωρό, το ExtractMin θα ήταν γραμμική σάρωση $O (n)$ και θα κατέληγες σε $O (n^{2})$ .

Κάρτα μνήμης — Σωρός (Heap)

Λέξεις-κλειδιά

ισοσταθμισμένο δυαδικό δέντρογονέας ≤ παιδιάπίνακας: γονέας ⌊i/2⌋heapify-up / heapify-downρίζα = ελάχιστο

Τα βήματα στο μυαλό σου

1Σχήμα: ισοσταθμισμένο δυαδικό δέντρο — ύψος ⌊log₂ n⌋.

2Διάταξη: κάθε γονέας ≤ κάθε παιδί του, άρα η ρίζα κρατά το ελάχιστο.

3Insert: βάλε στο τέλος, heapify-up (ανέβασέ το όσο είναι < γονέας).

4ExtractMin: επίστρεψε τη ρίζα, φέρε το τελευταίο πάνω, heapify-down (κατέβασέ το προς το μικρότερο παιδί).

Πολυπλοκότητα

FindMin O(1) · Insert/ExtractMin O(log n)

Κλασική παγίδα

Στο heapify-down ανταλλάσσεις πάντα με το ΜΙΚΡΟΤΕΡΟ από τα δύο παιδιά — με το μεγαλύτερο, η ιδιότητα παραβιάζεται ξανά αμέσως. Και ο σωρός δεν λέει τίποτα για αδέλφια: είναι μόνο «χαλαρά» ταξινομημένος, όχι πλήρως.

Μέρος Β' — Ξένα Σύνολα (Union-Find)

Το πρόβλημα που λύνουν

Θυμήσου τον Kruskal από το L09: σαρώνει ακμές σε αύξουσα σειρά κόστους και προσθέτει την ${u, v}$ εκτός αν δημιουργεί κύκλο. Πότε δημιουργεί κύκλο; Ακριβώς όταν οι $u$ και $v$ είναι ήδη στην ίδια συνεκτική συνιστώσα του μέχρι τώρα δέντρου.

Χρειαζόμαστε λοιπόν μια δομή που κρατά μια διαμέριση — μια συλλογή από ανά δύο ξένα σύνολα — και απαντά γρήγορα: «το $u$ και το $v$ είναι στο ίδιο σύνολο;»

Εφαρμογή — συνεκτικές συνιστώσες

Με αυτές τις τρεις πράξεις, η εύρεση των συνεκτικών συνιστωσών ενός γραφήματος γίνεται μηχανική.

ΑλγόριθμοςΣυνεκτικές συνιστώσες με union-find

O((n + m) · α(n))

Κάθε κορυφή ξεκινά μόνη της· κάθε ακμή «κολλάει» τα δύο της άκρα στην ίδια συνιστώσα.

Είσοδος:: γράφημα G = (V, E)
Έξοδος:: μια διαμέριση των κορυφών στις συνεκτικές συνιστώσες

Με λόγια. Φτιάξε ένα ξεχωριστό σύνολο για κάθε κορυφή. Μετά, για κάθε ακμή, ένωσε τα σύνολα των δύο άκρων της (αν είναι ήδη μαζί, δεν χρειάζεται). Στο τέλος, δύο κορυφές είναι στην ίδια συνιστώσα ακριβώς όταν έχουν τον ίδιο Find.

Μια αφελής προσέγγιση — και γιατί δεν φτάνει

Η πιο απλή ιδέα: ένας πίνακας $label []$ , όπου $label [x]$ είναι το «όνομα» του συνόλου του $x$ .

Find(x) — επίστρεψε $label [x]$ . $O (1)$ — εξαιρετικό.
Union(x, y) — διάλεξε ένα όνομα και σάρωσε όλον τον πίνακα αλλάζοντας κάθε εμφάνιση του άλλου ονόματος. $O (n)$ — απαίσιο.

Με $n$ ενώσεις φτάνουμε $O (n^{2})$ . Πληρώνουμε υπερβολικά στο Union. Χρειαζόμαστε καλύτερη ισορροπία.

Κάθε σύνολο ένα δέντρο με ρίζα

Η σωστή ιδέα: αναπαριστούμε κάθε σύνολο σαν ένα κατευθυνόμενο δέντρο με ρίζα.

Κάθε κορυφή έχει έναν δείκτη — προς τον γονέα της.
Η ρίζα δείχνει στον εαυτό της και είναι ο αντιπρόσωπος του συνόλου.
Πολλά ξένα σύνολα → ένα κατευθυνόμενο δάσος.

Με αυτή την αναπαράσταση, οι τρεις πράξεις γίνονται απλές:

MakeSet(x) — ένα δέντρο με μία μόνο κορυφή, που δείχνει στον εαυτό της. $O (1)$ .
Find(x) — ακολούθησε τους δείκτες-γονείς από το $x$ προς τα πάνω, ως τη ρίζα· επίστρεψέ την.
Union(x, y) — βρες τις δύο ρίζες, και κάνε τη μία να δείχνει στην άλλη. $O (1)$ — αφού έχεις τις ρίζες.

Τρέξε μια ακολουθία από αυτές τις πράξεις και δες το δάσος να σχηματίζεται. Πρόσεξε δύο πράγματα: το Find ανεβαίνει πάντα μέχρι τη ρίζα, και ο πίνακας γονέων από κάτω είναι το ίδιο ακριβώς δάσος, γραμμένο σαν απλοί αριθμοί.

Union-Find — κάθε σύνολο ένα δέντρο με ρίζα

MakeSet ×7

Ίδιο χρώμα = ίδιο σύνολο · βέλος = δείκτης προς τον γονέα · 7 σύνολα τώρα

Πίνακας γονέων — parent[ ]

11ρίζα

22ρίζα

33ρίζα

44ρίζα

55ρίζα

66ρίζα

77ρίζα

Επτά στοιχεία, επτά ξεχωριστά σύνολα. Το MakeSet δίνει στο καθένα το δικό του δέντρο μιας κορυφής — ρίζα του εαυτού του.

Βήμα 0 / 8

Πρώτη βελτίωση: union by size

Η προειδοποίηση πιο πάνω είπε ότι ο εχθρός είναι η αλυσίδα. Να ο φθηνός τρόπος να την αποφεύγουμε: για κάθε δέντρο αποθηκεύουμε το μέγεθός του, και στο Union κάνουμε πάντα τη ρίζα του μικρότερου δέντρου να δείχνει στη ρίζα του μεγαλύτερου — ποτέ ανάποδα.

Το παρακάτω εργαλείο τρέχει την ίδια ακολουθία ενώσεων με δύο στρατηγικές. Πάνω, η απλοϊκή ένωση που αγνοεί τα μεγέθη· κάτω, το union by size. Δες το βάθος του ενός να εκτοξεύεται και του άλλου να μένει καρφωμένο:

Union by size — η ίδια ακολουθία, δύο στρατηγικές

Αρχή

Απλοϊκή ένωση

βάθος: 0 · χειρότερο Find 0 βήματα

Union by size

βάθος: 0 · χειρότερο Find 0 βήματα

Πέντε μεμονωμένα στοιχεία — και οι δύο πλευρές ξεκινούν ίδιες. Θα τρέξουμε ΤΗΝ ΙΔΙΑ ακολουθία ενώσεων· η μόνη διαφορά είναι ποιο δέντρο κρεμιέται κάτω από ποιο.

Βήμα 0 / 4

Η εικόνα γίνεται θεώρημα:

Δεύτερη βελτίωση: συμπίεση μονοπατιών

Σχεδόν δωρεάν — και κρύβεται μέσα σε μια πράξη που κάνουμε ήδη. Κάθε φορά που τρέχουμε Find(v), διασχίζουμε ολόκληρο το μονοπάτι από το $v$ ως τη ρίζα· το πληρώσαμε ήδη. Πριν επιστρέψουμε, λοιπόν, ξανασυνδέουμε κάθε κορυφή αυτού του μονοπατιού απευθείας στη ρίζα.

Δες το να συμβαίνει: μια Find σε ένα σχεδόν εκφυλισμένο δέντρο πληρώνει τη μακριά διαδρομή μία φορά — και την ισιώνει στο πέρασμά της, ώστε η επόμενη να είναι ακαριαία.

Συμπίεση μονοπατιού — πλήρωσε μία φορά, κέρδισε για πάντα

Αρχή

Αναπηδήσεις αυτής της Find: 0

Πίνακας γονέων — parent[ ]

11ρίζα

21γονέας

32γονέας

43γονέας

54γονέας

65γονέας

74γονέας

Αυτό το δέντρο union-find έχει εκφυλιστεί σχεδόν σε αλυσίδα. Θα τρέξουμε Find(6) — και θα δούμε τη συμπίεση μονοπατιού να το ισιώνει.

Βήμα 0 / 8

Με union by size + συμπίεση μονοπατιών μαζί συμβαίνει κάτι σχεδόν μαγικό: μια ακολουθία $m$ πράξεων σε $n$ στοιχεία τρέχει σε $O (m \cdot α (n))$ .

Κλειδί

Το $α (n)$ είναι η αντίστροφη συνάρτηση Ackermann. Η συνάρτηση Ackermann μεγαλώνει τόσο εκρηκτικά γρήγορα, που η αντίστροφή της σέρνεται απίστευτα αργά: παραμένει $\leq 4$ για κάθε $n$ μέχρι έναν αριθμό αστρονομικά μεγαλύτερο από το πλήθος των ατόμων στο σύμπαν.

Για κάθε $n$ που θα συναντήσεις ποτέ σε αληθινό πρόβλημα, λοιπόν, $α (n) \leq 4$ . Πρακτικά, το union-find κοστίζει σταθερό χρόνο ανά πράξη — γι' αυτό θεωρείται από τις πιο αποδοτικές δομές δεδομένων που υπάρχουν.

Πώς το union-find επιταχύνει τον Kruskal

Κλείνει και η δεύτερη υπόσχεση του L09. Στον Kruskal, ο έλεγχος «κλείνει κύκλο;» γίνεται με ένα ζεύγος Find, και η προσθήκη ακμής με ένα Union:

Ταξινόμηση: $O (m lo g n)$ .
$m$ ζεύγη Find + έως $n - 1$ Union: $O (m \cdot α (n))$ — ουσιαστικά γραμμικό.
Σύνολο: $O (m lo g n)$ — η ταξινόμηση κυριαρχεί. Ακριβώς το φράγμα του L09.

Κάρτα μνήμης — Union-Find (ξένα σύνολα)

Λέξεις-κλειδιά

κάθε σύνολο = δέντρο με ρίζαFind = ανέβα ως τη ρίζαunion by sizeσυμπίεση μονοπατιώνO(α(n)) ανά πράξη

Τα βήματα στο μυαλό σου

1MakeSet: κάθε στοιχείο μόνο του, δείκτης στον εαυτό του.

2Find(x): ακολούθησε τους δείκτες-γονείς ως τη ρίζα — αυτή είναι ο αντιπρόσωπος.

3Union(x, y): βρες τις δύο ρίζες, κρέμασε τη μικρότερη κάτω από τη μεγαλύτερη.

4Συμπίεση μονοπατιών: μετά από Find, ξανασύνδεσε όλο το μονοπάτι απευθείας στη ρίζα.

Πολυπλοκότητα

O(α(n)) αμορτοποιημένα — πρακτικά σταθερό

Κλασική παγίδα

Χωρίς union by size τα δέντρα εκφυλίζονται σε αλυσίδες και το Find γίνεται O(n). «Ίδιο σύνολο;» σημαίνει ίδιο Find — όχι σύγκριση δεικτών-γονέων· δύο στοιχεία είναι μαζί ανν Find(x) = Find(y).

Κλείδωσε τη γνώση

Βάλε στη σειρά τα βήματα του ExtractMin:

Βάλε τα βήματα στη σειρά

Η πράξη ExtractMin ενός σωρού, από την πρώτη ενέργεια στην τελευταία.

Σύρε τις γραμμές για αναδιάταξη — ή χρησιμοποίησε τα βελάκια.

1.Επίστρεψε το αποθηκευμένο ελάχιστο.

2.Σύγκρινε το νέο στοιχείο της ρίζας με το μικρότερο από τα παιδιά του.

3.Μείωσε το μέγεθος του σωρού κατά ένα.

4.Φέρε το τελευταίο στοιχείο του σωρού στη θέση της ρίζας.

5.Όσο κάποιο παιδί είναι μικρότερο, αντάλλαξέ τα και κατέβα — heapify-down.

6.Διάβασε τη ρίζα H[1] — αυτό είναι το ελάχιστο που θα επιστραφεί· κράτησέ το.

Και συμπλήρωσε τα κενά για το union-find:

Συμπλήρωσε τα κενά

Η δομή ξένων συνόλων σε τέσσερις λέξεις-κλειδιά.

Στο union-find, κάθε σύνολο αναπαρίσταται ως ένα δέντρο με , που είναι ο αντιπρόσωπός του. Η πράξη Find ανεβαίνει ως εκεί, οπότε δύο στοιχεία ανήκουν στο ίδιο σύνολο αν έχουν το ίδιο . Η τεχνική union by size κρεμάει το δέντρο κάτω από το μεγαλύτερο, κρατώντας το βάθος O(log n) — και η συμπίεση μονοπατιών το μικραίνει κι άλλο, ώστε κάθε πράξη να κοστίζει πρακτικά χρόνο.

Μοτίβο σκέψης

Διάλεξε δομή δεδομένων από τις πράξεις

Σινιάλα στην εκφώνηση«ξανά και ξανά «δώσε μου το ελάχιστο»»««είναι αυτά τα δύο μαζί;»»«ποια δομή υποστηρίζει… γρήγορα»

Μια δομή δεδομένων δεν είναι «καλή» ή «κακή» απόλυτα — είναι καλή για κάποιες πράξεις και κακή για άλλες. Πριν διαλέξεις:

Γράψε τις πράξεις που θα κάνεις πολλές φορές. Αυτές πρέπει να είναι γρήγορες· τις σπάνιες μπορείς να τις θυσιάσεις.
«Επαναλαμβανόμενα το ελάχιστο / μέγιστο» → σωρός, δηλαδή ουρά προτεραιότητας.
«Συνεχώς ενώνω ομάδες και ρωτάω αν δύο πράγματα είναι μαζί» → union-find.
Θυμήσου τον πίνακα συμβιβασμών: ταξινομημένος πίνακας, μη ταξινομημένος, σωρός — καθένας κερδίζει σε άλλη πράξη. Δεν υπάρχει δομή που τα κάνει όλα φθηνά· η τέχνη είναι να ταιριάξεις τη δομή με το προφίλ των πράξεών σου.

Ραντάρ εξετάσεων

Τρέξε heapify-up / heapify-down ή Insert / ExtractMin βήμα-βήμα σε δοσμένο σωρό (περιλαμβάνει αλλαγή κλειδιού)συχνό

Δες το στις ασκήσειςpt6-th3

Η αντιστοίχιση σωρού ↔ πίνακα: τύποι parent/child, ποιο στοιχείο σε ποια θέσηπιθανό

Union-Find: τρέξε μια ακολουθία MakeSet / Union / Find και σχεδίασε το δάσοςπιθανό

Απόδειξη ότι το union by size κρατά το βάθος ≤ log nπιθανό

Hash table για ζευγάρωμα τιμών — pair-sum & meet in the middle σε O(n) ή O(n^{k/2})συχνό

Δες το στις ασκήσειςfront-set-5-ask10 front-set-5-ask11

Ποια δομή για ποια πράξη — γιατί ο σωρός κάνει τον Dijkstra O(m log n)σπανιότερο

Τι μάθαμε

Τι κρατάμε από αυτή τη διάλεξη

Σωρός — ισοσταθμισμένο δυαδικό δέντρο με ιδιότητα διάταξης (γονιός $\leq$ παιδιά). Αποθηκεύεται σε πίνακα: $parent (i) = ⌊ i /2 ⌋$ , παιδιά $2 i$ και $2 i + 1$ — μηδέν δείκτες.
Heapify-up / Heapify-down — επιδιορθώνουν μία παραβίαση σε $O (lo g n)$ , σπρώχνοντας ένα στοιχείο προς τη ρίζα ή προς τα φύλλα (πάντα προς το μικρότερο παιδί).
Ουρά προτεραιότητας — FindMin $O (1)$ , Insert/ExtractMin $O (lo g n)$ . Δίνει Heapsort $O (n lo g n)$ και κάνει Dijkstra & Prim $O (m lo g n)$ .
Union-Find — MakeSet, Union, Find πάνω σε διαμέριση σε ξένα σύνολα. Κάθε σύνολο = δέντρο με ρίζα = αντιπρόσωπο.
Union by size κρατά το βάθος $\leq lo g n$ · η συμπίεση μονοπατιών το μικραίνει κι άλλο. Μαζί → $O (α (n))$ ανά πράξη, πρακτικά σταθερό.
Το union-find κάνει τον Kruskal $O (m lo g n)$ — η ταξινόμηση των ακμών είναι πια το ακριβό κομμάτι.

Επόμενο

L11 · Άπληστοι I — interval scheduling, exchange argument

Ασκήσεις από εξετάσεις

Από τη θεωρία στην εξεταστική

3 άσκησεις που χρησιμοποιούν ως τελευταίο εργαλείο αυτή τη διάλεξη. Οι πρόσφατες εξεταστικές (2024/2025) φέρουν badge προτεραιότητας.

Από φροντιστήριοΦροντιστήριο 2023–24Άσκηση 10Δομές δεδομένωνΔύσκολο

Φροντιστηριακό Σετ #5 · Άσκηση 10 — Πυθαγόρεια τετράδα σε O(n²)

Μια Πυθαγόρεια τετράδα είναι ακέραιοι $(a, b, c, d)$ με $d = a^{2} + b^{2} + c^{2}$ , δηλαδή $a^{2} + b^{2} + c^{2} = d^{2}$ . Σχεδίασε αλγόριθμο $O (n^{2})$ που αποφασίζει αν υπάρχει Πυθαγόρεια τετράδα σε έναν πίνακα $n$ διακριτών θετικών ακεραίων (επιτρέπεται η πολλαπλή χρήση ενός στοιχείου).

Απαιτεί:L10 · Δομές δεδομένων

Από φροντιστήριοΦροντιστήριο 2023–24Άσκηση 11Δομές δεδομένωνΜέτριο

Φροντιστηριακό Σετ #5 · Άσκηση 11 — Ζεύγη με δοσμένο άθροισμα σε O(n)

Σχεδίασε αλγόριθμο που, δοθέντος ενός πίνακα $A$ με $n$ διαφορετικούς ακεραίους στο εύρος ${1, \dots, n^{4}}$ και τιμή στόχο $x$ , εκτυπώνει όλα τα ζεύγη $(i, j)$ με $A [i] + A [j] = x$ . Ο αναμενόμενος χρόνος πρέπει να είναι $O (n)$ .

Απαιτεί:L10 · Δομές δεδομένων

Παλαιό θέμαΣεπτέμβριος 2023Θέμα 325%Δομές δεδομένωνΜέτριο

Σεπτέμβριος 2023 · Θέμα 3 — Master Theorem & επιδιόρθωση σωρού

(Α) Να επιλυθεί η αναδρομική εξίσωση $T (n) = 3 T (2 n /3) + c$ , όπου $T (1) = Θ (1)$ και $c$ μια σταθερά θετική, με χρήση του Θεωρήματος Κυριαρχίας (Master Theorem).

(Β) Η ακολουθία $t_{1}, t_{2}, \dots, t_{n}$ είναι αποθηκευμένη στον μονοδιάστατο πίνακα $H$ υπό δομή σωρού (max-heap). Κάποιος όρος $t_{s}$ αλλάζει και παίρνει μικρότερη τιμή. Ο νέος πίνακας $H$ ενδέχεται να μην είναι πλέον σωρός.

i. Να δοθεί σύντομα ένας αναδρομικός αλγόριθμος $R A (H, i)$ που διατηρεί στον $H$ τη δομή σωρού. ii. Να δοθεί η αναδρομική σχέση $S (n)$ που περιγράφει την πολυπλοκότητα του αλγορίθμου στη χείριστη περίπτωση. iii. Να επιλυθεί η $S (n)$ , με $S (1) = Θ (1)$ . iv. Εφαρμόστε τον αλγόριθμο για έναν εσωτερικό κόμβο που κρατούσε την τιμή $14$ , όταν αυτή αλλάζει σε $13$ και όταν αλλάζει σε $6$ (τα παιδιά του κόμβου κρατούν τις τιμές $8$ και $10$ ).

Απαιτεί:L03 · D&C I (mergesort, master)L10 · Δομές δεδομένων

Φόρτωση σχολίων…