STL中的斐波那契堆在哪里？ 如果STL没有实现斐波那契堆，使用现有算法和STL容器实现它的最佳实践是什么？
Fibonacci堆的STL实现？
10
- amin
2
1在维基百科上有一个C++实现（http://ideone.com/9jYnv），看起来相当不错。 - Rapptz
3可能是因为 STL 本身已经足够复杂，并且通常只提供最常用和最需要的功能。然而，像往常一样，boost 库中有这个功能：http://www.boost.org/doc/libs/1_49_0/doc/html/heap.html - Yuushi
4个回答
1
尽管标准库中没有斐波那契堆，但我编写了一个实现。
它在我写的一篇论文中使用，在该论文中与Dijkstra算法一起使用。该论文的完整源代码可以在这里找到。
//Struct used for each Fibonacci heap node
struct FibonacciNode {
int degree;
FibonacciNode* parent;
FibonacciNode* child;
FibonacciNode* left;
FibonacciNode* right;
bool mark;
int key;
int nodeIndex;
};
//Fibonacci heap class
class FibonacciHeap {
private:
FibonacciNode* minNode;
int numNodes;
vector<FibonacciNode*> degTable;
vector<FibonacciNode*> nodePtrs;
public:
FibonacciHeap(int n) {
//Constructor function
this->numNodes = 0;
this->minNode = NULL;
this->degTable = {};
this->nodePtrs.resize(n);
}
~FibonacciHeap() {
//Destructor function
this->numNodes = 0;
this->minNode = NULL;
this->degTable.clear();
this->nodePtrs.clear();
}
int size() {
//Number of nodes in the heap
return this->numNodes;
}
bool empty() {
//Is the heap empty?
if (this->numNodes > 0) return false;
else return true;
}
void insert(int u, int key) {
//Insert the vertex u with the specified key (value for L(u)) into the Fibonacci heap. O(1) operation
this->nodePtrs[u] = new FibonacciNode;
this->nodePtrs[u]->nodeIndex = u;
FibonacciNode* node = this->nodePtrs[u];
node->key = key;
node->degree = 0;
node->parent = NULL;
node->child = NULL;
node->left = node;
node->right = node;
node->mark = false;
FibonacciNode* minN = this->minNode;
if (minN != NULL) {
FibonacciNode* minLeft = minN->left;
minN->left = node;
node->right = minN;
node->left = minLeft;
minLeft->right = node;
}
if (minN == NULL || minN->key > node->key) {
this->minNode = node;
}
this->numNodes++;
}
FibonacciNode* extractMin() {
//Extract the node with the minimum key from the heap. O(log n) operation, where n is the number of nodes in the heap
FibonacciNode* minN = this->minNode;
if (minN != NULL) {
int deg = minN->degree;
FibonacciNode* currChild = minN->child;
FibonacciNode* remChild;
for (int i = 0; i < deg; i++) {
remChild = currChild;
currChild = currChild->right;
_existingToRoot(remChild);
}
_removeNodeFromRoot(minN);
this->numNodes--;
if (this->numNodes == 0) {
this->minNode = NULL;
}
else {
this->minNode = minN->right;
FibonacciNode* minNLeft = minN->left;
this->minNode->left = minNLeft;
minNLeft->right = this->minNode;
_consolidate();
}
}
return minN;
}
void decreaseKey(int u, int newKey) {
//Decrease the key of the node in the Fibonacci heap that has index u. O(1) operation
FibonacciNode* node = this->nodePtrs[u];
if (newKey > node->key) return;
node->key = newKey;
if (node->parent != NULL) {
if (node->key < node->parent->key) {
FibonacciNode* parentNode = node->parent;
_cut(node);
_cascadingCut(parentNode);
}
}
if (node->key < this->minNode->key) {
this->minNode = node;
}
}
private:
//The following are private functions used by the public methods above
void _existingToRoot(FibonacciNode* newNode) {
FibonacciNode* minN = this->minNode;
newNode->parent = NULL;
newNode->mark = false;
if (minN != NULL) {
FibonacciNode* minLeft = minN->left;
minN->left = newNode;
newNode->right = minN;
newNode->left = minLeft;
minLeft->right = newNode;
if (minN->key > newNode->key) {
this->minNode = newNode;
}
}
else {
this->minNode = newNode;
newNode->right = newNode;
newNode->left = newNode;
}
}
void _removeNodeFromRoot(FibonacciNode* node) {
if (node->right != node) {
node->right->left = node->left;
node->left->right = node->right;
}
if (node->parent != NULL) {
if (node->parent->degree == 1) {
node->parent->child = NULL;
}
else {
node->parent->child = node->right;
}
node->parent->degree--;
}
}
void _cut(FibonacciNode* node) {
_removeNodeFromRoot(node);
_existingToRoot(node);
}
void _addChild(FibonacciNode* parentNode, FibonacciNode* newChildNode) {
if (parentNode->degree == 0) {
parentNode->child = newChildNode;
newChildNode->right = newChildNode;
newChildNode->left = newChildNode;
newChildNode->parent = parentNode;
}
else {
FibonacciNode* child1 = parentNode->child;
FibonacciNode* child1Left = child1->left;
child1->left = newChildNode;
newChildNode->right = child1;
newChildNode->left = child1Left;
child1Left->right = newChildNode;
}
newChildNode->parent = parentNode;
parentNode->degree++;
}
void _cascadingCut(FibonacciNode* node) {
FibonacciNode* parentNode = node->parent;
if (parentNode != NULL) {
if (node->mark == false) {
node->mark = true;
}
else {
_cut(node);
_cascadingCut(parentNode);
}
}
}
void _link(FibonacciNode* highNode, FibonacciNode* lowNode) {
_removeNodeFromRoot(highNode);
_addChild(lowNode, highNode);
highNode->mark = false;
}
void _consolidate() {
int deg, rootCnt = 0;
if (this->numNodes > 1) {
this->degTable.clear();
FibonacciNode* currNode = this->minNode;
FibonacciNode* currDeg, * currConsolNode;
FibonacciNode* temp = this->minNode, * itNode = this->minNode;
do {
rootCnt++;
itNode = itNode->right;
} while (itNode != temp);
for (int cnt = 0; cnt < rootCnt; cnt++) {
currConsolNode = currNode;
currNode = currNode->right;
deg = currConsolNode->degree;
while (true) {
while (deg >= int(this->degTable.size())) {
this->degTable.push_back(NULL);
}
if (this->degTable[deg] == NULL) {
this->degTable[deg] = currConsolNode;
break;
}
else {
currDeg = this->degTable[deg];
if (currConsolNode->key > currDeg->key) {
swap(currConsolNode, currDeg);
}
if (currDeg == currConsolNode) break;
_link(currDeg, currConsolNode);
this->degTable[deg] = NULL;
deg++;
}
}
}
this->minNode = NULL;
for (size_t i = 0; i < this->degTable.size(); i++) {
if (this->degTable[i] != NULL) {
_existingToRoot(this->degTable[i]);
}
}
}
}
};
- Rhyd Lewis
-1
尽管STL没有明确说明它是一个斐波那契堆，但它实现了一个priority_queue，其复杂度、api和行为与斐波那契堆相同（实际上可能是一个伪装成斐波那契堆的斐波那契堆）
- hl037_
1
2
std::priority_queue 是一个容器适配器，它意味着它接受另一个容器（例如std::vector），并提供使用该容器的新操作。它要求其容器提供随机访问迭代器，这意味着它在后台使用二进制堆(理论上它可以使用基于数组的其他堆实现)。
二进制堆和斐波那契堆的复杂度不同。STL队列与比如 boost 斐波那契堆相比也有限的 API。 - Michal网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接