fheap.h

来自「I implement Dijkstra s Single Source Sho」· C头文件 代码 · 共 52 行

#pragma once
#include "distset.h"
#include <cmath>

class FHeapNode
{
public:	
	int degree;
	int dist;
	int node;
    bool chlidcut;
	FHeapNode *parent;
    FHeapNode *left, *right;
    FHeapNode *child;
};

class FHeap :
	public DistSet
{
public:
	FHeap(int);
public:
	~FHeap(void);
public:
	virtual int insert(int node, int dist);
public:
	virtual int decreasDist(int node, int newDist);
public:
	virtual int deleteMin(void);
public:
	virtual void initial(void);
public:
	FHeapNode * min;
	int tree_num;
	FHeapNode ** allNodes;
public:
	void pairwiseCombine(void);
public:
	static void testFHeap(void);
private:
	void meld(FHeapNode *, int);
private:
	void combineTrees(FHeapNode * tree1, FHeapNode * tree2);
private:
	void cascadingCut(FHeapNode * theNode);
private:
	void cut(FHeapNode * node, FHeapNode * parent);
private:
	int maxDegree;
	int *degreeList;
};