C++: Sắp xếp vun đống (Heap Sort)

Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
Giải phóng thời gian, khai phóng năng lực

Sắp xếp vun đống (Heap Sort) là một kỹ thuật sắp xếp phân loại dựa trên một cấu trúc dữ liệu được gọi là đống nhị phân (binary heap), gọi đơn giản là đống. Nó tương tự như thuật toán Sắp xếp chọn (Selection Sort) nơi phần tử lớn nhất sẽ được xếp vào cuối danh sách. Lặp đi lặp lại các bước này cho các phần tử còn lại của danh sách.

Phân loại: Thuật toán sắp xếp
Cấu trúc dữ liệu: Mảng
Hiệu suất trường hợp xấu nhất: O(nlogn)
Hiệu suất trường hợp tốt nhất: O (nlogn) (các khóa riêng biệt) hoặc O(n) (các khóa bằng nhau)
Hiệu suất trung bình: O(nlogn)
Trường hợp phức tạp nhất về không gian: O(1)

Khái niệm đống nhị phân (binary heap)

Mỗi mảng a[1..n] có thể xem như một cây nhị phân gần đầy (có trọng số là các giá trị của mảng), với gốc ở phần tử thứ nhất, con bên trái của đỉnh a[i] là a[2*i] con bên phải là a[2*i+1] (nếu mảng bắt đầu từ 1 còn nếu mảng bắt đầu từ 0 thì hai nhánh con là a[2*i+1] và a[2*i+2]) (nếu 2*i ≤ n hoặc 2*i+1 ≤ n, khi đó các phần tử có chỉ số lớn hơn (int) (n/2) không có con, do đó là lá).

  • Một cây nhị phân, được gọi là đống cực đại nếu khóa của mọi nút không nhỏ hơn khóa các con của nó. Khi biểu diễn một mảng a[ ] bởi một cây nhi phân theo thứ tự tự nhiên điều đó nghĩa là a[i] ≥ a[2*i] và a[i] ≥ a[2*i+1] với mọi i =1..int(n/2). Ta cũng sẽ gọi mảng như vậy là đống. Như vậy trong đống a[1] (ứng với gốc của cây) là phần tử lớn nhất. Mảng bất kỳ chỉ có một phần tử luôn luôn là một đống.
  • Một đống cực tiểu được định nghĩa theo các bất đẳng thức ngược lại: a[i] ≤ a[2*i] và a[i] ≤ a[2*i+1]. Phần tử đứng ở gốc cây cực tiểu là phần tử nhỏ nhất.

Kỹ thuật vun đống

Việc sắp xếp lại các phần tử của một mảng ban đầu sao cho nó trở thành đống được gọi là vun đống.

Vun đống tại đỉnh thứ i

Nếu hai cây con gốc 2*i và 2*i+1 đã là đống thì để cây con gốc i trở thành đống chỉ việc so sánh giá trị a[i] với giá trị lớn hơn trong hai giá trị a[2*i] và a[2*i+1], nếu a[i] nhỏ hơn thì đổi chỗ chúng cho nhau. Nếu đổi chỗ cho a[2*i], tiếp tục so sánh với con lớn hơn trong hai con của nó cho đên khi hoặc gặp đỉnh lá.

Vun một mảng thành đống

Để vun mảng a[1..n] thành đống ta vun từ dưới lên, bắt đầu từ phần tử a[j] với j = Int (n/2) ngược lên tới a[1].

Sắp xếp bằng vun đống

  • Đổi chỗ (Swap): Sau khi mảng a[1..n] đã là đống, lấy phần tử a[1] trên đỉnh của đống ra khỏi đống đặt vào vị trí cuối cùng n, và chuyển phần tử thứ cuối cùng a[n] lên đỉnh đống thì phần tử a[n] đã được đứng đúng vị trí.
  • Vun lại: Phần còn lại của mảng a[1..n-1] chỉ khác cấu trúc đống ở phần tử a[1]. Vun lại mảng này thành đống với n-1 phần tử.
  • Lặp: Tiếp tục với mảng a[1..n-1]. Quá trình dừng lại khi đống chỉ còn lại một phần tử.

Ví dụ

Ví dụ 01: Cho mảng a=(2,3,5,6,4,1,7), Ở đây n = 7. Các phần tử từ a[4] đến a[7] là lá.

Tạo đống

  • Vun cây gốc a[3] ta được mảng a=(2,3,7,6,4,1,5)
  • Vun cây gốc a[2] ta được mảng a=(2,6,7,3,4,1,5)
  • Vun cây gốc a[1] ta được mảng a=(7,6,5,3,4,1,2)

Bây giờ a=(7,6,5,3,4,1,2) đã là đống.

Sắp xếp vun đống

  1. Đổi chỗ a[1] với a[7]: a=(2,6,5,3,4,1,7) và vun lại mảng a[1..6] ta được mảng a=(6,4,5,3,2,1,7)
  2. Đổi chỗ a[1] với a[6]: a=(1,4,5,3,2,6,7) và vun lại mảng a[1..5] ta được mảng a=(5,4,1,3,2,6,7)
  3. Đổi chỗ a[1] với a[5]: a=(1,4,2,3,5,6,7) và vun lại mảng a[1..4] ta được mảng a=(4,3,1,2,5,6,7)
  4. Đổi chỗ a[1] với a[4]: a=(1,3,2,4,5,6,7) và vun lại mảng a[1..3] ta được mảng a=(3,2,1,4,5,6,7)
  5. Đổi chỗ a[1] với a[3]: a=(2,1,3,4,5,6,7) và vun lại mảng a[1..2] ta được mảng a=(2,1,3,4,5,6,7)
  6. Đổi chỗ a[1] với a[2]:a=(1,2,3,4,5,6,7) Mảng còn lại chỉ một phần tử.
  7. Quá trình sắp xếp đã xong.

Ví dụ 02: Sắp xếp mảng { 6, 5, 3, 1, 8, 7, 2, 4 } từ nhỏ đến lớn sử dụng phương pháp vun đống

Tạo đống

Đống Phần tử mới được thêm vào Đổi chỗ phần tử
null 6  
6 5  
6, 5 3  
6, 5, 3 1  
6, 5, 3, 1 8  
6, 5, 3, 1, 8   5, 8
68, 3, 1, 5   6, 8
8, 6, 3, 1, 5 7  
8, 6, 3, 1, 5, 7   3, 7
8, 6, 7, 1, 5, 3 2  
8, 6, 7, 1, 5, 3, 2 4  
8, 6, 7, 1, 5, 3, 2, 4   1, 4
8, 6, 7, 4, 5, 3, 2, 1    

Sắp xếp (vun đống)

Heap Phần tử hoán đổi Xóa phần tử Mảng sắp xếp Chi tiết
8 , 6, 7, 4, 5, 3, 2, 1 8, 1     hoán đổi 8 và 1 để xóa 8 từ đống
1, 6, 7, 4, 5, 3, 2, 8   số 8   xóa 8 từ heap và thêm vào mảng đã sắp xếp
1 , 6, 7 , 4, 5, 3, 2 1, 7   số 8 hoán đổi 1 và 7 vì chúng không theo thứ tự trong đống
7, 6, 1 , 4, 5, 3 , 2 1, 3   số 8 hoán đổi 1 và 3 vì chúng không theo thứ tự trong đống
7 , 6, 3, 4, 5, 1, 2 7, 2   số 8 hoán đổi 7 và 2 để xóa 7 từ đống
2, 6, 3, 4, 5, 1, 7   7 số 8 xóa 7 từ heap và thêm vào mảng đã sắp xếp
2 , 6 , 3, 4, 5, 1 2, 6   7, 8 hoán đổi 2 và 6 vì chúng không theo thứ tự trong đống
6, 2 , 3, 4, 5 , 1 2, 5   7, 8 hoán đổi 2 và 5 vì chúng không theo thứ tự trong đống
6 , 5, 3, 4, 2, 1 6, 1   7, 8 hoán đổi 6 và 1 để xóa 6 từ đống
1, 5, 3, 4, 2, 6   6 7, 8 xóa 6 từ heap và thêm vào mảng đã sắp xếp
1 , 5 , 3, 4, 2 1, 5   6, 7, 8 hoán đổi 1 và 5 vì chúng không theo thứ tự trong đống
5, 1 , 3, 4 , 2 1, 4   6, 7, 8 hoán đổi 1 và 4 vì chúng không theo thứ tự trong đống
5 , 4, 3, 1, 2 5, 2   6, 7, 8 hoán đổi 5 và 2 để xóa 5 từ đống
2, 4, 3, 1, 5   5 6, 7, 8 xóa 5 từ heap và thêm vào mảng đã sắp xếp
2 , 4 , 3, 1 2, 4   5, 6, 7, 8 hoán đổi 2 và 4 vì chúng không theo thứ tự trong đống
4 , 2, 3, 1 4, 1   5, 6, 7, 8 hoán đổi 4 và 1 để xóa 4 từ đống
1, 2, 3, 4   4 5, 6, 7, 8 xóa 4 từ heap và thêm vào mảng đã sắp xếp
1 , 2, 3 1, 3   4, 5, 6, 7, 8 hoán đổi 1 và 3 vì chúng không theo thứ tự trong đống
3 , 2, 1 3, 1   4, 5, 6, 7, 8 hoán đổi 3 và 1 để xóa 3 từ đống
1, 2, 3   3 4, 5, 6, 7, 8 xóa 3 từ heap và thêm vào mảng đã sắp xếp
1 , 2 1, 2   3, 4, 5, 6, 7, 8 hoán đổi 1 và 2 vì chúng không theo thứ tự trong đống
2 , 1 2, 1   3, 4, 5, 6, 7, 8 hoán đổi 2 và 1 để xóa 2 từ đống
1, 2   2 3, 4, 5, 6, 7, 8 xóa 2 từ heap và thêm vào mảng đã sắp xếp
1   1 2, 3, 4, 5, 6, 7, 8 xóa 1 từ heap và thêm vào mảng đã sắp xếp
      1, 2, 3, 4, 5, 6, 7, 8 hoàn thành

 

 

Heap Sort
Hình ảnh minh hoạ cho Ví dụ 02 thuật toán sắp xếp vun đống

Sắp xếp vun đống trong lập trình C++

Sắp xếp một mảng arr[] = {12, 11, 13, 5, 6, 7} theo thứ tự tăng dần sử dụng phương pháp vun đống bằng ngôn ngữ lập trình C++.

#include<bits/stdc++.h>
using namespace std;

// Vun đống một cây con có nút gốc (root) là i
// n là kích thước của đống
void heapify(int arr[], int n, int i) {
  int largest = i; // khởi tạo largest là gốc
  int left = 2 * i + 1; // left = 2*i + 1
  int right = 2 * i + 2; // right = 2*i + 2

  // nếu nút con trái lớn hơn so với gốc
  if (left < n && arr[left] > arr[largest])
    largest = left;

  // nếu nút con phải lớn hơn so với gốc
  if (right < n && arr[right] > arr[largest])
    largest = right;

  // nếu gốc không phải là lớn nhất
  if (largest != i){
    swap(arr[i], arr[largest]);

    // đệ quy lại hàm heapify()
    heapify(arr, n, largest);
  }
}

// Hàm vun đống
void heapSort(int arr[], int n){
  // tạo một đống (sắp xếp lại mảng)
  for (int i = n / 2 - 1; i >= 0; i--)
    heapify(arr, n, i);

  // trích xuất từng phần tử một từ heap
  for (int i = n - 1; i >= 0; i--){
    // di chuyển gốc về cuối
    swap(arr[0], arr[i]);

    // gọi hàm heapify
    heapify(arr, i, 0);
  }
}

void printArray(int arr[], int n){
  for (int i = 0; i<n; ++i)
    cout << arr[i] << " ";
  cout << endl;
}

int main(){
  int arr[] = { 12, 11, 13, 5, 6, 7 };
  int n = sizeof(arr) / sizeof(arr[0]);

  heapSort(arr, n);

  cout << "Sau khi sap xep tang dan, ta duoc mang:" << endl;
  printArray(arr, n);

  return 0;
}
» Tiếp: Vector
« Trước: Tìm kiếm nhị phân (Binary Search)
Các khóa học qua video:
Python SQL Server PHP C# Lập trình C Java HTML5-CSS3-JavaScript
Học trên YouTube <76K/tháng. Đăng ký Hội viên
Viết nhanh hơn - Học tốt hơn
Giải phóng thời gian, khai phóng năng lực
Copied !!!