کنکور کامپیوتر
0
ورود | ثبت نام
کنکور کامپیوترهیپ فیبوناچی یا هرم فیبوناچی چیست
نظرات
اشتراک
بالا
علاقه‌مندی

اشتراک
 
راهنمای انتخاب موضوع
هیپ فیبوناچی یا هرم فیبوناچی
کنکور کامپیوترهیپ فیبوناچی یا هرم فیبوناچی چیست

هیپ فیبوناچی یا هرم فیبوناچی چیست

هیپ فیبوناچی (Fibonacci heap) چیست، این صفحه عالی به آموزش هرم فیبوناچی و عملیات هیپ فیبوناچی و ویژگی های هیپ فیبوناچی و کاربردهای هیپ فیبوناچی پرداخته

هیپ فیبوناچی یک ساختمان دادهآموزش ساختمان داده و الگوریتمآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است است که از مجموعه‌ای از درختان تشکیل شده است که‌‌ این درختان از ویژگی Min-Heap یا Max-Heap پیروی می‌کنند. در هیپ فیبوناچی، یک گره می‌تواند بیش از دو فرزند داشته باشد یا اصلاً فرزندی نداشته باشد؛ همچنین عملیات‌های بهینه‌تری نسبت به هیپ‌های دوجمله‌‌ای و باینری دارد. هیپ فیبوناچی را به‌‌ این نام صدا می‌کنند زیرا درختان به گونه‌‌ای ساخته شده‌اند که درختی از مرتبه $\mathrm{n}$ دارای حداقل گره‌های ${\mathrm{F}}_{\mathrm{n+2}}$ در آن باشد، جایی که ${\mathrm{F}}_{\mathrm{n+2}}$ جمله $\mathrm{n+2}$ ام فیبوناچی است.

حتما بخوانید :
ساختمان داده پشته ⚡️ پشته چیست؟ کاربرد پشته در ساختمان داده

ویژگی های هیپ فیبوناچی

ویژگی‌های مهم هیپ فیبوناچی عبارتند از:

نمونه ای از یک هیپ فیبوناچی و ویژگی های آن

عملیات های هیپ فیبوناچی

در ادامه به بررسی عملیاتی که بر روی هیپ فیبوناچی انجام می‌گیرند می‌پردازیم.

عملیات درج در هیپ فیبوناچی

درج یک گره در یک هیپ شامل مراحل زیر است:

هیپ زیر را در نظر بگیرید:

یک نمونه هیپ فیبوناچی

پس از درج عنصر 21، هیپ به صورت زیر خواهد بود:

تصویری از هیپ فیبوناچی، پس از وارد کردن عنصر 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 داده می‌شود.

اجتماع

اجتماع دو هیپ فیبوناچی شامل مراحل زیر است:

دو هیپ زیر را در نظر بگیرید:

نمونه ای از دو هیپ جدا

اجتماع‌‌ این دو هیپ به صورت زیر خواهد بود:

دو هیپ فیبوناچی که با یکدیگر ادغام شدند

پیچیدگی زمانی هیپ فیبوناچی

پیچیدگی زمانیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیپیچیدگی زمانی الگوریتم چیست؟ معرفی نماد های مجانبیاین صفحه عالی به معرفی پیچیدگی زمانی الگوریتم پرداخته، همچنین انواع نماد های مجانبی و پیچیدگی زمانی های برخی از الگوریتم های مرتب سازی و جستجو را توضیح داده این الگوریتم به صورت زیر است:

حتما بخوانید :
صف در ساختمان داده⚡️آموزش+انواع+مثال

پیاده سازی هیپ فیبوناچی

در ادامه هیپ فیبوناچی را در زبان های برنامه نویسیزبان های برنامه نویسی چیست؟زبان های برنامه نویسی چیست؟این مقاله عالی توضیح داده که زبان های برنامه نویسی چیست؟ و انواع زبان های برنامه نویسی و بهترین زبان برنامه نویسی برای شروع و پردرآمدترین آنها را معرفی کرده مختلف پیاده‌سازی می‌کنیم.

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 - الگوریتم دایکسترااین صفحه الگوریتم دایجسترا (Dijkstra) (یا همان الگوریتم دایکسترا) را از 0 تا 100 بررسی کرده، همین طور به پیاده سازی و آموزش الگوریتم دایجسترا پرداخته است. استفاده می‌شود که به الگوریتم، زمان اجرای بسیار کارآمدی می‌دهد. هیپ های فیبوناچی نسبت به سایر انواع هیپ زمان استهلاک سریع‌تری دارند. هیپ های فیبوناچی شبیه هیپ‌های دو جمله‌‌ای هستند اما هیپ های فیبوناچی ساختار پیچیده‌تری دارند.

جمع‌بندی

هیپ فیبوناچی یک ساختمان داده قدرت‌مند است که می‌تواند در بسیاری از زمینه‌های علوم کامپیوترعلوم کامپیوتر یا کامپیوتر ساینس چیستعلوم کامپیوتر یا کامپیوتر ساینس چیستدر این صفحه به بررسی و موشکافی رشته علوم کامپیوتر اعم از بررسی بازار کار، گرایش‌ها، دروس و چارت درسی این رشته، میزان درآمد و حقوق فارغ التحصیلان این رشته و ادامه تحصیل در این رشته پرداخته‌ شده است. اعمال شود. در‌‌ این مقاله ما به بررسی‌‌ این ساختمان داده پرداختیم و تعدادی از عملیات‌های آن را شرح دادیم و پیاده‌سازی‌هایی از‌‌ این الگوریتم را دیدیم.

هیپ فیبوناچی برای چه کاری استفاده می‌شود؟

هیپ های فیبوناچی برای پیاده‌سازی صف اولویت در الگوریتم دایکسترا استفاده می‌شود که به الگوریتم، زمان اجرای بسیار کارآمدی می‌دهد. هیپ‌های فیبوناچی نسبت به سایر انواع هیپ، زمان اجرای سریع‌تری دارند. هیپ‌های فیبوناچی شبیه هیپ‌های دو جمله‌‌ای هستند، اما هیپ‌های فیبوناچی ساختار پیچیده‌تری دارند.

چرا هیپ فیبوناچی به ‌این نام، نام گذاری شده‌اند؟

هیپ فیبوناچی را به ‌‌این نام می‌نامند زیرا درختان به گونه‌‌ای ساخته شده‌اند که درختی از مرتبه $\mathrm{n}$ دارای حداقل گره‌های ${\mathrm{F}}_{\mathrm{n+2}}$ در آن باشد، جایی که ${\mathrm{F}}_{\mathrm{n+2}}$ جمله $\mathrm{n+2}$ ام فیبوناچی است.

معایب هیپ فیبوناچی چیست؟

یک عیب‌‌ این است که هزینه واقعی یک فراخوانی داده شده می‌تواند به اندازه $\mathrm{O}\left(\mathrm{n}\right)$ باشد. یکی دیگر از معایب هیپ فیبوناچی‌‌ این است که از حافظه بیشتری در هر عنصر نسبت به جایگزین‌هایی مانند هیپ باینری استفاده می‌کند.

چرا هیپ فیبوناچی زیاد استفاده نمی‌شود؟

اگرچه هیپ‌های فیبوناچی بسیار کارآمد به نظر می‌رسند، اما دو اشکال را دارند: در عمل آنها پیچیده هستند و آنها در عمل در مقایسه با اشکال دیگر هیپ‌ها کمتر کارآمد هستند.

امتیازدهی4.1666666666667 1 1 1 1 1 1 1 1 1 14.17 امتیاز (3 رای)
اشتراک
برچسب‌ها :
13
12
5
16
19
14
11
22
17

مطالب مرتبط

همه مقالات
زبان برنامه نویسی Mojo، جایگزینی برای پایتون

زبان برنامه نویسی Mojo، جایگزینی برای پایتون

میزان و درجه سختی زبان های برنامه نویسی

میزان و درجه سختی زبان های برنامه نویسی

ترتیب یادگیری زبان های برنامه نویسی

ترتیب یادگیری زبان های برنامه نویسی

بهترین زبان برنامه نویسی برای شروع‌ چیست؟

بهترین زبان برنامه نویسی برای شروع‌ چیست؟

معرفی ارشد شبکه های کامپیوتری دانشگاه صنعتی شریف

معرفی ارشد شبکه های کامپیوتری دانشگاه صنعتی شریف

معرفی بهترین دانشگاه های ایران در رشته فناوری اطلاعات

معرفی بهترین دانشگاه های ایران در رشته فناوری اطلاعات

صحبت با هوش مصنوعی گوگل

صحبت با هوش مصنوعی گوگل

معرفی گرایش رایانش امن مقطع ارشد دانشگاه شریف

معرفی گرایش رایانش امن مقطع ارشد دانشگاه شریف

ظرفیت مهندسی کامپیوتر شریف

ظرفیت مهندسی کامپیوتر شریف

مشاهده تمامی مقالات
رتبه بندی دانشگاه های ایران + معرفی بهترین دانشگاه های ایران

رتبه بندی دانشگاه های ایران + معرفی بهترین دانشگاه های ایران

منابع کنکور ارشد کامپیوتر

منابع کنکور ارشد کامپیوتر

معرفی رشته آی تی (رشته فناوری اطلاعات)

معرفی رشته آی تی (رشته فناوری اطلاعات)

گرایش های ارشد کامپیوتر

گرایش های ارشد کامپیوتر

رشته کامپیوتر فنی حرفه ای و ادامه تحصیل این رشته در دانشگاه

رشته کامپیوتر فنی حرفه ای و ادامه تحصیل این رشته در دانشگاه

مشاهده تمامی مقالات
14
11
22
17
13
12
5
16
19
بارگذاری نظرات
تلگرام اینستاگرام