std::pop_heap

#include <algorithm>

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

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

Loại bỏ phần tử lớn nhất (phần tử đầu tiên) khỏi 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. Về bản chất, pop_heap không xóa phần tử, mà hoán đổi phần tử đầu tiên (lớn nhất) với phần tử cuối cùng trong phạm vi, sau đó điều chỉnh lại heap trên phạm vi mới không bao gồm phần tử cuối, coi như phần tử lớn nhất đã được "lấy" ra.

Tham số

`first`

Random Access Iterator trỏ đến phần tử đầu tiên trong phạm vi là 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.
pop_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.
pop_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) phải là một max heap hợp lệ trước khi gọi pop_heap().
Sau khi gọi pop_heap(), phạm vi [first, last - 1) là một max heap hợp lệ. Phần tử tại vị trí last - 1 (ban đầu là phần tử đầu tiên) không còn thuộc về 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.
pop_heap() thường được sử dụng trong các trường hợp sau:
- Lấy phần tử lớn nhất ra khỏi max heap:
  - Gọi pop_heap(first, last) để hoán đổi phần tử đầu tiên (lớn nhất) với phần tử cuối cùng và điều chỉnh lại heap trên phạm vi [first, last - 1).
  - Phần tử lớn nhất lúc này đã nằm ở cuối phạm vi (vị trí last - 1). Bạn có thể truy cập hoặc xóa nó khỏi container (ví dụ: sử dụng vector::pop_back()) nếu cần.
- Triển khai thuật toán Heap Sort:
  - pop_heap() được sử dụng repeatedly để trích xuất lần lượt các phần tử lớn nhất và thu hẹp dần phạm vi heap cho đến khi toàn bộ phạm vi được sắp xếp.

Phân biệt với push_heap() và make_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>

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

  // Hoán đổi phần tử đầu tiên (lớn nhất) với phần tử cuối cùng và điều chỉnh lại heap
  std::pop_heap(heap.begin(), heap.end());

  std::cout << "Heap after pop_heap: ";
  for (int i = 0; i < heap.size(); ++i) {
    std::cout << heap[i] << " ";
  }
  std::cout << std::endl;

  // Lấy phần tử lớn nhất ra khỏi heap (đã nằm ở cuối sau khi gọi pop_heap)
  int largest = heap.back();
  heap.pop_back();

  std::cout << "Largest element: " << largest << std::endl;
  std::cout << "Heap after removing largest element: ";
  for (int x : heap) {
    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
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​