Wikiszótár

Fibonacci-kupac

Magyar

Kiejtés

  • IPA: [ ˈfibonɒt͡sːikupɒt͡s]

Főnév

Fibonacci-kupac

  1. (matematika, algoritmusok)

Fibonacci-kupac (Fibonacci Heap)

A Fibonacci-kupac egy haladó adatstruktúra, amely hatékonyan támogatja a prioritási sor műveleteit. Ez különösen hasznos grafalgoritmusokban, például a Dijkstra algoritmusban vagy a Prim algoritmusban, ahol gyakran kell minimális elemeket keresni vagy prioritást csökkenteni.


1. Fibonacci-kupac jellemzői

  1. Szerkezet:
    • A Fibonacci-kupac egy lazán strukturált binomiális halom.
    • A kupac több fát tartalmazhat, amelyek minimum-heappal (min-heap) kapcsolatos tulajdonságot tartanak fenn: minden szülő csomópont értéke kisebb vagy egyenlő a gyermekei értékénél.
    • A fák ciklikus kétirányú listákban vannak szervezve.
  2. Műveletek időbonyolultsága:
    • Insert (beszúrás): (O(1)) amortizált.
    • Find-Min (minimum keresése): (O(1)).
    • Extract-Min (minimum eltávolítása): (O(n)) amortizált.
    • Decrease-Key (kulcs csökkentése): (O(1)) amortizált.
    • Delete (elem törlése): (O(n)).
    • Merging (kupacok egyesítése): (O(1)).
  3. Amortizált elemzés:
    • Az amortizált hatékonyságot a potenciál módszer biztosítja, amely a fák számának csökkentésére és a laza szerkezet kihasználására épül.


2. Fibonacci-kupac szerkezete

  • Node (csomópont):
    • Minden csomópont tárolja:
      • Kulcs (érték).
      • Szülőre és gyermekekre mutató pointerek.
      • A gyermekek számát (degree).
      • Egy “jelölt” (marked) flag-et, amely megjegyzi, hogy a csomópont gyermekét elvesztette-e.
  • Gyökérlista:
    • A fák gyökércsomópontjai egy kétirányú ciklikus listában vannak tárolva.


3. Fibonacci-kupac műveletei

1. Beszúrás (Insert)

  1. Hozz létre egy új csomópontot az értékkel.
  2. Tedd hozzá a gyökérlistához.
  3. Frissítsd a minimális elemet, ha szükséges.
  4. Időbonyolultság: (O(1)).


2. Minimum keresése (Find-Min)

  1. Egyszerűen térj vissza a gyökérlistában tárolt minimális elemre mutató pointerrel.
  2. Időbonyolultság: (O(1)).


3. Minimum eltávolítása (Extract-Min)

  1. Töröld a minimális csomópontot.
  2. Add a minimális csomópont összes gyermekét a gyökérlistához.
  3. Alakítsd át a kupacot úgy, hogy az megfeleljen a Fibonacci-kupac tulajdonságainak (pairwise combining).
  4. Frissítsd a minimális elemet.
  5. Időbonyolultság: (O(n)) amortizált.


4. Kulcs csökkentése (Decrease-Key)

  1. Csökkentsd a kulcsot a megadott csomópontban.
  2. Ha a csomópont új kulcsa kisebb, mint a szülőé:
    • Válaszd le a csomópontot a szülőről, és add hozzá a gyökérlistához.
    • Ha a szülő jelölt volt, válaszd le azt is, és ismételd ezt felfelé a fában (cascading cut).
  3. Frissítsd a minimális elemet, ha szükséges.
  4. Időbonyolultság: (O(1)) amortizált.


5. Kupacok egyesítése (Union)

  1. Összefűzés a két gyökérlista között.
  2. Frissítsd a minimális elemet.
  3. Időbonyolultság: (O(1)).


4. Pseudocode

Beszúrás

function Insert(heap, key):
    node = create_node(key)
    add_to_root_list(heap, node)
    if heap.min is None or key < heap.min.key:
        heap.min = node
    heap.size += 1

Minimum keresése

function Find-Min(heap):
    return heap.min

Minimum eltávolítása

function Extract-Min(heap):
    z = heap.min
    if z is not None:
        for each child in z.children:
            add_to_root_list(heap, child)
            child.parent = None
        remove_from_root_list(heap, z)
        if z == z.next:
            heap.min = None
        else:
            heap.min = z.next
            Consolidate(heap)
        heap.size -= 1
    return z

Kulcs csökkentése

function Decrease-Key(heap, node, new_key):
    if new_key > node.key:
        return "Error: New key is greater than current key"
    node.key = new_key
    y = node.parent
    if y is not None and node.key < y.key:
        Cut(heap, node, y)
        Cascading-Cut(heap, y)
    if node.key < heap.min.key:
        heap.min = node

5. Python implementáció

Az alábbi kód egy egyszerű Fibonacci-kupac implementáció: 

class FibonacciNode:
    def __init__(self, key):
        self.key = key
        self.parent = None
        self.child = None
        self.degree = 0
        self.mark = False
        self.next = self
        self.prev = self

class FibonacciHeap:
    def __init__(self):
        self.min = None
        self.size = 0

    def insert(self, key):
        node = FibonacciNode(key)
        if self.min is None:
            self.min = node
        else:
            self._add_to_root_list(node)
            if key < self.min.key:
                self.min = node
        self.size += 1
        return node

    def find_min(self):
        return self.min.key if self.min else None

    def extract_min(self):
        z = self.min
        if z is not None:
            if z.child is not None:
                children = [x for x in self._iterate(z.child)]
                for child in children:
                    self._add_to_root_list(child)
                    child.parent = None
            self._remove_from_root_list(z)
            if z == z.next:
                self.min = None
            else:
                self.min = z.next
                self._consolidate()
            self.size -= 1
        return z.key if z else None

    def _add_to_root_list(self, node):
        if self.min is None:
            self.min = node
        else:
            node.prev = self.min
            node.next = self.min.next
            self.min.next.prev = node
            self.min.next = node

    def _remove_from_root_list(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

    def _consolidate(self):
        degrees = {}
        nodes = [x for x in self._iterate(self.min)]
        for node in nodes:
            degree = node.degree
            while degree in degrees:
                other = degrees.pop(degree)
                if node.key > other.key:
                    node, other = other, node
                self._link(other, node)
                degree += 1
            degrees[degree] = node
        self.min = None
        for node in degrees.values():
            if self.min is None or node.key < self.min.key:
                self.min = node

    def _link(self, y, x):
        self._remove_from_root_list(y)
        y.parent = x
        if x.child is None:
            x.child = y
        else:
            self._add_to_root_list(y, x.child)
        x.degree += 1
        y.mark = False

    def _iterate(self, start):
        node = stop = start
        while True:
            yield node
            node = node.next
            if node == stop:
                break

# Használat
fib_heap = FibonacciHeap()
fib_heap.insert(10)
fib_heap.insert(3)
fib_heap.insert(15)
print(fib_heap.find_min())  # 3
fib_heap.extract_min()
print(fib_heap.find_min())  # 10

6. C++ implementáció

Egy C++ implementáció bonyolultabb a pointerek miatt, de hasonló struktúrát követ. Ha szeretnél, készítek egy konkrét példát.

A Fibonacci-kupac hatékony és gyakran használt haladó algoritmusokban, különösen a grafalgoritmusoknál!

Fordítások

További információk

A lap eredeti címe: „https://hu.wiktionary.org/w/index.php?title=Fibonacci-kupac&oldid=3480222”