Rate this post

Heap sort là một thuật toán sắp xếp dựa trên cấu trúc dữ liệu Heap. Nó sắp xếp các phần tử trong mảng bằng cách tạo ra một Heap và sau đó loại bỏ các phần tử từ đầu đến cuối. Heap sort sử dụng kỹ thuật Max Heap hoặc Min Heap để sắp xếp dữ liệu.

Các bài viết liên quan:

Thuật toán Heap Sort sử dụng cấu trúc dữ liệu tốt nhất (heap) để sắp xếp một dãy dữ liệu. Heap là một cây nhị phân có thể lớn hoặc nhỏ hơn giá trị con của nó. Khi sắp xếp dữ liệu, chúng ta sẽ tìm kiếm phần tử lớn nhất trong heap và di chuyển nó đến cuối dãy dữ liệu. Sau đó, chúng ta cập nhật lại heap bằng cách sắp xếp lại các nút con. Quá trình này sẽ tiếp tục cho đến khi tất cả các phần tử đã được sắp xếp.

Ví dụ thuật toán heapsort trong c++

Đây là một ví dụ của thuật toán Heapsort trong C++:

#include <iostream>
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 < n && arr[l] > arr[largest]) 
        largest = l;

    if (r < n && arr[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[] = {12, 11, 13, 5, 6, 7}; 
    int n = sizeof(arr)/sizeof(arr[0]); 

    heapSort(arr, n); 

    cout << "Sorted array is \n"; 
    printArray(arr, n); 
}

Trong ví dụ trên, chúng ta định nghĩa một hàm heapify để tạo ra một Heap Max, và một hàm heapSort để sắp xếp mảng theo thuật toán Heapsort. Cuối cùng, chúng ta in mảng đã sắp xếp.

Giải thích đoạn code trên

Đoạn code trên mô tả thuật toán Heap Sort trong C++.

Heap Sort là một thuật toán sắp xếp cấu trúc dữ liệu với độ phức tạp thời gian tốt nhất, tồi tệ nhất và trung bình O(n log n).

Đoạn code bắt đầu bằng việc tạo một hàm “heapify” để tạo ra một hỗn hợp phù hợp với tất cả các điều kiện cần thiết cho thuật toán Heap Sort. Sau đó, hàm “heapSort” được gọi để thực hiện quá trình sắp xếp bằng cách lấy phần tử lớn nhất trong hỗn hợp và chuyển nó đến cuối mảng. Quá trình này được lặp lại cho đến khi mảng hoàn toàn được sắp xếp.

Độ phức tạp thuật toán Heap sort

Độ phức tạp của thuật toán Heap sort là O(n log n), trong đó n là số lượng phần tử trong mảng cần sắp xếp, log n là độ sâu của cây heap. Trung bình, thuật toán Heap sort hoạt động tốt hơn so với các thuật toán sắp xếp khác như Insertion sort hoặc Selection sort, nhưng không có tốc độ tốt nhất như Quick sort hoặc Merge sort.

Algorithm, C/C++

Heap Sort trong c++

Ví dụ thuật toán heapsort trong c++

Độ phức tạp thuật toán Heap sort

Trả lời Hủy