std::make_heap

#include <algorithm>

// So sánh bằng toán tử <
template <class RandomAccessIterator>
void make_heap (RandomAccessIterator first, RandomAccessIterator last);

// Sử dụng hàm so sánh tùy chỉnh
template <class RandomAccessIterator, class Compare>
void make_heap (RandomAccessIterator first, RandomAccessIterator last,
                Compare comp);

Biến đổi một phạm vi (range) tùy ý thành một max heap. Trong max heap, phần tử ở gốc (đầu) luôn là phần tử lớn nhất, và cây con của mỗi nút cũng là max heap.

Tham số

`first`

Random Access Iterator trỏ đến phần tử đầu tiên trong phạm vi cần biến đổi thành max heap.

`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 (để tạo max heap), 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

Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
make_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.
make_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ử.
Phạm vi đầu vào không cần phải được sắp xếp trước khi gọi make_heap().
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.
make_heap() thường sử dụng thuật toán Floyd's algorithm (hay còn gọi là heapify hoặc build heap) để xây dựng heap từ dưới lên (bottom-up). Độ phức tạp thời gian của make_heap() là O(n), trong đó n là số phần tử trong phạm vi.
make_heap() biến đổi phạm vi đầu vào thành heap tại chỗ, không yêu cầu thêm không gian lưu trữ đáng kể.
make_heap() thường được sử dụng để:
- Khởi tạo một max heap từ một mảng hoặc một container chưa được sắp xếp.
- Chuẩn bị dữ liệu cho các thuật toán sử dụng heap như Heap Sort hoặc priority queue.

Phân biệt với push_heap() và pop_heap()

make_heap() biến đổi một phạm vi chưa phải là heap thành một heap.
push_heap() thêm một phần tử vào cuối heap và điều chỉnh lại heap.
pop_heap() "loại bỏ" phần tử lớn nhất khỏi heap bằng cách hoán đổi nó với phần tử cuối cùng và điều chỉnh lại heap trên phạm vi mới (không bao gồm phần tử cuối).

Ví dụ

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

// Hàm so sánh để tạo min heap (phần tử nhỏ nhất ở đầu)
bool compareGreaterThan(int a, int b) {
  return a > b;
}

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

  // 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;

  std::vector<int> numbers2 = {3, 1, 4, 1, 5, 9, 2, 6};
    
  // Biến đổi numbers2 thành min heap sử dụng compareGreaterThan
  std::make_heap(numbers2.begin(), numbers2.end(), compareGreaterThan);

  std::cout << "Min heap: ";
  for (int x : numbers2) {
      std::cout << x << " ";
  }
  std::cout << std::endl;

  return 0;
}

Các hàm liên quan


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
sort_heap	Sắp xếp một phạm vi đã là max heap thành một dãy tăng dần (hoặc theo tiêu chí so sánh khác)
reverse	Đảo ngược thứ tự các phần tử trong một phạm vi được chỉ định

Tham số​

first​

last​

comp​

Giá trị trả về​

Đặc điểm​

Ví dụ​

Các hàm liên quan​