هیپ فیبوناچی یک ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیرهسازی و مدیریت دادهها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن دادهها را برای یکسری از الگوریتمها و کاربردها فراهم میکند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است است که از مجموعهای از درختان تشکیل شده است که این درختان از ویژگی Min-Heap یا Max-Heap پیروی میکنند. در هیپ فیبوناچی، یک گره میتواند بیش از دو فرزند داشته باشد یا اصلاً فرزندی نداشته باشد؛ همچنین عملیاتهای بهینهتری نسبت به هیپهای دوجملهای و باینری دارد. هیپ فیبوناچی را به این نام صدا میکنند زیرا درختان به گونهای ساخته شدهاند که درختی از مرتبه $\mathrm{n}$ دارای حداقل گرههای ${\mathrm{F}}_{\mathrm{n+2}}$ در آن باشد، جایی که ${\mathrm{F}}_{\mathrm{n+2}}$ جمله $\mathrm{n+2}$ ام فیبوناچی است.
ویژگی های هیپ فیبوناچی
ویژگیهای مهم هیپ فیبوناچی عبارتند از:
- این مجموعهای از درختان Min-Heap است (یعنی والدین همیشه کوچکتر از فرزندان هستند).
- یک اشاره گراشاره گر چیست — اشاره گرها در برنامه نویسیاین صفحه عالی توضیح داده اشاره گر چیست و نحوه تعریف اشاره گرها و همین طور اشاره گرها در برنامه نویسی را بررسی کرده سپس انواع اشاره گرها و کاربرد اشاره گرها را گفته در گره Min نگهداری میشود.
- از مجموعهای از گرههای مشخص شده تشکیل شده است.
- درختان درون یک هیپ فیبوناچی نامرتب هستند، اما ریشه دارند.
عملیات های هیپ فیبوناچی
در ادامه به بررسی عملیاتی که بر روی هیپ فیبوناچی انجام میگیرند میپردازیم.
عملیات درج در هیپ فیبوناچی
درج یک گره در یک هیپ شامل مراحل زیر است:
- یک گره جدید برای عنصر ایجاد کنید.
- بررسی کنید که آیا هیپ خالی است یا خیر.
- اگر هیپ خالی است، گره جدید را به عنوان گره ریشه و Min علامت گذاری کنید.
- در غیر این صورت، گره را در لیست ریشه قرار دهید و Min را بهروز کنید.
هیپ زیر را در نظر بگیرید:
پس از درج عنصر 21، هیپ به صورت زیر خواهد بود:
الگوریتمالگوریتم چیست به زبان ساده و با مثال های فراواندر این مقاله به زبان بسیار ساده و با مثال های متعدد توضیح داده شده که الگوریتم چیست و چه کاربردهایی دارد درج در هیپ فیبوناچی به صورت زیر است:
insert(H, x)
degree[x] = 0
p[x] = NIL
child[x] = NIL
left[x] = x
right[x] = x
mark[x] = FALSE
concatenate the root list containing x with root list H
if min[H] == NIL or key[x] < key[min[H]]
then min[H] = x
n[H] = n[H] + 1
پیدا کردن عنصر Min در هیپ فیبوناچی
عنصر Min همیشه با نشانگر Min داده میشود.
اجتماع
اجتماع دو هیپ فیبوناچی شامل مراحل زیر است:
- ریشههای هر دو هیپ را به هم بچسبانید.
- با انتخاب یک کلید Min از لیستهای ریشه جدید، Min را بهروز کنید.
دو هیپ زیر را در نظر بگیرید:
اجتماع این دو هیپ به صورت زیر خواهد بود:
پیچیدگی زمانی هیپ فیبوناچی
پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده این الگوریتم به صورت زیر است:
- درج: $\mathrm{O}\left(\mathrm{1}\right)$
- یافتن حداقل: $\mathrm{O}\left(\mathrm{1}\right)$
- اجتماع: $\mathrm{O}\left(\mathrm{1}\right)$
پیاده سازی هیپ فیبوناچی
در ادامه هیپ فیبوناچی را در زبان های برنامه نویسیزبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده مختلف پیادهسازی میکنیم.
Python
# Fibonacci Heap in python
import math
# Creating fibonacci tree
class FibonacciTree:
def __init__(self, value):
self.value = value
self.child = []
self.order = 0
# Adding tree at the end of the tree
def add_at_end(self, t):
self.child.append(t)
self.order = self.order + 1
# Creating Fibonacci heap
class FibonacciHeap:
def __init__(self):
self.trees = []
self.least = None
self.count = 0
# Insert a node
def insert_node(self, value):
new_tree = FibonacciTree(value)
self.trees.append(new_tree)
if (self.least is None or value < self.least.value):
self.least = new_tree
self.count = self.count + 1
# Get minimum value
def get_min(self):
if self.least is None:
return None
return self.least.value
# Extract the minimum value
def extract_min(self):
smallest = self.least
if smallest is not None:
for child in smallest.child:
self.trees.append(child)
self.trees.remove(smallest)
if self.trees == []:
self.least = None
else:
self.least = self.trees[0]
self.consolidate()
self.count = self.count - 1
return smallest.value
# Consolidate the tree
def consolidate(self):
aux = (floor_log(self.count) + 1) * [None]
while self.trees != []:
x = self.trees[0]
order = x.order
self.trees.remove(x)
while aux[order] is not None:
y = aux[order]
if x.value > y.value:
x, y = y, x
x.add_at_end(y)
aux[order] = None
order = order + 1
aux[order] = x
self.least = None
for k in aux:
if k is not None:
self.trees.append(k)
if (self.least is None
or k.value < self.least.value):
self.least = k
def floor_log(x):
return math.frexp(x)[1] - 1
fibonacci_heap = FibonacciHeap()
fibonacci_heap.insert_node(7)
fibonacci_heap.insert_node(3)
fibonacci_heap.insert_node(17)
fibonacci_heap.insert_node(24)
print('the minimum value of the fibonacci heap: {}'.format(fibonacci_heap.get_min()))
print('the minimum value removed: {}'.format(fibonacci_heap.extract_min()))
C++
// Operations on a Fibonacci heap in C++
#include <cmath>
#include <cstdlib>
#include <iostream>
using namespace std;
// Node creation
struct node {
int n;
int degree;
node *parent;
node *child;
node *left;
node *right;
char mark;
char C;
};
// Implementation of Fibonacci heap
class FibonacciHeap {
private:
int nH;
node *H;
public:
node *InitializeHeap();
int Fibonnaci_link(node *, node *, node *);
node *Create_node(int);
node *Insert(node *, node *);
node *Union(node *, node *);
node *Extract_Min(node *);
int Consolidate(node *);
int Display(node *);
node *Find(node *, int);
int Decrease_key(node *, int, int);
int Delete_key(node *, int);
int Cut(node *, node *, node *);
int Cascase_cut(node *, node *);
FibonacciHeap() { H = InitializeHeap(); }
};
// Initialize heap
node *FibonacciHeap::InitializeHeap() {
node *np;
np = NULL;
return np;
}
// Create node
node *FibonacciHeap::Create_node(int value) {
node *x = new node;
x->n = value;
return x;
}
// Insert node
node *FibonacciHeap::Insert(node *H, node *x) {
x->degree = 0;
x->parent = NULL;
x->child = NULL;
x->left = x;
x->right = x;
x->mark = ‘F’;
x->C = ‘N’;
if (H != NULL) {
(H->left)->right = x;
x->right = H;
x->left = H->left;
H->left = x;
if (x->n < H->n)
H = x;
} else {
H = x;
}
nH = nH + 1;
return H;
}
// Create linking
int FibonacciHeap::Fibonnaci_link(node *H1, node *y, node *z) {
(y->left)->right = y->right;
(y->right)->left = y->left;
if (z->right == z)
H1 = z;
y->left = y;
y->right = y;
y->parent = z;
if (z->child == NULL)
z->child = y;
y->right = z->child;
y->left = (z->child)->left;
((z->child)->left)->right = y;
(z->child)->left = y;
if (y->n < (z->child)->n)
z->child = y;
z->degree++;
}
// Union Operation
node *FibonacciHeap::Union(node *H1, node *H2) {
node *np;
node *H = InitializeHeap();
H = H1;
(H->left)->right = H2;
(H2->left)->right = H;
np = H->left;
H->left = H2->left;
H2->left = np;
return H;
}
// Display the heap
int FibonacciHeap::Display(node *H) {
node *p = H;
if (p == NULL) {
cout << "Empty Heap" << endl;
return 0;
}
cout << "Root Nodes: " << endl;
do {
cout << p->n;
p = p->right;
if (p != H) {
cout << "-->";
}
} while (p != H && p->right != NULL);
cout << endl;
}
// Extract min
node *FibonacciHeap::Extract_Min(node *H1) {
node *p;
node *ptr;
node *z = H1;
p = z;
ptr = z;
if (z == NULL)
return z;
node *x;
node *np;
x = NULL;
if (z->child != NULL)
x = z->child;
if (x != NULL) {
ptr = x;
do {
np = x->right;
(H1->left)->right = x;
x->right = H1;
x->left = H1->left;
H1->left = x;
if (x->n < H1->n)
H1 = x;
x->parent = NULL;
x = np;
} while (np != ptr);
}
(z->left)->right = z->right;
(z->right)->left = z->left;
H1 = z->right;
if (z == z->right && z->child == NULL)
H = NULL;
else {
H1 = z->right;
Consolidate(H1);
}
nH = nH – 1;
return p;
}
// Consolidation Function
int FibonacciHeap::Consolidate(node *H1) {
int d, I;
float f = (log(nH)) / (log(2));
int D = f;
node *A[D];
for (i = 0; i <= D; i++)
A[i] = NULL;
node *x = H1;
node *y;
node *np;
node *pt = x;
do {
pt = pt->right;
d = x->degree;
while (A[d] != NULL)
{
y = A[d];
if (x->n > y->n)
{
np = x;
x = y;
y = np;
}
if (y == H1)
H1 = x;
Fibonnaci_link(H1, y, x);
if (x->right == x)
H1 = x;
A[d] = NULL;
d = d + 1;
}
A[d] = x;
x = x->right;
}
while (x != H1);
H = NULL;
for (int j = 0; j <= D; j++) {
if (A[j] != NULL) {
A[j]->left = A[j];
A[j]->right = A[j];
if (H != NULL) {
(H->left)->right = A[j];
A[j]->right = H;
A[j]->left = H->left;
H->left = A[j];
if (A[j]->n < H->n)
H = A[j];
} else {
H = A[j];
}
if (H == NULL)
H = A[j];
else if (A[j]->n < H->n)
H = A[j];
}
}
}
// Decrease Key Operation
int FibonacciHeap::Decrease_key(node *H1, int x, int k) {
node *y;
if (H1 == NULL) {
cout << "The Heap is Empty" << endl;
return 0;
}
node *ptr = Find(H1, x);
if (ptr == NULL) {
cout << "Node not found in the Heap" << endl;
return 1;
}
if (ptr->n < k) {
cout << "Entered key greater than current key" << endl;
return 0;
}
ptr->n = k;
y = ptr->parent;
if (y != NULL && ptr->n < y->n) {
Cut(H1, ptr, y);
Cascase_cut(H1, y);
}
if (ptr->n < H->n)
H = ptr;
return 0;
}
// Cutting Function
int FibonacciHeap::Cut(node *H1, node *x, node *y)
{
if (x == x->right)
y->child = NULL;
(x->left)->right = x->right;
(x->right)->left = x->left;
if (x == y->child)
y->child = x->right;
y->degree = y->degree – 1;
x->right = x;
x->left = x;
(H1->left)->right = x;
x->right = H1;
x->left = H1->left;
H1->left = x;
x->parent = NULL;
x->mark = ‘F’;
}
// Cascade cut
int FibonacciHeap::Cascase_cut(node *H1, node *y) {
node *z = y->parent;
if (z != NULL) {
if (y->mark == ‘F’) {
y->mark = ‘T’;
} else
{
Cut(H1, y, z);
Cascase_cut(H1, z);
}
}
}
// Search function
node *FibonacciHeap::Find(node *H, int k) {
node *x = H;
x->C = ‘Y’;
node *p = NULL;
if (x->n == k) {
p = x;
x->C = ‘N’;
return p;
}
if (p == NULL) {
if (x->child != NULL)
p = Find(x->child, k);
if ((x->right)->C != ‘Y’)
p = Find(x->right, k);
}
x->C = ‘N’;
return p;
}
// Deleting key
int FibonacciHeap::Delete_key(node *H1, int k) {
node *np = NULL;
int t;
t = Decrease_key(H1, k, -5000);
if (!t)
np = Extract_Min(H);
if (np != NULL)
cout << "Key Deleted" << endl;
else
cout << "Key not Deleted" << endl;
return 0;
}
int main() {
int n, m, l;
FibonacciHeap fh;
node *p;
node *H;
H = fh.InitializeHeap();
p = fh.Create_node(7);
H = fh.Insert(H, p);
p = fh.Create_node(3);
H = fh.Insert(H, p);
p = fh.Create_node(17);
H = fh.Insert(H, p);
p = fh.Create_node(24);
H = fh.Insert(H, p);
fh.Display(H);
p = fh.Extract_Min(H);
if (p != NULL)
cout << "The node with minimum key: " << p->n << endl;
else
cout << "Heap is empty" << endl;
m = 26;
l = 16;
fh.Decrease_key(H, m, l);
m = 16;
fh.Delete_key(H, m);
}
کاربردهای هیپ فیبوناچی
هیپ های فیبوناچی برای پیادهسازی عنصر صفصف در ساختمان داده⚡️آموزش+انواع+مثالاین مقاله عالی به بررسی و آموزش صف در ساختمان داده ها پرداخته و همچنین صف خطی و صف حلقوی و پیاده سازی و عملیات روی هر یک و کاربردهای صف را بررسی کرده اولویت در الگوریتم دایجستراالگوریتم دایجسترا (Dijkstra) از 0 تا 100 - الگوریتم دایکسترااین صفحه الگوریتم دایجسترا (Dijkstra) (یا همان الگوریتم دایکسترا) را از 0 تا 100 بررسی کرده، همین طور به پیاده سازی و آموزش الگوریتم دایجسترا پرداخته است. استفاده میشود که به الگوریتم، زمان اجرای بسیار کارآمدی میدهد. هیپ های فیبوناچی نسبت به سایر انواع هیپ زمان استهلاک سریعتری دارند. هیپ های فیبوناچی شبیه هیپهای دو جملهای هستند اما هیپ های فیبوناچی ساختار پیچیدهتری دارند.
جمعبندی
هیپ فیبوناچی یک ساختمان داده قدرتمند است که میتواند در بسیاری از زمینههای علوم کامپیوترعلوم کامپیوتر یا کامپیوتر ساینس چیستدر این صفحه به بررسی و موشکافی رشته علوم کامپیوتر اعم از بررسی بازار کار، گرایشها، دروس و چارت درسی این رشته، میزان درآمد و حقوق فارغ التحصیلان این رشته و ادامه تحصیل در این رشته پرداخته شده است. اعمال شود. در این مقاله ما به بررسی این ساختمان داده پرداختیم و تعدادی از عملیاتهای آن را شرح دادیم و پیادهسازیهایی از این الگوریتم را دیدیم.
هیپ فیبوناچی برای چه کاری استفاده میشود؟
هیپ های فیبوناچی برای پیادهسازی صف اولویت در الگوریتم دایکسترا استفاده میشود که به الگوریتم، زمان اجرای بسیار کارآمدی میدهد. هیپهای فیبوناچی نسبت به سایر انواع هیپ، زمان اجرای سریعتری دارند. هیپهای فیبوناچی شبیه هیپهای دو جملهای هستند، اما هیپهای فیبوناچی ساختار پیچیدهتری دارند.
چرا هیپ فیبوناچی به این نام، نام گذاری شدهاند؟
هیپ فیبوناچی را به این نام مینامند زیرا درختان به گونهای ساخته شدهاند که درختی از مرتبه $\mathrm{n}$ دارای حداقل گرههای ${\mathrm{F}}_{\mathrm{n+2}}$ در آن باشد، جایی که ${\mathrm{F}}_{\mathrm{n+2}}$ جمله $\mathrm{n+2}$ ام فیبوناچی است.
معایب هیپ فیبوناچی چیست؟
یک عیب این است که هزینه واقعی یک فراخوانی داده شده میتواند به اندازه $\mathrm{O}\left(\mathrm{n}\right)$ باشد. یکی دیگر از معایب هیپ فیبوناچی این است که از حافظه بیشتری در هر عنصر نسبت به جایگزینهایی مانند هیپ باینری استفاده میکند.
چرا هیپ فیبوناچی زیاد استفاده نمیشود؟
اگرچه هیپهای فیبوناچی بسیار کارآمد به نظر میرسند، اما دو اشکال را دارند: در عمل آنها پیچیده هستند و آنها در عمل در مقایسه با اشکال دیگر هیپها کمتر کارآمد هستند.