Introduzione a Heap Sort in C ++
Heapsort è una delle tecniche di ordinamento basate sul confronto e fa parte dell'ordinamento di selezione. Laddove l'ordinamento è definito come l'organizzazione di set di dati in un ordine specifico utilizzando un valore univoco noto come elemento chiave nell'elenco specificato. Il termine ordinamento è stato introdotto man mano che le persone venivano a conoscenza dell'importanza di cercare qualsiasi elemento in un dato insieme di informazioni, altrimenti sarebbe molto difficile cercare qualsiasi record se non fosse ordinato e non ordinato.
Esistono molte tecniche diverse per l'ordinamento, ciascuna delle quali ha la rispettiva efficienza nel tempo impiegato per ordinare i dati dati e le esigenze di spazio in memoria. Sono ordinamento a bolle, ordinamento per inserzione, ordinamento per selezione, ordinamento rapido, unione e ordinamento heap.
Che cos'è l'heap sort?
Heapsort è un approccio di ordinamento basato sulla struttura di dati dell'heap binario simile all'ordinamento di selezione in cui otteniamo innanzitutto il set di dati massimo e lo posizioniamo alla fine e continuiamo per il resto degli elementi.
Heapsort come suggerisce il nome stesso. Crea innanzitutto l'heap di elementi di dati dall'array non ordinato specificato, quindi controlla l'elemento più grande e lo posiziona alla fine dell'array parzialmente ordinato. Ricostruisce nuovamente l'heap, cerca il successivo pezzo più grande di record e lo posiziona nel successivo slot vuoto dalla fine della disposizione ordinata dei record. Questo processo viene ripetuto fino a quando non rimangono più elementi nell'heap. Questa tecnica richiede due array uno per la memorizzazione dell'heap e l'altro per un array ordinato.
Algoritmo di Heap Sort in C ++
- Innanzitutto scegli root come elemento elevato dall'insieme di informazioni fornito di elementi per creare un heap massimo.
- Ricostruisci l'heap posizionando o scambiando la radice con l'ultimo elemento.
- Le dimensioni dell'heap ora si ridurranno di 1.
- Quindi creiamo nuovamente l'heap con gli elementi rimanenti e continuiamo fino a quando la dimensione dell'heap non viene ridotta a 1.
Esempio di ordinamento di heap in C ++
Questa tecnica utilizza un heap binario che viene costruito utilizzando un albero binario completo in cui il nodo principale è maggiore dei suoi due nodi figlio.
Considera l'array di set di dati indicato.
Andiamo secondo l'algoritmo. Dice di selezionare l'elemento più alto come radice e costruire l'heap massimo.
1. Prima iterazione
Ora l'array sarà nella forma:
Ora l'array ordinato sarà nel formato:
La dimensione dell'heap verrà ridotta di 1, ora 6-1 = 5.
2. Seconda iterazione
Quindi ora l'heap appare come:
La matrice è nella forma:
La matrice ordinata sarà:
La dimensione dell'heap verrà ridotta di 1, ora 5-1 = 4.
3. Terza iterazione
Il nuovo heap si presenta come:
La matrice è nella forma:
La matrice ordinata sarà:
La dimensione dell'heap verrà ridotta di 1, ora 4-1 = 3.
4. Quarta iterazione
Il nuovo heap si presenta come:
La matrice è nella forma:
La matrice ordinata sarà:
La dimensione dell'heap verrà ridotta di 1, ora 3-1 = 2.
5. Quinta iterazione
Il nuovo heap si presenta come:
La matrice è nella forma:
La matrice ordinata sarà:
La dimensione dell'heap verrà ridotta di 1, ora 2-1 = 1.
6. Ultima iterazione
Il nuovo heap si presenta come:
La matrice ha:
4
Dall'algoritmo, abbiamo eseguito tutti i passaggi fino a quando la dimensione dell'heap è 1. Quindi ora abbiamo l'array ordinato:
Pertanto la matrice ordinata dell'heap massimo è in ordine crescente. Se è necessario che l'array sia ordinato in ordine decrescente, seguire i passaggi precedenti con un heap minimo.
Il programma C ++ per l'heap sort è come indicato di seguito:
#include
using namespace std;
void heapify(int arr(), int n, int i)
(
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l arr(largest))
largest = l;
if (r arr(largest))
largest = r;
if (largest != i) (
swap(arr(i), arr(largest));
heapify(arr, n, largest);
)
)
void heapSort(int arr(), int n)
(
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i >= 0; i--)
(
swap(arr(0), arr(i));
heapify(arr, i, 0);
)
)
void printArray(int arr(), int n)
(
for (int i = 0; i < n; ++i)
cout << arr(i) << " ";
cout << "\n";
)
int main()
(
int arr() = ( 5, 18, 4, 13, 10, 7);
int n = sizeof(arr) / sizeof(arr(0));
heapSort(arr, n);
cout << "Sorted array is \n";
printArray(arr, n);
)
Produzione:
Conclusione
Heapsort è la tecnica basata sul confronto che è il miglioramento dell'ordinamento per selezione. L'ordinamento heap utilizza la selezione dell'elemento più alto o più basso nell'array dato per ordinare in ordine crescente o decrescente rispettivamente con l'heap massimo o minimo. Esegui questo processo fino a quando non ne otteniamo uno come dimensione heap. Questa tecnica di ordinamento viene anche utilizzata per trovare l'elemento più grande e più basso nell'array. La tecnica di ordinamento dell'heap è più efficiente e più veloce della tecnica di ordinamento della selezione.
Articoli consigliati
Questa è una guida a Heap Sort in C ++. Qui discutiamo cos'è l'heap sort in c ++, lavorando con il suo algoritmo ed Esempio. Puoi anche consultare i seguenti articoli per saperne di più-
- Heap Ordina in C
- Ordinamento dell'heap in Java
- Sovraccarico in C ++
- Puntatori in C ++
- Sovraccarico in Java