Ένα δυαδικό Heap είναι ένα πλήρες δυαδικό δέντρο που αποθηκεύεται σε ένα array και διατηρεί την ιδιότητα Heap: σε ένα min-heap, κάθε γονικός κόμβος είναι ≤ των παιδιών του, επομένως το ελάχιστο είναι πάντα στη ρίζα. Αυτό το κάνει την τυπική υλοποίηση μιας Ουράς Προτεραιότητας.
1 index: 0 1 2 3 4
/ \ array: [1, 3, 5, 8, 4]
3 5 parent(i) = (i-1)//2
/ \ left(i) = 2i+1
8 4 right(i) = 2i+2
import heapq
h = []
heapq.heappush(h, 5) # O(log n) — bubble up
heapq.heappush(h, 1)
heapq.heappush(h, 3)
smallest = h[0] # peek min -> O(1)
heapq.heappop(h) # O(log n) — remove root, sift down -> 1
| Λειτουργία | Χρόνος |
|---|---|
| peek ελάχιστο/μέγιστο | O(1) |
| push (εισαγωγή) | O(log n) |
| pop (εξαγωγή) | O(log n) |
| κατασκευή Heap από n στοιχεία | O(n) |
Ένα Heap σας δίνει το επόμενο πιο σημαντικό στοιχείο αμέσως χωρίς να χρειάζεται να κρατάτε τα πάντα πλήρως ταξινομημένα, κάτι που είναι πολύ φθηνότερο από την επανα-ταξινόμηση.
Είναι η ραχοκοκαλιά αλγορίθμων που κινούνται από προτεραιότητες και ένα συχνό εργαλείο συνέντευξης για ερωτήματα "k μεγαλύτερα/μικρότερα".