Skip to main content

An implementation of Fibonacci heap

Project description

Fibonacci Heap

Fibonacci Heap Overview

The data structure and its operations are described Cormen et al. (chapter 19) Fibonacci heap supports mergeable-heap operations, including make-heap, insert, minimum, extract-min, and union. The data structure also supports key-decrease and delete, although using these two operations requires users to create nodes for items themselves.

Representation

Node

Each node has the following attributes:

  • left, right: the node’s adjacent siblings. The node and its siblings are doubly linked, so they form a circular loop. If x is an only child, it is its own left and right sibling.
  • child: the representative child of the node. To access all the children of the node, first access the representative child, then access all the representative child’s siblings through left and right attributes
  • parent
  • degree: the number of the node’s children
  • mark: (description by Cormen et al.) is either True or False, indicating whether the node has lost a child since the last time it was made the child of another node. Newly created nodes are unmarked. A node becomes unmarked whenever it is made the child of another node.

Fibonacci Heap

A heap has the following attributes:

  • min: points to the node that contains the minimum key
  • number of nodes currently in the heap
  • number of roots in the tree. A Fibonacci heap can contain many trees of min-ordered heap. The roots of these trees are doubly linked and form a circular loop as in the case with siblings. The number of trees of a Fibonacci heap is always the number of roots.
  • number of marked nodes in the heap

Operations Overview

make-heap

Runs in worst-case time. Initializes an empty heap.

insert

Runs in worst-case time. Adds the node as a root of the heap.

minimum

Runs in worst-case time. Returns the min attribute of the heap.

extract-min

Runs in amortized time. Removes and returns the minimum node. This procedure moves each of the minimum node’s children to the root list, removes the minimum node itself from the root list, and consolidates the resulted tree to reduces the number of trees.

union

Runs in worst-case time. Makes and returns a union of two heaps. This procedure simply concatenates the two root lists.

decrease-key

Runs in amortized time. Decreases node x’s key to k.

delete

Runs in amortized time. Remove x from the heap by first setting its key to minus infinity and extracting the heap’s min.

Use

Installing using pip:

>>> pip install fibheap

Using mergable-heap operations:

>>> from fibheap import *
>>> heap1 = makefheap()
>>> heap2 = makefheap()
>>> num_list1 = [1,4,2]
>>> num_list2 = [6,-1,0]
>>> for num in num_list1:
...     fheappush(heap1, num)
... 
>>> for num in num_list2:
...     fheappush(heap2, num)
... 
>>> fheapunion(heap1, heap2)
>>> getfheapmin(heap1)
-1
>>> sorted_list = []
>>> while heap1.num_nodes:
...     sorted_list.append(fheappop(heap1))
... 
>>> sorted_list
[-1, 0, 1, 2, 4, 6]

When data contains more than numbers:

>>> item_list = [(3, 'a'),(0, 'z'), (2,'m'), (-2, 'r')]
>>> heap = makefheap()
>>> for item in item_list:
...     fheappush(heap, item)
... 
>>> sorted_list = []
>>> while heap.num_nodes:
...     sorted_list.append(fheappop(heap))
... 
>>> sorted_list
[(-2, 'r'), (0, 'z'), (2, 'm'), (3, 'a')]

Project details


Download files

Download the file for your platform. If you're not sure which to choose, learn more about installing packages.

Source Distribution

fibheap-0.2.1.tar.gz (5.6 kB view details)

Uploaded Source

File details

Details for the file fibheap-0.2.1.tar.gz.

File metadata

  • Download URL: fibheap-0.2.1.tar.gz
  • Upload date:
  • Size: 5.6 kB
  • Tags: Source
  • Uploaded using Trusted Publishing? No
  • Uploaded via: twine/1.12.1 pkginfo/1.4.2 requests/2.18.4 setuptools/40.6.3 requests-toolbelt/0.8.0 tqdm/4.28.1 CPython/3.6.5

File hashes

Hashes for fibheap-0.2.1.tar.gz
Algorithm Hash digest
SHA256 270fcca93e3cc7e2aab68a640e441686b509cc961d3ee9199dff9256a3649cb3
MD5 6453e2da991f900df88654cb55e4c31a
BLAKE2b-256 5bf8cfe18a1b76810bc9df6ab319b7505dc38f69e71e871b6a9fc81b2fe5757d

See more details on using hashes here.

Supported by

AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Pingdom Monitoring Sentry Error logging StatusPage Status page