Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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])
- if(a[max_child] > a[node])
- 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;
- }
- }
- 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;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement