Οδηγός για το Heaps στην Python

Εισαγωγή

Φανταστείτε ένα πολυσύχναστο αεροδρόμιο με πτήσεις που απογειώνονται και προσγειώνονται κάθε λεπτό. Όπως οι ελεγκτές εναέριας κυκλοφορίας δίνουν προτεραιότητα στις πτήσεις βάσει επείγουσας ανάγκης, οι σωροί μας βοηθούν να διαχειριζόμαστε και να επεξεργαζόμαστε δεδομένα βάσει συγκεκριμένων κριτηρίων, διασφαλίζοντας ότι το πιο «επείγον» ή «σημαντικό» τμήμα δεδομένων είναι πάντα προσβάσιμο στην κορυφή.

Σε αυτόν τον οδηγό, θα ξεκινήσουμε ένα ταξίδι για να κατανοήσουμε τους σωρούς από την αρχή. Θα ξεκινήσουμε απομυθοποιώντας τι είναι οι σωροί και τις εγγενείς ιδιότητές τους. Από εκεί, θα βουτήξουμε στην εφαρμογή της Python των heaps, το heapq και εξερευνήστε το πλούσιο σύνολο λειτουργιών του. Έτσι, αν έχετε ποτέ αναρωτηθεί πώς να διαχειριστείτε αποτελεσματικά ένα δυναμικό σύνολο δεδομένων όπου το στοιχείο υψηλότερης (ή χαμηλότερης) προτεραιότητας είναι συχνά απαραίτητο, είστε έτοιμοι.

Τι είναι το Heap;

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

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

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

Καθώς προχωράμε, θα βουτήξουμε βαθύτερα στο πώς αυτές οι εγγενείς ιδιότητες των σωρών επιτρέπουν αποτελεσματικές λειτουργίες και πώς η Python heapq Η ενότητα ενσωματώνει απρόσκοπτα σωρούς στις προσπάθειές μας κωδικοποίησης.

Χαρακτηριστικά και Ιδιότητες Σωρών

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

Πρώτα και κύρια, οι σωροί είναι εγγενώς αποτελεσματικό. Η δομή τους που βασίζεται σε δέντρα, συγκεκριμένα η πλήρης μορφή δυαδικού δέντρου, διασφαλίζει ότι λειτουργίες όπως η εισαγωγή και η εξαγωγή στοιχείων προτεραιότητας (μέγιστη ή ελάχιστη) μπορούν να εκτελεστούν σε λογαριθμικό χρόνο, συνήθως O (ημερολόγιο n). Αυτή η αποτελεσματικότητα είναι ένα όφελος για αλγόριθμους και εφαρμογές που απαιτούν συχνή πρόσβαση σε στοιχεία προτεραιότητας.

Μια άλλη αξιοσημείωτη ιδιότητα των σωρών είναι αποδοτικότητα μνήμης. Δεδομένου ότι οι σωροί μπορούν να αναπαρασταθούν χρησιμοποιώντας πίνακες ή λίστες χωρίς την ανάγκη ρητών δεικτών σε θυγατρικούς ή γονικούς κόμβους, εξοικονομούν χώρο. Η θέση κάθε στοιχείου στον πίνακα αντιστοιχεί στην τοποθέτησή του στο δέντρο, επιτρέποντας προβλέψιμη και απλή διέλευση και χειρισμό.

Η ιδιότητα παραγγελίας των σωρών, είτε ως μέγιστος σωρός είτε ως ελάχιστος σωρός, το διασφαλίζει αυτό η ρίζα έχει πάντα το στοιχείο της υψηλότερης προτεραιότητας. Αυτή η συνεπής σειρά είναι που επιτρέπει τη γρήγορη πρόσβαση στο στοιχείο κορυφαίας προτεραιότητας χωρίς να χρειάζεται να κάνετε αναζήτηση σε ολόκληρη τη δομή.

Επιπλέον, οι σωροί είναι πολύπλευρος. Ενώ οι δυαδικοί σωροί (όπου κάθε γονέας έχει το πολύ δύο παιδιά) είναι οι πιο συνηθισμένοι, οι σωροί μπορούν να γενικευθούν ότι έχουν περισσότερα από δύο παιδιά, γνωστά ως d-ary σωροί. Αυτή η ευελιξία επιτρέπει τη μικρορύθμιση με βάση συγκεκριμένες περιπτώσεις χρήσης και απαιτήσεις απόδοσης.

Τέλος, οι σωροί είναι αυτορυθμιζόμενη. Κάθε φορά που προστίθενται ή αφαιρούνται στοιχεία, η δομή αναδιατάσσεται για να διατηρήσει τις ιδιότητές της. Αυτή η δυναμική εξισορρόπηση διασφαλίζει ότι ο σωρός παραμένει βελτιστοποιημένος για τις βασικές του λειτουργίες ανά πάσα στιγμή.

Καθώς εμβαθύνουμε στην υλοποίηση και τις πρακτικές εφαρμογές της Python, οι πραγματικές δυνατότητες των σωρών θα ξεδιπλωθούν μπροστά μας.

Τύποι Σωρών

Δεν δημιουργούνται όλοι οι σωροί ίσοι. Ανάλογα με τη σειρά και τις δομικές τους ιδιότητες, οι σωροί μπορούν να κατηγοριοποιηθούν σε διαφορετικούς τύπους, ο καθένας με το δικό του σύνολο εφαρμογών και πλεονεκτημάτων. Οι δύο βασικές κατηγορίες είναι μέγιστο σωρό και ελάχιστο σωρό.

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

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

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

Ενώ οι δυαδικοί σωροί είναι οι πιο συνηθισμένοι, με κάθε γονέα να έχει το πολύ δύο παιδιά, η έννοια των σωρών μπορεί να επεκταθεί σε κόμβους που έχουν περισσότερα από δύο παιδιά. Σε ένα d-ary σωρός, κάθε κόμβος έχει το πολύ d παιδιά. Αυτή η παραλλαγή μπορεί να βελτιστοποιηθεί για συγκεκριμένα σενάρια, όπως η μείωση του ύψους του δέντρου για την επιτάχυνση ορισμένων λειτουργιών.

Διωνυμικός Σωρός είναι ένα σύνολο διωνυμικών δέντρων που ορίζονται αναδρομικά. Οι διωνυμικοί σωροί χρησιμοποιούνται σε υλοποιήσεις ουράς προτεραιότητας και προσφέρουν αποτελεσματικές λειτουργίες συγχώνευσης.

Πήρε το όνομά του από τη διάσημη ακολουθία Fibonacci, το Σωρός Fibonacci προσφέρει καλύτερους χρόνους εκτέλεσης απόσβεσης για πολλές λειτουργίες σε σύγκριση με δυαδικούς ή διωνυμικούς σωρούς. Είναι ιδιαίτερα χρήσιμοι σε αλγόριθμους βελτιστοποίησης δικτύου.

Python's Heap Implementation – The heapq Μονάδα μέτρησης

Η Python προσφέρει μια ενσωματωμένη μονάδα για λειτουργίες σωρού – το heapq μονάδα μέτρησης. Αυτή η ενότητα παρέχει μια συλλογή λειτουργιών που σχετίζονται με το σωρό που επιτρέπουν στους προγραμματιστές να μετασχηματίζουν λίστες σε σωρούς και να εκτελούν διάφορες λειτουργίες σωρού χωρίς την ανάγκη προσαρμοσμένης υλοποίησης. Ας βουτήξουμε στις αποχρώσεις αυτής της ενότητας και πώς σας προσφέρει τη δύναμη των σωρών.

Η heapq Η μονάδα δεν παρέχει έναν ξεχωριστό τύπο δεδομένων σωρού. Αντίθετα, προσφέρει λειτουργίες που λειτουργούν σε κανονικές λίστες Python, μετασχηματίζοντας και αντιμετωπίζοντάς τις ως δυαδικοί σωροί.

Αυτή η προσέγγιση είναι ταυτόχρονα αποδοτική στη μνήμη και ενσωματώνεται άψογα με τις υπάρχουσες δομές δεδομένων της Python.

Αυτό σημαίνει ότι οι σωροί αντιπροσωπεύονται ως λίστες in heapq. Η ομορφιά αυτής της αναπαράστασης είναι η απλότητά της – το μηδενικό σύστημα ευρετηρίου λίστας χρησιμεύει ως ένα άρρητο δυαδικό δέντρο. Για οποιοδήποτε δεδομένο στοιχείο στη θέση i, είναι:

• Το αριστερό παιδί βρίσκεται στη θέση του 2*i + 1
• Το σωστό παιδί βρίσκεται στη θέση του 2*i + 2
• Ο γονικός κόμβος βρίσκεται στη θέση του (i-1)//2

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

Είναι απαραίτητο να σημειωθεί ότι το heapq ενότητα δημιουργεί ελάχιστες σωρούς από προεπιλογή. Αυτό σημαίνει ότι το μικρότερο στοιχείο βρίσκεται πάντα στη ρίζα (ή στην πρώτη θέση στη λίστα). Εάν χρειάζεστε ένα μέγιστο σωρό, θα πρέπει να αντιστρέψετε τη σειρά πολλαπλασιάζοντας τα στοιχεία επί -1 ή χρησιμοποιήστε μια προσαρμοσμένη συνάρτηση σύγκρισης.

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

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

Πώς να μετατρέψετε μια λίστα σε σωρό

Η heapify() Η λειτουργία είναι το σημείο εκκίνησης για πολλές εργασίες που σχετίζονται με το σωρό. Παίρνει ένα επαναληπτικό (συνήθως μια λίστα) και αναδιατάσσει τα στοιχεία του στη θέση του για να ικανοποιήσει τις ιδιότητες ενός ελάχιστου σωρού:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
heapq.heapify(data)
print(data)

Αυτό θα παράγει μια αναδιατεταγμένη λίστα που αντιπροσωπεύει έναν έγκυρο ελάχιστο σωρό:

[1, 1, 2, 3, 3, 9, 4, 6, 5, 5, 5]

Πώς να προσθέσετε ένα στοιχείο στο σωρό

Η heappush() Η λειτουργία σάς επιτρέπει να εισάγετε ένα νέο στοιχείο στο σωρό διατηρώντας τις ιδιότητες του σωρού:

import heapq heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 7)
print(heap)

Η εκτέλεση του κώδικα θα σας δώσει μια λίστα στοιχείων που διατηρούν την ιδιότητα min heap:

[3, 5, 7]

Πώς να αφαιρέσετε και να επιστρέψετε το μικρότερο στοιχείο από το σωρό

Η heappop() Η συνάρτηση εξάγει και επιστρέφει το μικρότερο στοιχείο από το σωρό (τη ρίζα σε ένα λεπτό σωρό). Μετά την αφαίρεση, διασφαλίζει ότι η λίστα παραμένει ένας έγκυρος σωρός:

import heapq heap = [1, 3, 5, 7, 9]
print(heapq.heappop(heap))
print(heap)

Αυτό θα παράγει το μικρότερο στοιχείο και την υπόλοιπη λίστα:

1
[3, 7, 5, 9]

Εδώ, 1 είναι το μικρότερο στοιχείο από το heap, και η υπόλοιπη λίστα έχει διατηρήσει την ιδιότητα σωρού, ακόμη και μετά την κατάργησή μας 1.

Πώς να σπρώξετε ένα νέο αντικείμενο και να ανοίξετε το μικρότερο αντικείμενο

Η heappushpop() Η συνάρτηση είναι μια συνδυασμένη λειτουργία που ωθεί ένα νέο στοιχείο στο σωρό και στη συνέχεια εμφανίζεται και επιστρέφει το μικρότερο στοιχείο από το σωρό:

import heapq heap = [3, 5, 7, 9]
print(heapq.heappushpop(heap, 4)) print(heap)

Αυτό θα εξάγει 3, το μικρότερο στοιχείο, και εκτυπώστε το νέο heap λίστα που περιλαμβάνει τώρα 4 ενώ διατηρείται η ιδιότητα του σωρού:

3
[4, 5, 7, 9]

Πώς να αντικαταστήσετε το μικρότερο αντικείμενο και να προωθήσετε ένα νέο αντικείμενο

Η heapreplace() Η λειτουργία ανοίγει το μικρότερο στοιχείο και ωθεί ένα νέο στοιχείο στο σωρό, όλα σε μία αποτελεσματική λειτουργία:

import heapq heap = [1, 5, 7, 9]
print(heapq.heapreplace(heap, 4))
print(heap)

Αυτό εκτυπώνει 1, το μικρότερο στοιχείο και η λίστα περιλαμβάνει πλέον 4 και διατηρεί την ιδιότητα σωρού:

1
[4, 5, 7, 9]

Εύρεση πολλαπλών ακραίων στο Python's Heap

nlargest(n, iterable[, key]) και nsmallest(n, iterable[, key]) Οι συναρτήσεις έχουν σχεδιαστεί για να ανακτούν πολλαπλά μεγαλύτερα ή μικρότερα στοιχεία από ένα επαναληπτικό. Μπορούν να είναι πιο αποτελεσματικά από την ταξινόμηση ολόκληρου του iterable όταν χρειάζεστε μόνο μερικές ακραίες τιμές. Για παράδειγμα, ας πούμε ότι έχετε την ακόλουθη λίστα και θέλετε να βρείτε τρεις μικρότερες και τρεις μεγαλύτερες τιμές στη λίστα:

data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]

Εδώ, nlargest() και nsmallest() οι λειτουργίες μπορούν να φανούν χρήσιμες:

import heapq data = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(heapq.nlargest(3, data)) print(heapq.nsmallest(3, data)) 

Αυτό θα σας δώσει δύο λίστες – η μία περιέχει τις τρεις μεγαλύτερες τιμές και η άλλη τις τρεις μικρότερες τιμές από το data λίστα:

[9, 6, 5]
[1, 1, 2]

Πώς να δημιουργήσετε τον προσαρμοσμένο σωρό σας

Ενώ της Python heapq Η ενότητα παρέχει ένα ισχυρό σύνολο εργαλείων για εργασία με σωρούς, υπάρχουν σενάρια όπου η προεπιλεγμένη συμπεριφορά ελάχιστων σωρών μπορεί να μην αρκεί. Είτε θέλετε να εφαρμόσετε ένα μέγιστο σωρό είτε χρειάζεστε ένα σωρό που να λειτουργεί με βάση προσαρμοσμένες συναρτήσεις σύγκρισης, η δημιουργία ενός προσαρμοσμένου σωρού μπορεί να είναι η απάντηση. Ας εξερευνήσουμε πώς να προσαρμόσουμε τους σωρούς στις συγκεκριμένες ανάγκες.

Εφαρμογή ενός Max Heap χρησιμοποιώντας heapq

Από προεπιλογή, heapq δημιουργεί ελάχιστα σωρεία. Ωστόσο, με ένα απλό κόλπο, μπορείτε να το χρησιμοποιήσετε για να εφαρμόσετε ένα μέγιστο σωρό. Η ιδέα είναι να αντιστρέψουμε τη σειρά των στοιχείων πολλαπλασιάζοντάς τα επί -1 πριν τα προσθέσετε στο σωρό:

import heapq class MaxHeap: def __init__(self): self.heap = [] def push(self, val): heapq.heappush(self.heap, -val) def pop(self): return -heapq.heappop(self.heap) def peek(self): return -self.heap[0]

Με αυτήν την προσέγγιση, ο μεγαλύτερος αριθμός (σε όρους απόλυτης τιμής) γίνεται ο μικρότερος, επιτρέποντας το heapq λειτουργεί για τη διατήρηση μιας μέγιστης δομής σωρού.

Σωροί με προσαρμοσμένες συναρτήσεις σύγκρισης

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

Για να το πετύχετε αυτό, μπορείτε να τυλίξετε στοιχεία σε μια βοηθητική κλάση που παρακάμπτει τους τελεστές σύγκρισης:

import heapq class CustomElement: def __init__(self, obj, comparator): self.obj = obj self.comparator = comparator def __lt__(self, other): return self.comparator(self.obj, other.obj) def custom_heappush(heap, obj, comparator=lambda x, y: x < y): heapq.heappush(heap, CustomElement(obj, comparator)) def custom_heappop(heap): return heapq.heappop(heap).obj

Με αυτήν τη ρύθμιση, μπορείτε να ορίσετε οποιαδήποτε προσαρμοσμένη λειτουργία σύγκρισης και να τη χρησιμοποιήσετε με το σωρό.

Συμπέρασμα

Τα Heaps προσφέρουν προβλέψιμη απόδοση για πολλές λειτουργίες, καθιστώντας τα μια αξιόπιστη επιλογή για εργασίες που βασίζονται σε προτεραιότητα. Ωστόσο, είναι σημαντικό να ληφθούν υπόψη οι ειδικές απαιτήσεις και τα χαρακτηριστικά της εφαρμογής. Σε ορισμένες περιπτώσεις, η προσαρμογή της υλοποίησης του σωρού ή ακόμη και η επιλογή εναλλακτικών δομών δεδομένων μπορεί να αποφέρει καλύτερη απόδοση στον πραγματικό κόσμο.

Οι σωροί, όπως έχουμε ταξιδέψει, είναι κάτι περισσότερο από μια άλλη δομή δεδομένων. Αντιπροσωπεύουν μια συρροή αποτελεσματικότητας, δομής και προσαρμοστικότητας. Από τις θεμελιώδεις ιδιότητές τους μέχρι την εφαρμογή τους σε Python's heapq ενότητα, τα heaps προσφέρουν μια ισχυρή λύση σε μια μυριάδα υπολογιστικών προκλήσεων, ειδικά εκείνων που επικεντρώνονται στην προτεραιότητα.

• SEO Powered Content & PR Distribution. Ενισχύστε σήμερα.
• PlatoData.Network Vertical Generative Ai. Ενδυναμώστε τον εαυτό σας. Πρόσβαση εδώ.
• PlatoAiStream. Web3 Intelligence. Ενισχύθηκε η γνώση. Πρόσβαση εδώ.
• PlatoESG. Ανθρακας, Cleantech, Ενέργεια, Περιβάλλον, Ηλιακός, Διαχείριση των αποβλήτων. Πρόσβαση εδώ.
• PlatoHealth. Ευφυΐα βιοτεχνολογίας και κλινικών δοκιμών. Πρόσβαση εδώ.
• πηγή: https://stackabuse.com/guide-to-heaps-in-python/