std::is_heap_until

#include <algorithm>

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

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

Tìm vị trí phần tử đầu tiên trong một phạm vi (range) mà từ vị trí đó trở đi, phạm vi không còn là một max heap (theo mặc định) hoặc không còn thỏa mãn tiêu chí heap tùy chỉnh (sử dụng hàm so sánh). Nói cách khác, nó tìm vị trí kết thúc của dãy con là max heap tính từ đầu phạm vi.

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ề

• Random Access Iterator trỏ đến phần tử đầu tiên trong phạm vi mà từ vị trí đó trở đi, phạm vi không còn là heap.
• Nếu toàn bộ phạm vi là heap, iterator trả về sẽ là last.

Đặc điểm

1. Phạm vi [first, last) là "nửa mở", không bao gồm phần tử last.
2. is_heap_until() không thay đổi phạm vi đầu vào.
3. is_heap_until() 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. 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.
5. is_heap_until() thường được sử dụng để:
   • Xác định phần đầu tiên của một phạm vi là heap.
   • Tìm vị trí bắt đầu của phần không phải là heap trong một phạm vi.
   • Kiểm tra xem một phần của container có phải là heap hay không.

Phân biệt với is_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> heap = {9, 7, 5, 2, 6, 4, 1, 8, 3}; // Bắt đầu là max heap

  // Tìm vị trí phần tử đầu tiên không thỏa mãn max heap
  auto it = std::is_heap_until(heap.begin(), heap.end());

  std::cout << "Max heap until index: " << (it - heap.begin()) << std::endl;
  if (it != heap.end())
      std::cout << "Value: " << *it << std::endl;

  std::vector<int> minHeap = {1, 3, 2, 4, 5, 6};
  // Tìm vị trí phần tử đầu tiên không thỏa mãn min heap (sử dụng compareGreaterThan)
  auto it2 = std::is_heap_until(minHeap.begin(), minHeap.end(), compareGreaterThan);
  std::cout << "Min heap until index: " << (it2 - minHeap.begin()) << std::endl;
  if (it2 != minHeap.end())
      std::cout << "Value: " << *it2 << std::endl;

  std::vector<int> fullHeap = {9, 8, 7, 6, 5, 4};
  // Kiểm tra fullHeap (là max heap hoàn chỉnh)
  auto it3 = std::is_heap_until(fullHeap.begin(), fullHeap.end());
  if (it3 == fullHeap.end()) {
    std::cout << "fullHeap is a complete max heap.\n";
  } else {
      std::cout << "fullHeap is not a complete max heap.\n";
  }

  return 0;
}

Các hàm liên quan

is_heap	Kiểm tra xem một phạm vi có phải là max heap hay không hoặc có thỏa mãn tiêu chí heap tùy chỉnh hay không
make_heap	Biến đổi một phạm vi tùy ý thành một max heap
is_sorted_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 được sắp xếp theo thứ tự tăng dần hoặc theo một tiêu chí so sánh tùy chỉnh