std::sort_heap

#include <algorithm>

// Sắp xếp tăng dần theo mặc định sử dụng toán tử <
template <class RandomAccessIterator>
void sort_heap (RandomAccessIterator first, RandomAccessIterator last);

// Sắp xếp theo tiêu chí so sánh tùy chỉnh
template <class RandomAccessIterator, class Compare>
void sort_heap (RandomAccessIterator first, RandomAccessIterator last,
                Compare comp);

Sắp xếp một phạm vi (range) đã là max heap thành một dãy tăng dần (hoặc theo tiêu chí so sánh khác). Về bản chất, sort_heap thực hiện thuật toán Heap Sort trên max heap đầu vào.

Tham số

first

• Random Access Iterator trỏ đến phần tử đầu tiên trong phạm vi đã là max heap cần sắp xếp.

last

• Random Access Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi. Phạm vi là [first, last).

comp

• Một hàm hoặc đối tượng hàm (comparator) nhận hai đối số (hai phần tử trong phạm vi) và trả về true nếu phần tử thứ nhất được coi là nhỏ hơn phần tử thứ hai theo tiêu chí so sánh, false nếu ngược lại. (Phiên bản 2)

Giá trị trả về

Không có giá trị trả về

Đặc điểm

1. Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
2. sort_heap() thay đổi trực tiếp thứ tự các phần tử trong phạm vi gốc, không tạo ra một phạm vi mới.
3. sort_heap() yêu cầu Random Access Iterator, cho phép truy cập ngẫu nhiên vào các phần tử.
4. Phạm vi đầu vào [first, last) phải là một max heap hợp lệ (hoặc min heap nếu sử dụng comp để so sánh giảm dần) trước khi gọi sort_heap().
5. Trong C++11 trở lên, bạn có thể sử dụng biểu thức lambda cho hàm so sánh comp (phiên bản 2) để code ngắn gọn và dễ đọc hơn.
6. sort_heap() sử dụng chính tính chất của max heap để sắp xếp. Nó liên tục lấy phần tử lớn nhất (phần tử đầu tiên) ra khỏi heap, hoán đổi nó với phần tử cuối cùng, thu hẹp phạm vi heap lại, và điều chỉnh lại heap (sử dụng pop_heap logic). Quá trình này lặp lại cho đến khi toàn bộ phạm vi được sắp xếp. Độ phức tạp thời gian của sort_heap() là O(n log n), trong đó n là số phần tử trong phạm vi.
7. sort_heap() sắp xếp trực tiếp trên phạm vi đầu vào, không yêu cầu thêm không gian lưu trữ đáng kể.
8. sort_heap() thường được sử dụng khi:
   • Bạn đã có dữ liệu được tổ chức dưới dạng max heap và bạn muốn sắp xếp nó thành dãy tăng dần.
   • Bạn đang triển khai thuật toán Heap Sort.

Phân biệt với sort(), stable_sort(), make_heap(), push_heap(), và pop_heap()

• sort() và stable_sort() sắp xếp các phạm vi bất kỳ (không yêu cầu là heap).
• make_heap() biến đổi một phạm vi thành heap.
• push_heap() thêm một phần tử vào heap.
• pop_heap() "loại bỏ" phần tử lớn nhất khỏi heap (hoán đổi với phần tử cuối và thu hẹp phạm vi heap).
• sort_heap() sắp xếp một phạm vi đã là heap.

Ví dụ

#include <iostream>
#include <vector>
#include <algorithm>

// Hàm so sánh để sắp xếp giảm dần
bool compareDescending(int a, int b) {
  return a > b;
}

int main() {
  std::vector<int> numbers = {9, 7, 5, 2, 6, 4, 1, 8, 3};

  // Biến đổi numbers thành max heap
  std::make_heap(numbers.begin(), numbers.end());

  std::cout << "Max heap: ";
  for (int x : numbers) {
    std::cout << x << " ";
  }
  std::cout << std::endl;

  // Sắp xếp heap thành dãy tăng dần
  std::sort_heap(numbers.begin(), numbers.end());

  std::cout << "numbers after sort_heap (ascending): ";
  for (int x : numbers) {
    std::cout << x << " ";
  }
  std::cout << std::endl;

  std::vector<int> numbers2 = {9, 7, 5, 2, 6, 4, 1, 8, 3};
    
  // Tạo min heap cho dãy giảm dần
  std::make_heap(numbers2.begin(), numbers2.end(), compareDescending);

  // Sắp xếp heap thành dãy giảm dần
  std::sort_heap(numbers2.begin(), numbers2.end(), compareDescending);

  std::cout << "numbers2 after sort_heap (descending): ";
  for (int x : numbers2) {
      std::cout << x << " ";
  }
  std::cout << std::endl;

  return 0;
}

Các hàm liên quan

make_heap	Biến đổi một phạm vi tùy ý thành một max heap
push_heap	Thêm một phần tử vào cuối của một max heap và điều chỉnh lại heap để duy trì tính chất của max heap
pop_heap	Loại bỏ phần tử lớn nhất khỏi một max heap và điều chỉnh lại heap để duy trì tính chất của max heap
reverse	Đảo ngược thứ tự các phần tử trong một phạm vi được chỉ định