Thuật toán sắp xếp đống (Có mã trong Python và C++)

Thuật toán sắp xếp Heap là gì?

Heap Sort là một trong những thuật toán sắp xếp phổ biến và nhanh hơn. Nó được xây dựng trên cấu trúc dữ liệu cây nhị phân hoàn chỉnh. Chúng ta sẽ tìm kiếm phần tử lớn nhất và đặt nó lên trên cùng cho vùng heap tối đa. Chúng ta sẽ đặt nó trên nút cha của cây nhị phân.

Giả sử một mảng được đưa ra, dữ liệu = [10,5, 7, 9, 4, 11, 45, 17, 60].

Trong mảng, nếu chỉ mục thứ i-th (i=0,1,2,3 …) là nút cha thì (2i+1) và (2i+2) sẽ là nút con trái và phải. Tạo một cây nhị phân hoàn chỉnh với mảng này sẽ trông như thế này:

Chúng ta sẽ thực hiện quy trình heapify từ đầu đến cuối mảng. Ban đầu, nếu chúng ta chuyển đổi mảng thành cây, nó sẽ trông giống như trên. Chúng ta có thể thấy rằng nó không duy trì bất kỳ thuộc tính heap nào (min-heap hoặc max heap). Chúng ta sẽ có được mảng đã sắp xếp bằng cách thực hiện quy trình heapify cho tất cả các nút.

Ứng dụng sắp xếp đống

Dưới đây là một số cách sử dụng thuật toán sắp xếp heap:

Việc xây dựng “Hàng đợi ưu tiên” cần sắp xếp đống. Bởi vì heapsort giữ cho phần tử được sắp xếp sau mỗi lần chèn được thực hiện.
Cấu trúc dữ liệu Heap hiệu quả trong việc tìm kiếm k^th phần tử lớn nhất trong một mảng nhất định.
Hạt nhân Linux sử dụng sắp xếp heap làm mặc định thuật toán sắp xếp vì nó có độ phức tạp không gian O (1).

Tạo sắp xếp Heap với ví dụ

Ở đây, chúng ta sẽ xây dựng một heap tối đa từ cây nhị phân hoàn chỉnh sau.

Các nút lá là 17, 60, 4, 11 và 45. Chúng không có bất kỳ nút con nào. Đó là lý do tại sao chúng là nút lá. Vì vậy, chúng ta sẽ bắt đầu phương pháp heapify từ nút cha của chúng. Sau đây là các bước:

Bước 1) Chọn cây con ngoài cùng bên trái. Nếu các nút con lớn hơn, hãy hoán đổi nút cha với nút con.

Ở đây nút cha là 9. Và các nút con là 17 và 60. Vì 60 là lớn nhất nên 60 và 9 sẽ được hoán đổi để duy trì đống tối đa.

Bước 2) Bây giờ, cây con ngoài cùng bên trái đã được dồn lại. Nút cha tiếp theo là 7. Nút cha này có hai nút con và nút lớn nhất là 45. Vì vậy, 45 và 7 sẽ được hoán đổi cho nhau.

Bước 3) Nút 60 và 4 có nút cha 5. Vì “5” nhỏ hơn nút con 60 nên nó sẽ được hoán đổi.

Bước 4) Bây giờ, nút 5 có nút con 17,9. Đây không phải là duy trì thuộc tính heap tối đa. Vì vậy, 5 sẽ được thay thế bằng 17.

Bước 5) Nút 10 sẽ được hoán đổi với 60, sau đó được hoán đổi với 17. Quá trình sẽ diễn ra như sau.

Bước 6) Đến bước 5, chúng tôi đã tạo vùng nhớ heap tối đa. Mỗi nút cha đều lớn hơn các nút con của nó. Nút gốc có giá trị tối đa (60).

Lưu ý: Để tạo mảng được sắp xếp, chúng ta cần thay thế nút có giá trị lớn nhất bằng nút kế tiếp của nó.

Quá trình này được gọi là “trích xuất tối đa”. Vì 60 là nút tối đa nên chúng tôi sẽ cố định vị trí của nó thành chỉ mục 0 và tạo vùng heap không có nút 60.

Bước 7) Khi 60 bị loại bỏ, thì giá trị tối đa tiếp theo là 45. Chúng tôi sẽ thực hiện lại quy trình “Trích xuất tối đa” từ nút 45.

Lần này chúng ta sẽ nhận được 45 và thay thế nút gốc bằng nút kế nhiệm 17.

Chúng ta cần phải thực hiện “Trích xuất tối đa” cho đến khi tất cả các phần tử được sắp xếp.

Sau khi thực hiện các bước này cho đến khi trích xuất được tất cả các giá trị tối đa, chúng ta sẽ nhận được mảng sau.

Heap nhị phân là gì?

Heap nhị phân là một loại hoàn chỉnh Cây nhị phân cấu trúc dữ liệu. Trong loại cấu trúc cây này, nút cha lớn hơn hoặc nhỏ hơn nút con. Nếu nút cha nhỏ hơn thì vùng heap được gọi là “Heap tối thiểu” và nếu nút cha lớn hơn thì vùng heap được gọi là “Heap tối đa”.

Dưới đây là ví dụ về vùng heap tối thiểu và vùng heap tối đa.

Trong hình trên, nếu bạn nhận thấy “Min Heap”, nút cha luôn nhỏ hơn các nút con của nó. Ở đầu cây, chúng ta có thể tìm thấy giá trị nhỏ nhất là 10.

Tương tự, đối với “Max Heap”, nút cha luôn lớn hơn nút con. Phần tử tối đa hiện diện ở nút đầu của “Max Heap”.

“Heapify” là gì?

“Heapify” là nguyên lý của heap đảm bảo vị trí của node. Trong Heapify, một max heap luôn duy trì mối quan hệ với parent và child, và node parent sẽ lớn hơn các node child.

Ví dụ, nếu một nút mới được thêm vào, chúng ta cần định hình lại heap. Tuy nhiên, chúng ta có thể cần thay đổi hoặc hoán đổi các nút hoặc sắp xếp lại mảng. Quá trình định hình lại heap này được gọi là "heapify".

Sau đây là ví dụ về cách hoạt động của heapify:

Thêm một nút mới và Heapify — Thêm một nút mới và heapify

Sau đây là các bước thực hiện heapify:

Bước 1) Đã thêm nút 65 làm nút con bên phải của nút 60.

Bước 2) Kiểm tra xem nút mới được thêm có lớn hơn nút cha hay không.

Bước 3) Vì nó lớn hơn nút cha nên chúng tôi đã hoán đổi nút con bên phải với nút cha của nó.

Cách xây dựng Heap

Trước khi xây dựng heap hoặc heapify một cây, chúng ta cần biết cách chúng ta sẽ lưu trữ nó. Vì heap là một cây nhị phân hoàn chỉnh, tốt hơn là sử dụng mảng để chứa dữ liệu của heap.

Giả sử một mảng có tổng cộng n phần tử. Nếu chỉ số thứ “i” là nút cha thì nút bên trái sẽ ở chỉ mục (2i+1)và nút bên phải sẽ ở chỉ mục (2i+2). Chúng tôi giả sử rằng chỉ số mảng bắt đầu từ 0.

Sử dụng điều này, chúng ta hãy lưu trữ một heap tối đa vào một mảng như sau:

Biểu diễn dựa trên mảng của Max Heap — Biểu diễn dựa trên mảng của vùng heap tối đa

Thuật toán heapify duy trì thuộc tính heap. Nếu phần tử cha không có giá trị cực đại (nhỏ hơn hoặc lớn hơn), nó sẽ được hoán đổi với phần tử con cực đại nhất.

Sau đây là các bước để tạo thành một đống tối đa:

Bước 1) Bắt đầu từ nút lá.

Bước 2) Tìm mức tối đa giữa cha mẹ và con cái.

Bước 3) Hoán đổi các nút nếu nút con có giá trị lớn hơn nút cha.

Bước 4) Đi lên một cấp.

Bước 5) Thực hiện theo các bước 2,3,4 cho đến khi chúng ta đạt chỉ số 0 hoặc sắp xếp toàn bộ cây.

Sau đây là mã giả cho heapify đệ quy (heap tối đa):

def heapify():
  input→ array, size, i
  largest = i
  left = 2*i + 1
  right = 2*i + 2
if left<n and array[largest ] < array[left]:
  largest = left
if right<n and array[largest ] < array[right]:
  largest = right
If largest not equals i:
  swap(array[i],array[largest])
  heapify(array,n,largest)

Mã giả để sắp xếp đống

Đây là mã giả cho thuật toán sắp xếp heap:

Heapify(numbers as an array, n as integer, i as integer):
  largest = i
  left = 2i+1
  right= 2i+2
if(left<=n) and (numbers[i]<numbers[left])
  largest=left
if(right<=n) and (numbers[i]<numbers[right])
  largest=right
if(largest  != i)
  swap(numbers[i], numbers[largest])
  Heapify(numbers,n,largest)
HeapSort(numbers as an array):
  n= numbers.size()
for i in range n/2 to 1
  Heapify(numbers,n,i)
for i in range n to 2
  Swap numbers[i] with numbers[1]
  Heapify(numbers,i,0)

Ví dụ về mã sắp xếp heap trong C++

#include <iostream>
using namespace std;
void display(int arr[], int n)
{
    for (int i = 0; i < n; i++)
    {
        cout << arr[i] << "\t";
    }
    cout << endl;
}
void heapify(int numbers[], int n, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && numbers[left] < numbers[largest])
    {
        largest = left;
    }
    if (right < n && numbers[right] < numbers[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
	//uncomment the following line to see details in output
        //cout<<"Swapping "<< numbers[i]<< " and "<<numbers[largest]<<endl;
        swap(numbers[i], numbers[largest]);
        heapify(numbers, n, largest);
    }
}
void heapSort(int numbers[], int n)
{
    for (int i = n/2 - 1; i >= 0; i--)
    {
        heapify(numbers, n, i);
//uncomment the following line to see details in output
 //cout<<"Heapify:\t";
  //display(numbers,n);
    }
    for (int i = n - 1; i >= 0; i--)
    {
        swap(numbers[0], numbers[i]);
        heapify(numbers, i, 0);
    }
}
int main()
{
    int numbers[] = { 10,5, 7, 9, 4, 11, 45, 17, 60};
    int size = sizeof(numbers) / sizeof(numbers[0]);
    cout<<"Initial Array:\t";
    display(numbers,size);
    heapSort(numbers, size);
    cout<<"Sorted Array (descending order):\t";
    display(numbers, size);
}

Đầu ra:

Initial Array:  10      5       7       9       4       11      45      17      60
Sorted Array (descending order):  60      45      17      11      10      9       7       5       4

Ví dụ về mã sắp xếp heap trong Python

def display(arr):
    for i in range(len(arr)):
    print(arr[i], end = "\t")
print()
def heapify(numbers, n, i):
    largest = i
left = 2 * i + 1
right = 2 * i + 2
if left < n and numbers[left] < numbers[largest]:
    largest = left
if right < n and numbers[right] < numbers[largest]:
    largest = right
if largest != i:
    numbers[i], numbers[largest] = numbers[largest], numbers[i]
heapify(numbers, n, largest)
def heapSort(items, n):
    for i in range(n //2,-1,-1):
        heapify(items, n, i) for i in range(n - 1, -1, -1):
        items[0], items[i] = items[i], items[0] heapify(items, i, 0) numbers = [10, 5, 7, 9, 4, 11, 45, 17, 60] print("Initial List:\t", end = "") display(numbers) print("After HeapSort:\t", end = "") heapSort(numbers, len(numbers)) display(numbers)

Đầu ra:

Initial List:   10      5       7       9       4       11      45      17      60
After HeapSort: 60      45      17      11      10      9       7       5       4

Phân tích độ phức tạp thời gian và không gian của Heap Sort

Có Độ phức tạp về thời gian và Độ phức tạp về không gian mà chúng ta có thể phân tích cho sắp xếp đống. Đối với độ phức tạp về thời gian, chúng ta có các trường hợp sau:

Trường hợp tốt nhất
Trường hợp trung bình
Trường hợp xấu nhất

Đống được thực hiện trên một cây nhị phân hoàn chỉnh. Vì vậy, ở cấp độ dưới cùng của cây nhị phân sẽ có số lượng nút tối đa. Nếu mức dưới cùng có n nút thì mức trên sẽ có n/2 nút.

Trong ví dụ này, Cấp 3 có bốn mục, cấp 2 có hai mục và cấp 1 có một mục. Nếu có tổng số n mục thì chiều cao hoặc tổng cấp độ sẽ là Khúc gỗ₂(N). Vì vậy, việc chèn một phần tử có thể mất tối đa số lần lặp Log(n).

Khi chúng ta muốn lấy giá trị lớn nhất từ heap, chúng ta chỉ cần lấy nút gốc. Sau đó, chạy lại heapify. Mỗi heapify lấy Khúc gỗ₂(n) thời gian. Việc trích xuất tối đa mất O(1) thời gian.

Độ phức tạp thời gian trường hợp tốt nhất cho thuật toán sắp xếp đống

Khi tất cả các phần tử đã được sắp xếp trong mảng, sẽ mất O(n) thời gian để tạo vùng nhớ heap. Bởi vì nếu danh sách được sắp xếp thì việc chèn một mục sẽ mất thời gian không đổi là O(1).

Vì vậy, sẽ mất O(n) thời gian để tạo vùng heap tối đa hoặc vùng heap tối thiểu trong trường hợp tốt nhất.

Độ phức tạp thời gian trường hợp trung bình cho thuật toán sắp xếp đống

Chèn một mục hoặc trích xuất một mục tốn thời gian tối đa O(log(n)). Vì vậy, độ phức tạp thời gian trường hợp trung bình cho thuật toán sắp xếp đống là O(n log(n)).

Độ phức tạp thời gian trường hợp xấu nhất cho thuật toán sắp xếp đống

Tương tự như trường hợp trung bình, trong trường hợp xấu nhất, chúng ta có thể thực hiện heapify n lần. Mỗi heapify sẽ tốn thời gian O(log(n)). Vì vậy, độ phức tạp thời gian trong trường hợp xấu nhất sẽ là O(n log(n)).

Độ phức tạp không gian cho thuật toán sắp xếp đống

Heap sort là thuật toán được thiết kế tại chỗ. Điều này có nghĩa là không cần thêm bộ nhớ hoặc bộ nhớ tạm thời để thực hiện tác vụ. Nếu chúng ta xem phần triển khai, chúng ta sẽ nhận thấy rằng chúng ta đã sử dụng swap() để thực hiện việc trao đổi các nút. Không cần danh sách hoặc mảng nào khác. Vì vậy, độ phức tạp không gian là O(1).