Heap trong C ++ STL - make_heap (), push_heap (), pop_heap (), sort_heap (), is_heap, is_heap_until ()

Trong phần này, chúng ta sẽ thấy cấu trúc dữ liệu heap có trong C ++ STL. Điều này cho phép nhập vào heap nhanh hơn và việc truy xuất một số luôn dẫn đến số lớn nhất, tức là số lớn nhất trong số các số còn lại được xuất hiện mỗi lần. Các yếu tố khác của đống được sắp xếp tùy thuộc vào việc triển khai. Các hoạt động đống như sau -

• make_heap () - Điều này chuyển đổi một phạm vi trong vùng chứa thành một đống.

• front () - Điều này trả về phần tử đầu tiên của đống là số lớn nhất.

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include<bits/stdc++.h>
using namespace std;
int main() {
   vector<int> heap = {33, 43, 53, 38, 28};
   make_heap(heap.begin(), heap.end());
   cout <<"Top element is : " << heap.front() << endl;
}

Đầu ra

Top element is : 53

• push_heap () - Điều này giúp sắp xếp lại heap sau khi chèn một phần tử vào heap. Kích thước của heap được tăng lên 1. Trong heap, phần tử mới được đặt một cách thích hợp.

• pop_heap () - Điều này giúp sắp xếp lại đống sau khi xóa phần tử lớn nhất của đống. Kích thước của heap giảm đi 1. Sau khi xóa một phần tử, các phần tử trong heap được sắp xếp lại cho phù hợp.

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include<bits/stdc++.h>
using namespace std;
int main() {
   vector<int> heap = {33, 43, 53, 38, 28};
   make_heap(heap.begin(), heap.end());
   cout <<"Top element is : " << heap.front() << endl;
   heap.push_back(60);
   push_heap(heap.begin(), heap.end());
   cout <<"Top element after insert : " << heap.front() << endl;
   pop_heap(heap.begin(), heap.end());
   heap.pop_back();
   cout <<"Top element after deletion : " << heap.front() << endl;
}

Đầu ra

Top element is : 53
Top element after insert : 60
Top element after deletion : 53

• sort_heap ():Thao tác này sắp xếp phần tử đống theo thứ tự tăng dần bằng kỹ thuật phân loại.

Ví dụ (C ++)

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include<bits/stdc++.h>
using namespace std;
int main() {
   vector<int> heap = {33, 43, 53, 38, 28};
   make_heap(heap.begin(), heap.end());
   cout <<"Before Sort : ";
   for (const auto &i : heap) {
      cout << i << ' ';
   }
   sort_heap(heap.begin(), heap.end());
   cout <<"\nAfter Sort : ";
   for (const auto &i : heap) {
      cout << i << ' ';
   }
}

Đầu ra

Before Sort : 53 43 33 38 28
After Sort : 28 33 38 43 53

• is_heap () - Điều này được sử dụng để kiểm tra xem container có phải là một đống hay không. Trong hầu hết các triển khai, vùng chứa được sắp xếp ngược lại được coi là đống. Hàm này trả về true heap khi đây là heap, nếu không thì false.

• is_heap_until () - Điều này được sử dụng để tìm trình lặp đến vị trí cho đến khi vùng chứa là đống.

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#include<bits/stdc++.h>
using namespace std;
int main() {
   vector<int> heap = {33, 43, 53, 38, 28};
   vector<int>::iterator iter;
   is_heap(heap.begin(), heap.end()) ? cout <<"The is a heap ": cout <<"The is not a heap";
   cout << endl;
   cout < "Heapify" << endl;
   make_heap(heap.begin(), heap.end());
   is_heap(heap.begin(), heap.end()) ? cout <<"The is a heap ": cout <<"The is not a heap";
   cout << endl;
   vector<int>::iterator iter2 = is_heap_until(heap.begin(), heap.end());
   cout <<"The heap elements are : ";
   for (iter=heap.begin(); iter!=iter2; iter++)
      cout << *iter <<" ";
}

Đầu ra

The is not a heap
Heapify
The is a heap
The heap elements are : 53 43 33 38 28