Нужно реализовать алгоритм Фибоначчиевой кучи, в этом коде показывает кучу ошибок. И они по сути связаны со структурой fib_heap. Код пыталась найти, так как для меня это очень сложно реализовать такое
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| #include "stdafx.h"
#include <conio.h>
#include <iostream>
using namespace std;
typedef bool(*cmpPtr)(node*, node*);
struct node {
node* parent; // указатель на отца
node* child; // указатель на одного из сыновей
node* left; // указатель на левого брата
node* right; // указатель на правого брата
int degree; // количество дочерних узлов
bool mark; // метка - был ли удален один из дочерних элементов
int key; // числовое значение узла
};
struct fib_heap {
node* min; // узел с минимальным корнем
int roots_amount; // количество узлов
cmpPtr less; // указатель на функцию-компаратор
};
void add(node* Node, node** bro, node* par = NULL) //добавление нового элемента
{
if (*bro == NULL) {
*bro = Node;
Node->left = Node;
Node->right = Node;
}
else {
Node->right = (*bro)->right;
Node->right->left = Node;
Node->left = *bro;
(*bro)->right = Node;
}
if (less(Node, *bro))
*bro = Node;
if (*bro == min) {
roots_amount++;
Node->parent = NULL;
}
if (par) {
par->degree++;
Node->parent = par;
}
}
node* add(int key) {
node* Node = new node(key);
add(Node, &min);
return Node;
}
struct fib_heap //объеденение двух фибоначчиевых куч
{
void union_fib_heap(fib_heap &fb) {
union_root(fb.min, fb.roots_amount);
if (!min || (fb.min && less(fb.min, min)))
min = fb.min;
fb.clear();
}
void union_root(node* Node, int nodes_amount) {
if (Node == NULL) return;
if (min == NULL) {
min = Node;
roots_amount = nodes_amount;
}
else {
node *L = Node->left;
node *R = min->right;
min->right = Node;
Node->left = min;
L->right = R;
R->left = L;
roots_amount += nodes_amount;
}
}
};
int extract_min() //удаление минимального дерева
{
node* res = min;
if (res) {
childs_in_root(res);
remove_root(res);
if (res->right == res)
min = 0;
else {
min = min->right;
consolidate();
}
}
int ans = res ? res->key : ERROR;
delete res;
return ans;
}
int main()
{
_getch();
return 0;
} |
|
(
