#include <iostream>
const int d = 3; /*Арность кучи*/
/*Реализация функций перестроения бинарной кучи*/
template <class Item>
void fixUp(Item a[], int node){
while(node > 1 && a[node/2] < a[node]){
std::swap(a[node], a[node/2]);
node = node / 2;
}
}
template <class Item>
void fixDown(Item a[], int node, int n){
while(2*node <= n){
int j = 2*node;
if(j < n && a[j] < a[j + 1]) j++;
if(!(a[node] < a[j])) break;
std::swap(a[node], a[j]);
node = j;
}
}
/*Реализация функций перестроения d-арной кучи*/
/*
first_child = node * d + 1 - (d - 1)
last_child = node * d + 1
parent = (node + d - 2) / d
*/
template <class Item>
void d_ary_fixUp(Item a[], int node){
while(node > 1 && a[(node + d - 2)/d] < a[node]){
std::swap(a[node], a[(node + d - 2)/d]);
node = (node + d - 2) / d;
}
}
template <class Item>
void d_ary_fixDown(Item a[], int node, int n){
int first_child = node*d + 1 - (d - 1);
int last_child = node*d + 1;
int max_child = first_child; /*Начнем с самого первого*/
while(d*node <= n){
/*Находим максимального потомка*/
for(int i = first_child; i <= last_child; i++)
if(a[i] > a[max_child])
max_child = i;
/*Если он больше родителя, меняем их местами*/
if(a[max_child] > a[(max_child + d - 2) / d])
std::swap(a[max_child], a[(max_child + d - 2) / d]);
node = max_child;
}
}
template <class Item>
void d_ary_fixDown2(Item a[], int node, int n){
int first_child = node*d + 1 - (d - 1);
int last_child = node*d + 1;
int max_child = first_child; /*Начнем с самого первого*/
while(node*d + 1 - (d - 1) <= n){
int j = node*d + 1 - (d - 1);
/*Ищем максимального потомка среди всех d потомков узла node*/
for(int i = first_child; i <= last_child; i++)
if(a[i] > a[max_child])
max_child = i;
/*Если потомок max_child больше своего родителя, то меняем их местами*/
if(a[max_child] > a[(max_child + d - 2) / d])
std::swap(a[max_child], a[(max_child + d - 2) / d]);
node = j;
int first_child = node*d + 1 - (d - 1);
int last_child = node*d + 1;
int max_child = first_child;
}
}
template <class Item>
class PQ{
private:
Item *pq;
int n;
public:
PQ(int max){
pq = new Item[max + 1];
n = 0;
}
~PQ(){
delete[] pq;
}
int empty() const{
return n == 0;
}
void insert(Item item){
pq[++n] = item;
d_ary_fixUp(pq, n);
}
Item getmax(){
if(!empty()){
std::swap(pq[1], pq[n]);
d_ary_fixDown2(pq, 1, n-1);
return pq[n--];
}else
return 0;
}
};
int main(){
PQ<int> pq(50);
int p;
for(int i = 0; i < 10; i++)
pq.insert(i);
for(int i = 0; i < 10; i++)
std::cout << pq.getmax() << " ";
std::cin >> p;
}