Ορθότητα αλγορίθμου

[Mathletic]

Γειά

Διαβάζω την ορθότητα του αλγορίθμου BuildHeap, η οποία μπορεί να αποδειχθεί μέσω της αναλλοίωτης συνθήκης:

Στην αρχή κάθε επανάληψης του βρόχου for στις γραμμές , κάθε κόμβος είναι ρίζα ενός σωρού μεγίστου.

Ο αλγόριθμος είναι ο εξής:

Κώδικας: Επιλογή όλων

HeapSort(A){
  Buildheap(A);
  for (i=size(A); i>1; --i){
       swap(A[i],A[1]);
       heap_size(A)=heap_size(A)-1;
       Heapify(A,1);
  }
}

Κώδικας: Επιλογή όλων

BuildHeap(A){
1.  for (i=floor((size(A))/2); i>=0; i--){
2.       Heapify(A,i);
   }
}

Κώδικας: Επιλογή όλων

Heapify(A,i){
  l=left(i);
  r=right(i);
  largest=i;
  if (l<=size(A) && A[l]>A[i]) largest=l;
  if (r<=size(A) && A[r]>A[largest]) largest=r;
  if (largest!=i){
      swap(A[i],A[largest]);
      Heapify(A, largest);
  }
}

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

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

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

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


Μπορείτε να μου εξηγήσετε τον έλεγχο διατήρησης;

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

Υποθέτουμε ότι ισχύει η αναλλοίωτη συνθήκη για και θέλουμε να δείξουμε ότι ισχύει και για ;