Thuật toán HeapSort – Giới thiệu chi tiết và code ví dụ trên nhiều ngôn ngữ lập trình

Hình minh họa thuật toán HeapSort

Chào các bạn! Hôm nay chúng ta sẽ tìm hiểu về một trong những thuật toán sắp xếp thông minh và hiệu quả nhất là HeapSort. Với cách tiếp cận sử dụng cấu trúc dữ liệu Binary Heap, HeapSort đã trở thành một trong những thuật toán sắp xếp phổ biến trong lập trình và thực tế.

1. Giới thiệu về HeapSort

HeapSort là một kỹ thuật sắp xếp dựa trên so sánh, sử dụng cấu trúc dữ liệu Binary Heap. Tương tự như sắp xếp lựa chọn, HeapSort tìm phần tử lớn nhất và đặt nó ở cuối. Sau đó, quá trình lặp lại cho các phần tử còn lại.

Bạn đang xem: Thuật toán HeapSort – Giới thiệu chi tiết và code ví dụ trên nhiều ngôn ngữ lập trình

1.1 Binary Heap là gì?

Trước tiên, chúng ta cần hiểu khái niệm về Cây nhị phân hoàn chỉnh. Cây nhị phân hoàn chỉnh là cây nhị phân trong đó mọi cấp, trừ cấp cuối cùng, được lấp đầy hoàn toàn và tất cả các nút ở bên trái càng xa càng tốt.

Một Binary Heap là một cây nhị phân hoàn chỉnh trong đó giá trị của nút cha lớn hơn (hoặc nhỏ hơn) so với giá trị của hai nút con. Nếu giá trị của nút cha lớn hơn, ta gọi là max heap và ngược lại, ta gọi là min heap. Heap có thể được biểu diễn bằng một cây hoặc mảng nhị phân.

1.2 Tại sao sử dụng mảng để biểu diễn Binary Heap?

Mảng là một cách hiệu quả để biểu diễn Binary Heap. Tại sao? Vì một Binary Heap là một cây nhị phân hoàn chỉnh, nó có thể dễ dàng được biểu diễn dưới dạng một mảng. Nếu chỉ mục của nút cha là I, nút con bên trái có thể tính bằng 2 I + 1 và nút con bên phải bằng 2 I + 2 (với giả định chỉ mục bắt đầu từ 0).

1.3 Làm thế nào để sắp xếp bằng Heap Sort?

Quá trình sắp xếp bằng Heap Sort được thực hiện trong ba bước:

1. Xây dựng một heap tối đa từ dữ liệu đầu vào.
2. Lấy phần tử lớn nhất từ gốc heap và đặt nó ở cuối mảng, sau đó giảm kích thước của heap đi 1. Kết quả là một heap mới.
3. Lặp lại bước 2 cho tới khi kích thước của heap còn lớn hơn 1.

1.4 Ví dụ về xây dựng Heap

Để xây dựng Heap, chúng ta cần thực hiện quy trình heapify từ dưới lên. Dưới đây là một ví dụ minh họa cho quá trình xây dựng Heap:

Dữ liệu đầu vào: 4, 10, 3, 5, 1

        4 (0)
       / 
   10 (1). 3 (2)
   / 
5 (3) 1 (4)

Xem thêm : Cách tính và luận giải các con số may mắn theo ngày tháng năm sinh cực chính xác

Áp dụng quy trình heapify cho chỉ mục 1:

        4 (0)
       / 
   10 (1) 3 (2)
   / 
5 (3) 1 (4)

Áp dụng quy trình heapify cho chỉ mục 0:

       10 (0)
       / 
   5 (1) 3 (2)
   / 
4 (3) 1 (4)

Quá trình heapify được gọi đệ quy để xây dựng Heap từ trên xuống.

2. Code ví dụ trên nhiều ngôn ngữ

Dưới đây là mã nguồn ví dụ cho HeapSort trên một số ngôn ngữ lập trình phổ biến:

C++

// C++ program for implementation of Heap Sort
#include 
using namespace std;

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
    int largest = i; // Initialize largest as root
    int l = 2 * i + 1; // left = 2*i + 1
    int r = 2 * i + 2; // right = 2*i + 2

    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;

    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;

    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);

        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}

// main function to do heap sort
void heapSort(int arr[], int n)
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // One by one extract an element from heap
    for (int i = n - 1; i > 0; i--) {
        // Move current root to end
        swap(arr[0], arr[i]);

        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}

/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; ++i)
        cout << arr[i] << " ";
    cout << "n";
}

// Driver program
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);
}

Java

// Java program for implementation of Heap Sort
public class HeapSort {
    public void sort(int arr[]) {
        int n = arr.length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--) {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int arr[], int n, int i) {
        int largest = i; // Initialize largest as root
        int l = 2 * i + 1; // left = 2*i + 1
        int r = 2 * i + 2; // right = 2*i + 2

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // If largest is not root
        if (largest != i) {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    /* A utility function to print array of size n */
    static void printArray(int arr[]) {
        int n = arr.length;
        for (int i = 0; i < n; ++i)
            System.out.print(arr[i] + " ");
        System.out.println();
    }

    // Driver program
    public static void main(String args[]) {
        int arr[] = { 12, 11, 13, 5, 6, 7 };
        int n = arr.length;

        HeapSort ob = new HeapSort();
        ob.sort(arr);

        System.out.println("Sorted array");
        printArray(arr);
    }
}

Python

# Python program for implementation of heap Sort
def heapify(arr, n, i):
    largest = i  # Initialize largest as root
    l = 2 * i + 1  # left = 2*i + 1
    r = 2 * i + 2  # right = 2*i + 2

    # See if left child of root exists and is
    # greater than root
    if l < n and arr[i] < arr[l]:
        largest = l

    # See if right child of root exists and is
    # greater than root
    if r < n and arr[largest] < arr[r]:
        largest = r

    # Change root, if needed
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]  # swap

        # Heapify the root.
        heapify(arr, n, largest)


# The main function to sort an array of given size
def heapSort(arr):
    n = len(arr)

    # Build a maxheap.
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

    # One by one extract elements
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]  # swap
        heapify(arr, i, 0)


# Driver code to test above
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
print("Sorted array is")
for i in range(n):
    print("%d" % arr[i])

C#

// C# program for implementation of Heap Sort
using System;

public class HeapSort
{
    public void sort(int[] arr)
    {
        int n = arr.Length;

        // Build heap (rearrange array)
        for (int i = n / 2 - 1; i >= 0; i--)
            heapify(arr, n, i);

        // One by one extract an element from heap
        for (int i = n - 1; i > 0; i--)
        {
            // Move current root to end
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;

            // call max heapify on the reduced heap
            heapify(arr, i, 0);
        }
    }

    // To heapify a subtree rooted with node i which is
    // an index in arr[]. n is size of heap
    void heapify(int[] arr, int n, int i)
    {
        int largest = i;
        int l = 2 * i + 1;
        int r = 2 * i + 2;

        // If left child is larger than root
        if (l < n && arr[l] > arr[largest])
            largest = l;

        // If right child is larger than largest so far
        if (r < n && arr[r] > arr[largest])
            largest = r;

        // If largest is not root
        if (largest != i)
        {
            int swap = arr[i];
            arr[i] = arr[largest];
            arr[largest] = swap;

            // Recursively heapify the affected sub-tree
            heapify(arr, n, largest);
        }
    }

    // A utility function to print array of size n
    static void printArray(int[] arr)
    {
        int n = arr.Length;
        for (int i = 0; i < n; ++i)
            Console.Write(arr[i] + " ");
        Console.Read();
    }

    // Driver program
    public static void Main()
    {
        int[] arr = { 12, 11, 13, 5, 6, 7 };
        int n = arr.Length;

        HeapSort ob = new HeapSort();
        ob.sort(arr);

        Console.WriteLine("Sorted array is");
        printArray(arr);
    }
}

PHP

 $arr[$largest])
        $largest = $l;

    // If right child is larger than largest so far
    if ($r < $n && $arr[$r] > $arr[$largest])
        $largest = $r;

    // If largest is not root
    if ($largest != $i) {
        $swap = $arr[$i];
        $arr[$i] = $arr[$largest];
        $arr[$largest] = $swap;   

        // Recursively heapify the affected sub-tree
        heapify($arr, $n, $largest);
    }
}

// main function to do heap sort
function heapSort(&$arr, $n)
{
    // Build heap (rearrange array)
    for ($i = $n / 2 - 1; $i >= 0; $i--)
        heapify($arr, $n, $i);

    // One by one extract an element from heap
    for ($i = $n-1; $i > 0; $i--)
    {
        // Move current root to end
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;

        // call max heapify on the reduced heap
        heapify($arr, $i, 0);
    }
}

/* A utility function to print array of size n */
function printArray(&$arr, $n)
{
    for ($i = 0; $i < $n; ++$i)
        echo ($arr[$i]." ");
}

// Driver Code
$arr = array(12, 11, 13, 5, 6, 7);
$n = sizeof($arr)/sizeof($arr[0]);

heapSort($arr, $n);

echo "Sorted array is n";
printArray($arr, $n);

?>

Kết quả

Sorted array is 5 6 7 11 12 13

Lưu ý:

• Heap Sort là một thuật toán tại chỗ.
• Tùy thuộc vào loại heap, Heap Sort có thể không ổn định, nhưng cũng có thể ổn định.

3. Độ phức tạp

Độ phức tạp thời gian của Heap Sort là O(nLogn). Độ phức tạp thời gian của việc xây dựng Heap là O(n) và độ phức tạp thời gian tổng thể của Heap Sort là O(nLogn).

4. Ứng dụng

Heap Sort có nhiều ứng dụng trong thực tế, bao gồm:

1. Sắp xếp một mảng gần như được sắp xếp hoặc đã sắp xếp (đặc biệt là K-sorting).
2. Tìm K phần tử lớn nhất (hoặc nhỏ nhất) trong một mảng.

Mặc dù Heap Sort có giới hạn sử dụng trong thực tế, Quicksort và Mergesort thường hiệu quả hơn. Tuy nhiên, cấu trúc dữ liệu Heap vẫn được sử dụng rất nhiều.

Nguồn và Tài liệu tham khảo:

• W3Schools
• GeeksforGeeks
• CodeChef
• Dev.to

Nếu bạn cảm thấy bài viết này hữu ích, hãy tham gia các kênh của chúng tôi để nhận thêm nhiều thông tin hơn:

• Group Facebook
• Fanpage
• Youtube
• Instagram
• Twitter
• Linkedin
• Pinterest
• Trang chủ

Chào thân ái và hãy thắng lợi, các bạn nhé!

Nguồn: https://ispacedanang.edu.vn
Danh mục: Học tập