ฮีปใน C++ STL - make_heap(), push_heap(), pop_heap(), sort_heap(), is_heap, is_heap_until()

ในส่วนนี้ เราจะเห็นโครงสร้างข้อมูลฮีปที่มีอยู่ใน C++ STL วิธีนี้ช่วยให้ป้อนข้อมูลในฮีปได้เร็วขึ้นและดึงข้อมูลตัวเลขได้เสมอส่งผลให้จำนวนที่มากที่สุด กล่าวคือ จำนวนที่ใหญ่ที่สุดของตัวเลขที่เหลือจะปรากฏขึ้นในแต่ละครั้ง มีการจัดเรียงองค์ประกอบอื่น ๆ ของฮีปซึ่งขึ้นอยู่กับการใช้งาน การทำงานของฮีปมีดังนี้ -

• make_heap() − สิ่งนี้จะแปลงช่วงในคอนเทนเนอร์เป็นฮีป

• ด้านหน้า() − ส่งคืนองค์ประกอบแรกของฮีปซึ่งเป็นจำนวนที่มากที่สุด

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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;
}

ผลลัพธ์

Top element is : 53

• push_heap() − สิ่งนี้ช่วยในการฮีปฮีปอีกครั้งหลังจากแทรกองค์ประกอบเข้าไปในฮีป ขนาดของฮีปเพิ่มขึ้น 1 ในฮีป องค์ประกอบใหม่จะถูกวางอย่างเหมาะสม

• pop_heap() − สิ่งนี้ช่วยในการฮีปฮีปอีกครั้งหลังจากลบองค์ประกอบที่ใหญ่ที่สุดของฮีป ขนาดของฮีปลดลง 1 หลังจากลบองค์ประกอบ องค์ประกอบฮีปจะได้รับการจัดระเบียบใหม่ตามนั้น

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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;
}

ผลลัพธ์

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

• sort_heap() :สิ่งนี้จะจัดเรียงองค์ประกอบฮีปในลำดับจากน้อยไปมากตามเทคนิคการจัดเรียงแบบแบ่งกลุ่ม

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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 << ' ';
   }
}

ผลลัพธ์

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

• is_heap() − ใช้เพื่อตรวจสอบว่าคอนเทนเนอร์นั้นเป็นฮีปหรือไม่ ในการใช้งานส่วนใหญ่ คอนเทนเนอร์ที่เรียงลำดับย้อนกลับจะถือเป็นฮีป ฟังก์ชันนี้จะคืนค่าฮีปจริงเมื่อเป็นฮีป มิฉะนั้นจะเป็นเท็จ

• is_heap_until() − ใช้เพื่อค้นหาตัววนซ้ำไปยังตำแหน่งจนกว่าคอนเทนเนอร์จะเป็นฮีป

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#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 <<" ";
}

ผลลัพธ์

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