NPComplete & Fibonacci Heap
JB Updated on ãƒ»6 min read
CS Level Up Series (29 Part Series)
This post covers concepts but, sadly, provides no code samples (particularly, no implementation of a fibonacci heap). This will be a rarity in this series. Although I think it's a worthwhile exercise to write code whilst covering topics, the Fibonnaci heap is seldomly (if ever) required to be implemented (say, in interviews)  but it is important to know what it is. Also consider that I have a large number of topics to cover in a defined window of time (which I intend to keep to).
Polynomial Time
Resources
Takeaways

O(n^k). Where
k
is non negative.  Some examples of polynomial run times: O(3n^4), O(n^100), O(n^2), O(n), O(log n), O(n log n).
 Faster than factorial (O(n!)) and exponential (O(2^n)) run times.
NP, NPHard, NPComplete
Resources
Takeaways
 P, NP, NPHard, & NPComplete are classes of complexity
 P is a set of problems solvable in polynomial time
 NP is a set of decision problems solvable in polynomial time using a nondeterministic algorithm (NP stands for Nondeterministic Polynomial time)
 Nondeterministic algorithms are a hypothetical model
 They allow us to imagine a solution to a problem, or subproblem, that can be solved in a notyet possible/discovered run time
 For example, a solution to an NP problem in polynomial time might assert that the search algorithm it uses for the solution is O(1) (constant time).
 Of course, we know that there is no such algorithm that can search, reliably, in O(1). This is exactly the point of nondeterministic algorithms. They are aware of the constraints in reality, but hypothetically if we can make decisions in algorithms in faster than possible run times (that we know of today) then we can theoretically prove that NP problems are solvable in polynomial time.
 A problem is in P if it can be solved in polynomial time
 An example of a problem in P: Given a list of
n
integers and an integerk
, is there an integer in the list greater thank
? We can solve this problem using linear search or, if the list is sorted, binary search.
 Both linear and binary search run in polynomial time, therefore the problem is solvable in polynomial time and is in P.
 A problem is in NP if it can be solved in polynomial time, using a nondeterministic algorithm
 An example of a problem in NP: Given a set of integers
A
, partitionA
into three subsets whose sum are equal. Essentially we need to split the list into 3 subsets, and each of those subsets must have an equal sum.
 This problem has no known solution that runs in polynomial time (deterministically)
 NPComplete are simply NP problems that can be reduced* to each other, such that solving one of them in polynomial time means that we can solve the rest of them, also in polynomial time.
 Formally: All problems
X
in NP for which it is possible to reduce any other NP problemY
toX
in polynomial time.
 Formally: All problems
 NPHard problems:
 These are at least as hard as the hardest problems in NP. If we can solve these problems in polynomial time, we can solve any NP problem.
 NPhard problems don't have to be decision problems, and they do not have to be in NP.
 Formally: A problem
X
is NPhard, if there is an NPcomplete problemY
, such thatY
is reducible toX
in polynomial time.
 There is a famous question in computer science: Does
P = NP
? Most people think
P != NP
, instead it is widely believed that P is a subset of NP (see diagram below). However, we have not yet proved that P does not equal NP.
 Most people think
*Reductions:
 A process whereby we reduce (convert) problem
X
into problemY
 We do this to answer "Can we use the solution for
X
to solveY
?"  Reduction is the most common algorithm design technique
 Reduction allows us to reuse/repurpose algorithms for a variety of problems.
 An example of this reuse is the partitioning logic for both
Quicksort()
&Quickselect()
 To learn more about quicksort see my post: Common Sorting Algorithms
 To learn more about quickselect see my post Searching Algorithms
Fibonacci Heap
Resources
Takeaways
deletemin  insert  decreasekey  

Binary Heap  O(log n)  O(log n)  O(log n) 
Binomial Heap  O(log n)  O(1) _{amortized}  O(log n) 
Linked List  O(n)  O(1)  O(1) 
Fibonacci Heap  O(log n) _{amortized}  O(1) _{amortized}  O(1) _{amortized} 
 Motivation behind inventing the Fibonacci heap was to speed up Dijkstra's algorithm
 Dijkstra's algorithm will be covered in depth in a later post, but it is an algorithm for finding the shortest path between vertices in a graph.
 To learn more about graphs, check out my post: Learning Graphs.
 Dijkstra's algorithm makes use of a primary queue in it's implementation, and makes heavy use of
insert
&decreasekey
operations  as well some use ofdeletemin
.  Binary Heaps are a common backing data structure for a priority queue
 To learn more about priority queues & binary heaps, see my posts: Learning Binary Heaps & Learning Priority Queues.
 As you can see in the above table, the Fibonacci heap greatly speeds up the
insert
anddecreasekey
operations  The Fibonacci heap takes advantage of the fact that batch operations are more efficient
 Example:
 A binary heap's
insert
operation isO(log n)
. But it can only take 1 element at a time. So if weinsert
N
items into a binary heap this will takeO(n log n)
.  But to convert
N
elements to a binary heap viaheapify
(which acceptsN
elements, and represents our batch operation) only takesO(n)
.  This demonstrates that batching can be faster than single operations within a binary heap. The Fibonacci heap capitalizes on batching and is able to speed up
insert
&decreasekey
operations as a result.
 A binary heap's
 So at it's core, what is a Fibonacci heap?
 A Fibonacci heap is essentially just a list of trees, with each tree being a heap.
 The Fibonacci heap keeps track of the smallest root in it's list of heaps. This pointer can be referred to as the
minroot
.  The Fibonacci heap is considered a lazy heap, remember that batching concept mentioned earlier? This is related to the Fibonacci heap's laziness
 A Fibonacci heap lazily defers merging/consolidating trees until
deletemin
is called.  Notice how
insert
anddecreasekey
are essentially constant time (O(1)
) operations? This is due to the fact that they don't do any related cleanup for their operation  they defer/delegate the work todeletemin
.  This means if you do a series of
insert
ordecreasekey
operations on a Fibonacci heap, no related cleanup is being performed. This allows those operations to be faster than the same operations in a binary heap.  So when does the cleanup happen? The next time
deletemin
is called.  So using our example of doing a series of
insert
/decreasekey
operations, if we followed those with adeletemin
operation  this would trigger our batch cleanup operation.  Lets go through what each operation is doing under the hood:

insert
: This just adds a new node to the list of heaps (it doesn't add the node to an existing heap in the list) 
deletemin
: Removes the
minroot
 Children of
minroot
get promoted to the root list  Trees with the same degree (number of children) are merged together
 The
minroot
pointer is updated
 Removes the

decreasekey
: If decreasing the key of a child node such that the child node's key is now less than its parent's key: consider the child node a heap violating node
 Put heap violating nodes into the root list and mark the old parent as loser
 If a parent loses two children in this fashion, it is also put into the root list (removed from it's heap  same as it's children were)
 Moving parents in this way prevents parents from having a large number of children but no grandchildren
 Having little to no grandchildren in a heap would make
deletemin
very slow  so it is best avoided

As always, if you found any errors in this post please let me know!
CS Level Up Series (29 Part Series)