std::push_heap

#include <algorithm>

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

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

Thêm một phần tử vào cuối của một max heap (được biểu diễn dưới dạng một phạm vi - range) và điều chỉnh lại heap để duy trì tính chất của max heap. Trong max heap, phần tử ở gốc (đầu) luôn là phần tử lớn nhất. Lưu ý push_heap giả định rằng phạm vi đã cho trước đó (ngoại trừ phần tử mới thêm vào cuối) đã là một max heap hợp lệ.

Tham số

`first`

Random Access Iterator trỏ đến phần tử đầu tiên trong phạm vi đã là max heap (ngoại trừ phần tử mới có thể được thêm vào cuối).

`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 bao gồm cả phần tử mới được thêm vào cuối. 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.
push_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.
push_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 [first, last - 1) phải là một max heap hợp lệ trước khi gọi push_heap(). push_heap() chỉ xử lý phần tử mới được thêm vào cuối (tại vị trí last - 1).
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.
push_heap() thường được sử dụng trong các trường hợp sau:
- Thêm một phần tử vào cuối một max heap đã tồn tại:
  - Đầu tiên, bạn thêm phần tử mới vào cuối container (ví dụ: sử dụng vector::push_back()).
  - Sau đó, bạn gọi push_heap() để điều chỉnh lại heap, đảm bảo phần tử mới được đặt vào đúng vị trí để duy trì tính chất của max heap.
- Xây dựng một heap từ đầu:
  - Bạn có thể bắt đầu với một container rỗng.
  - Sau đó, lần lượt thêm từng phần tử vào cuối container và gọi push_heap() sau mỗi lần thêm để xây dựng dần dần một max heap.

Phân biệt với make_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.
pop_heap() loại bỏ phần tử lớn nhất (phần tử đầu tiên) khỏi heap và điều chỉnh lại heap (thường được sử dụng để triển khai Heap Sort).
push_heap() thêm một phần tử vào cuối heap và điều chỉnh lại heap.

Ví dụ

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

int main() {
  std::vector<int> heap = {9, 7, 5, 2, 6, 4}; // Một max heap

  // Thêm số 8 vào cuối heap
  heap.push_back(8);

  // Điều chỉnh lại heap sau khi thêm phần tử mới
  std::push_heap(heap.begin(), heap.end());

  std::cout << "Heap after push_heap: ";
  for (int x : heap) {
    std::cout << x << " ";
  }
  std::cout << std::endl;
    
  // Tạo một heap rỗng
  std::vector<int> myHeap;
    
  // Thêm các phần tử vào và dùng push_heap để tạo heap
  myHeap.push_back(3);
  std::push_heap(myHeap.begin(), myHeap.end());
  myHeap.push_back(8);
  std::push_heap(myHeap.begin(), myHeap.end());
  myHeap.push_back(2);
  std::push_heap(myHeap.begin(), myHeap.end());
  myHeap.push_back(6);
  std::push_heap(myHeap.begin(), myHeap.end());

  std::cout << "myHeap after building: ";
  for (int x : myHeap) {
      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
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​