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

هیپ فیبوناچی یک ساختمان دادهآموزش ساختمان داده و الگوریتمهر ساختمان داده یک نوع فرمت ذخیره‌سازی و مدیریت داده‌ها در کامپیوتر است، که امکان دسترسی و اصلاح کارآمد آن داده‌ها را برای یکسری از الگوریتم‌ها و کاربردها فراهم می‌کند، در این صفحه به بررسی و آموزش ساختمان داده و الگوریتم پرداخته شده است است که از مجموعه‌ای از درختان تشکیل شده است که‌‌ این درختان از ویژگی 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

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()))

# 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);
}

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

جمع‌بندی

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

مطالب مرتبط

همه مقالات

لیست پیوندی دو طرفه

زبان های برنامه نویسی تحت وب و طراحی سایت⚡️فرانت اند+بک اند

سی شارپ چیست ⚡️سی شارپ به زبان ساده

بررسی زبان های برنامه نویسی جدید و کاربرد آنها