|
Mechanical Implementation of Priority Queues
|
| bet | 7/9 | | Sana | 24.05.2024 | | Hajmi | 0,71 Mb. | | #252108 |
Bog'liq Nishonova G (D2 M2)4.3 Mechanical Implementation of Priority Queues
Review the plug insertion and deletion.
Insertion of the heap: Adjust the data in the stacked tail, adjust the pile up.
Remove of a pile: Exchange the top elements and tail elements, and adjust the pile down.
Do not use the imitation function:
Adjust the function:
#pragma once
#include
#include
#include
#include
using namespace std;
namespace my{
template>
class priority_queue{
public:
priority_queue(){};
template
priority_queue(inputiterator first, inputiterator last){
while (first != last){
push(*first);
first++;
}
}
bool empty(){
return _con.empty();
}
size_t size(){
return _con.size();
}
T& top(){
return _con.front();
}
const T& top()const{
return _con.front();
}
void push(const T& val){
_con.push_back(val);
Adjustup(_con.size() - 1);
}
void pop(){
swap(_con[0], _con[_con.size() - 1]);
// Less an element is Size reduction, after exchange, delete the last element directly
_con.pop_back();
Adjustdown(0);
}
private:
void Adjustup(int child){
int parent = (child - 1) / 2;
while (child > 0){
if (_con[child] > _con[parent]){
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else{
break;
}
}
}
void Adjustdown(int parent){
int child = parent * 2 + 1;
/ / Can not be reduced, if there is no element size () is 0, type size_t, minus 1 is the maximum number (positive), will enter the loop
while ((size_t)child < _con. size() ){
if (child + 1 < _con.size() && _con[child + 1] > _con[child]){
child++;
}
if (_con[child]>_con[parent]){
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else{
break;
}
}
}
Container _con;
};
void test_priority_queue(){
int array[] = { 8, 4, 6, 2, 10 };
priority_queue pq(array, array + sizeof(array) / sizeof(int));
cout << pq.size() << endl;
while (!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
}
Imitation function: The priority queue achieves the establishment of large roots or small roots through the imitation function.
Adjusting the establishment of a large root or a small root, just changing the adjustment function. The father's node is more than smaller than less than that of the child. How to achieve it through the imitation function?
How to modify the adjustment function:
#pragma once
#include
#include
#include
#include
using namespace std;
namespace my{
template
struct less{
bool operator()(const T& left,const T& right){
return left < right;
}
};
template
struct greater{
bool operator()(const T& left, const T& right){
return left>right;
}
};
template,class Compare=less>
class priority_queue{
public:
priority_queue(){};
template
priority_queue(inputiterator first, inputiterator last){
while (first != last){
push(*first);
first++;
}
}
bool empty(){
return _con.empty();
}
size_t size(){
return _con.size();
}
T& top(){
return _con.front();
}
const T& top()const{
return _con.front();
}
void push(const T& val){
_con.push_back(val);
Adjustup(_con.size() - 1);
}
void pop(){
swap(_con[0], _con[_con.size() - 1]);
// Less an element is Size reduction, after exchange, delete the last element directly
_con.pop_back();
Adjustdown(0);
}
private:
void Adjustup(int child){
int parent = (child - 1) / 2;
Compare com;
while (child){
if (com(_con[parent],_con[child])){
swap(_con[child], _con[parent]);
child = parent;
parent = (child - 1) / 2;
}
else{
break;
}
}
}
void Adjustdown(int parent){
int child = parent * 2 + 1;
// Define an object
Compare com;
/ / Can not be reduced, if there is no element size () is 0, type size_t, minus 1 is the maximum number (positive), will enter the loop
while ((size_t)child < _con. size() ){
if (child + 1 < _con.size() && com(_con[child], _con[child + 1])){
child++;
}
if (com(_con[parent], _con[child])){
swap(_con[child], _con[parent]);
parent = child;
child = parent * 2 + 1;
}
else{
break;
}
}
}
Container _con;
};
void test_priority_queue(){
int array[] = { 8, 4, 6, 2, 10 };
priority_queue,greater> pq(array, array + sizeof(array) / sizeof(int));
cout << pq.size() << endl;
while (!pq.empty()){
cout << pq.top() << " ";
pq.pop();
}
cout << endl;
}
}
4. Konteynerlar bilan ishlaydigan algoritmlar.
Funktorlarni qo`llash
Konteynerlar bilan ishlash algoritmlari. Barcha konteynerlar umumiy yondashuvi tufayli, amalda qiziqtirgan asosiy algoritmlar konteynerlarning har qanday turi uchun qo‘llanilishi mumkin bo‘lgan umumiy shaklda amalga oshirilishi mumkinligi tufayli STL konteynerlar uzoq amaliy foydalanish uchun bir arzigulik ixtiro bo‘ldi.
Algoritmlar kutubxonaning eng katta va ommabop qismidir. Juda ko‘p algoritmlar mavjudki, ularning hammasini batafsil bayon qilish uchun katta kitob kerak. Quyida ularni guruhlarga ajratib, ularning nomlari bilan ataymiz (ularning hammasi emas) va ulardan faqat ayrimlari misol tariqasida keltiramiz.
for_each()algoritmi. for_each() eng ko‘p ishlatiladigan algoritmdir. Konteyner elementlar guruhi (ehtimol, barcha elementlari) uchun ketma-ket harakatni amalga oshiradi. U har qanday STL konteynerda foydalanish mumkin. Quyidagi 4.9-dasturda for_each() algoritm massiv va vektor uchun ishlatilgan.
4.9-dastur. for_each() algoritmidan foydalanish.
|
// Created by MBBahodir #include "stdafx.h" #include #include #include
using namespace std;
|
inline ostream& operator <<( ostream& out, const vector< unsigned > & obj ) { cout << "< ";
for( auto& p: obj ) cout << p << " ";
return out << ">";
}
void pow2( unsigned& i ) { i *= i; } int main( void ) {
const int examples = 4;
for( int i = 0; i < examples; i++ ) {
unsigned ai[] = { 1, 2, 3, 4 , 5, 6, 7, 8, 9 }, ni = sizeof( ai ) / sizeof( ai[ 0 ] );
vector< unsigned > vi( ai, ai + ni ); cout << vi;
switch( i ) { case 0:
for_each( vi.begin(), vi.end(), pow2 ); cout << " => " << vi << endl;
break; case 1:
for_each( ai, ai + ni, pow2 );
cout << " => " << vector< unsigned >( ai, ai + ni ) << endl; break;
case 2:
for( auto& i : ai ) pow2( i );
cout << " => " << vector< unsigned >( ai, ai + ni ) << endl; break;
case 3:
for_each( vi.begin() + 2, vi.end() - 2, pow2 ); cout << " => " << vi << endl;
break;
}
}
system("pause"); return 0;
}
|
|
4.9-dastur.Output.
|
< 1 2 3 4 5 6 7 8 9 > => < 1 4 9 16 25 36 49 64 81 >
|
< 1 2 3 4 5 6 7 8 9 > => < 1 4 9 16 25 36 49 64 81 >
< 1 2 3 4 5 6 7 8 9 > => < 1 4 9 16 25 36 49 64 81 >
< 1 2 3 4 5 6 7 8 9 > => < 1 2 9 16 25 36 49 8 9 >
|
Dasturning birinchi global (auto &x : ...) takrorlanish fragmenti ishlashini ko‘rsatilgan (C++11 standarti tomonidan joriy qilingan). Bu kabi fragmentni massivlar va konteynerlarga ham qo‘llanilishi mumkin (bu vektorni oqimga chiqarish operatori variant funksiyasida ko‘rsatilgan). Bu takrorlanish fragmenti aslida STL kutubxona yoki algoritmlarni qismi emas, lekin u for_each() algoritm bilan bir xil taʻsir ko‘rsatadi, yaʻni to‘plam barcha elementlar uchun izchil qo‘llash mumkin.
Bu yuqoridagi dastur barcha algoritmlarni berilgan interval asosida tashkiliy asosiy mantiq qismini ko‘rsatadi (shart emas, barcha konteynerlar). Boshi va oxiri bilan cheklangan iteratorga (ko‘pincha, birinchi berilgan 2 ta parametrlar) funksiya, funktor va predikat (bu funksiyalarga - qaysidir elementlari bo‘yicha saralash imkoni bo‘lsa va mantiqiy qiymat qaytaradigan funksiyalar kiradi) navbat bilan qo‘llaniladi.
Find(). Navbatdagi algoritm – bu find(). Bu nomidan maʻlumki, to‘plamdagi elementlarni qidirish funksyasidir. Eʻtibor bersak, juda ko‘p konteynerlar bunday find() – funksiyasiga ega va u obʻyekt uchun
|
| |
