Qual è la differenza tra A.length e A.heap-size?

Question

Ho una domanda sull'ordinamento dell'heap. Si afferma in un libro di Algorithms che A.heap-size<= A.length non capisco la differenza tra i due. Se una matrice rappresenta un heap, perché esiste la possibilità che A.heap-size sia inferiore a A.length. So che A.heap-size rappresenta il numero di elementi all'interno di un heap, quindi perché non è completamente uguale al numero di elementi all'interno di un array?

Answer 1

L'invariante dell'ordinamento dell'heap è che i primi k elementi dell'array n-elemento sono un heap sugli elementi k più piccoli e gli ultimi elementi n-k sono gli elementi nk più grandi in ordine ordinato. Gli ultimi elementi sono il motivo per cui l'heap non occupa l'intero array.

Answer 2

Solo per espandere una risposta. Leggi oltre quel libro.

A.heap_size di un array, è il luogo in cui verranno posizionati gli elementi della struttura heap (max_heap o min_heap). Ha senso nell'ambito dell'ordinamento o dell'accodamento. Hai ragione: questo è il numero di elementi all'interno di un heap, ma è uguale a A.length solo a prima iterazione di ordinamento heap.

Alla successiva iterazione, dopo lo scambio di radice dell'albero max_heap (A[1]) con A[i] = A[A.length] (ultimo elemento all'interno array A), l'elemento A[1] sarà l'ultimo elemento della A e A.heap_sort valore viene diminuito di 1 e max_heap la struttura deve essere max_heapified: A[Parent(i)] >= A[i], dove Parent(i) restituisce i/2 della struttura ad albero.

Answer 3

Dal libro di testo Algoritmo di Cormen che sto usando: (questo mi ha aiutato)

Answer 4

a.length dà la totale non di elementi di serie, mentre dimensioni A.heap dato il no di elementi che sono in ordine ordinato o no di elementi che seguono la proprietà heap ........ E dimensione A.length-A.heap o addirittura non ordinati anche adesso e devono essere ordinati in futuro.