Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là HeapSort, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về HeapSort thông qua các phần sau.
Nội dung chính
1. Giới thiệu
Heap sort là kỹ thuật sắp xếp dựa trên so sánh dựa trên cấu trúc dữ liệu Binary Heap. Nó tương tự như sắp xếp lựa chọn, nơi đầu tiên chúng ta tìm phần tử lớn nhất và đặt phần tử lớn nhất ở cuối. Chúng ta lặp lại quá trình tương tự cho các phần tử còn lại.
1.1 Binary Heap là gì?
Đầu tiên chúng ta hãy xác định một 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, ngoại 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 (Nguồn Wikipedia)
Một Binary Heap là một cây nhị phân hoàn chỉnh trong đó các mục được lưu trữ theo một thứ tự đặc biệt sao cho giá trị trong nút cha lớn hơn (hoặc nhỏ hơn) so với giá trị trong hai nút con của nó. Cái trước được gọi là max heap và cái sau được 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 biểu diễn dựa trên mảng cho Binary Heap?
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 và cách biểu diễn dựa trên mảng là hiệu quả về không gian. Nếu nút cha được lưu trữ ở chỉ mục I, nút con bên trái có thể được tính bằng 2 * I + 1 và nút con bên phải bằng 2 * I + 2 (giả sử việc lập chỉ mục bắt đầu từ 0).
1.3 Thuật toán Heap Sort(xếp đống) để sắp xếp theo thứ tự tăng dần:
1. Xây dựng một heap tối đa từ dữ liệu đầu vào.
2. Tại thời điểm này, mục lớn nhất được lưu trữ ở gốc của heap. Thay thế nó bằng mục cuối cùng của heap, sau đó giảm kích thước của heap đi 1. Cuối cùng, ta có một gốc heap.
3. Lặp lại bước 2 trong khi kích thước của heap lớn hơn 1.
1.4 Làm thế nào để xây dựng Heap?
Thủ tục Heap chỉ có thể được áp dụng cho một nút nếu các nút con của nó đã được chất đống. Vì vậy việc chất đống phải được thực hiện theo thứ tự từ dưới lên.
Hãy hiểu với sự trợ giúp của một ví dụ sau:
Dữ liệu đầu vào: 4, 10, 3, 5, 1
4 (0)
/ \
10 (1). 3 (2)
/ \
5 (3) 1 (4)
Các số trong ngoặc đại diện cho các chỉ số trong mảng biểu diễn dữ liệu.
Áp dụng quy trình chất đống cho chỉ mục 1:
4 (0)
/ \
10 (1) 3 (2)
/ \
5 (3) 1 (4)
Áp dụng quy trình chất đống cho chỉ mục 0:
10 (0)
/ \
5 (1) 3 (2)
/ \
4 (3) 1 (4)
Thủ tục chất đống tự gọi đệ quy để xây dựng heap theo cách từ trên xuống.
2. Code ví dụ trên nhiều ngôn ngữ
C++
// C++ program for implementation of Heap Sort
#include <iostream>
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 is");
printArray(arr);
}
}
Python
# Python program for implementation of heap Sort
# To heapify subtree rooted at index i.
# n is size of heap
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; // 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)
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
<?php
// Php program for implementation of Heap Sort
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
function 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
// 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[$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 program
$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 13Lưu ý:
- Heap sort là một thuật toán tại chỗ.
- Tùy loại mà triển khai hình thức sắp xếp này vì nó không ổn định, nhưng nó cũng có thể ổn định
3. Độ phức tạp
Độ phức tạp về thời gian: Độ phức tạp về thời gian của heap là O (Logn). Độ phức tạp thời gian của createAndBuildHeap() 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
1. Sắp xếp một mảng gần được sắp xếp xong (hoặc K đã sắp xếp)
2. Tìm k phần tử lớn nhất (hoặc nhỏ nhất) trong một mảng
Thuật toán Heap sort có giới hạn sử dụng vì Quicksort và Mergesort tốt hơn trong thực tế. Tuy nhiên, bản thân cấu trúc dữ liệu Heap được sử dụng rất nhiều.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
