std::is_heap

#include <algorithm>

// Kiểm tra max heap theo mặc định sử dụng toán tử <
template <class RandomAccessIterator>
bool is_heap (RandomAccessIterator first, RandomAccessIterator last);

// Kiểm tra heap theo tiêu chí so sánh tùy chỉnh
template <class RandomAccessIterator, class Compare>
bool is_heap (RandomAccessIterator first, RandomAccessIterator last,
              Compare comp);

Kiểm tra xem một phạm vi (range) có phải là max heap hay không (theo mặc định) hoặc có thỏa mãn tiêu chí heap tùy chỉnh (sử dụng hàm so sánh) hay không. 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 kiểm tra.

`last`

Random Access Iterator trỏ đến phần tử ngay sau phần tử cuối cùng trong phạm vi cần kiểm tra. 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ề

`true`

Nếu phạm vi là một heap hợp lệ (max heap theo mặc định hoặc theo tiêu chí so sánh comp).

`false`

Nếu phạm vi không phải là một heap hợp lệ.

Đặc điểm

Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
is_heap() không thay đổi phạm vi đầu vào.
is_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ử.
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.
Một phạm vi rỗng hoặc chỉ có một phần tử luôn được coi là một heap hợp lệ.
is_heap() thường được sử dụng để:
- Kiểm tra xem dữ liệu trong một container có đang được tổ chức dưới dạng heap hay không trước khi thực hiện các thao tác khác (ví dụ: push_heap(), pop_heap(), sort_heap()).
- Xác minh tính hợp lệ của dữ liệu đầu vào.
- Kiểm tra kết quả của các thuật toán tạo heap như make_heap().

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

make_heap() tạo một heap từ một phạm vi chưa phải là 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 (hoán đổi với phần tử cuối và thu hẹp phạm vi heap).
is_heap() kiểm tra xem toàn bộ phạm vi có phải là heap hay không.
is_heap_until() tìm vị trí phần tử đầu tiên làm mất tính chất heap của phạm vi.

Ví dụ

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

// Hàm so sánh để kiểm tra min heap
bool compareGreaterThan(int a, int b) {
  return a > b;
}

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

  // Kiểm tra maxHeap (max heap)
  if (std::is_heap(maxHeap.begin(), maxHeap.end())) {
    std::cout << "maxHeap is a max heap.\n";
  } else {
    std::cout << "maxHeap is not a max heap.\n";
  }

  // Kiểm tra minHeap (min heap) sử dụng compareGreaterThan
  if (std::is_heap(minHeap.begin(), minHeap.end(), compareGreaterThan)) {
    std::cout << "minHeap is a min heap.\n";
  } else {
    std::cout << "minHeap is not a min heap.\n";
  }

  // Kiểm tra notHeap (không phải heap)
  if (std::is_heap(notHeap.begin(), notHeap.end())) {
    std::cout << "notHeap is a max heap.\n";
  } else {
    std::cout << "notHeap is not a max heap.\n";
  }

  return 0;
}

Các hàm liên quan


is_heap_until	Tìm vị trí phần tử đầu tiên trong một phạm vi mà từ vị trí đó trở đi, phạm vi không còn là một max heap hoặc không còn thỏa mãn tiêu chí heap tùy chỉnh
make_heap	Biến đổi một phạm vi tùy ý thành một 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)

Tham số​

first​

last​

comp​

Giá trị trả về​

true​

false​

Đặc điểm​

Ví dụ​

Các hàm liên quan​