NP-Complete & Fibonacci Heap
Tags: computerscience, algorithms, datastructures, csharp
Published: 2020-02-02 19:58:34

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](https://dev.to/jjb/cs-level-up-series-part-0-cco) in a defined window of time (which I intend to keep to).

# Polynomial Time

**Resources**
1. [What exactly is polynomial time?](https://cs.stackexchange.com/a/13626)

**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, NP-Hard, NP-Complete

**Resources**
1. [Video explanation](https://www.youtube.com/watch?v=e2cF8a5aAhE)
1. [Video on computational complexity](https://www.youtube.com/watch?v=moPtwq_cVH8&list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb&index=23)
1. [Explanation of each complexity class](https://stackoverflow.com/a/1857342/3574076)

**Takeaways**

- P, NP, NP-Hard, & NP-Complete 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 not-yet 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 integer `k`, is there an integer in the list greater than `k`? 
   - 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`, partition `A` 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)
- NP-Complete 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 problem `Y` to `X` in polynomial time.
- NP-Hard 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.
   - NP-hard problems don't have to be decision problems, and they do not have to be in NP.
   - Formally: A problem `X` is NP-hard, if there is an NP-complete problem `Y`, such that `Y` is reducible to `X` 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.

**Visualization**
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/f23qxdvt9f5uhanap6mp.png)

*Reductions:
   - A process whereby we reduce (convert) problem `X` into problem `Y`
   - We do this to answer "Can we use the solution for `X` to solve `Y`?"
   - Reduction is the most common algorithm design technique
   - Reduction allows us to reuse/re-purpose 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](https://dev.to/jjb/part-12-common-sorting-algorithms-2f37)
      - To learn more about quickselect see my post [Searching Algorithms](https://dev.to/jjb/part-13-searching-algorithms-46jo)

---

# Fibonacci Heap

**Resources**
1. [Very good video explanation](https://www.youtube.com/watch?v=nZ0nFTvQez0)
2. [Overview and explanation (slide show)](https://www.cs.princeton.edu/~wayne/teaching/fibonacci-heap.pdf)

**Takeaways**

| | delete-min  | insert  | decrease-key  |
|---|---|---|---|---|
| Binary Heap  | `O(log n)`  | `O(log n)`  | `O(log n)`  |
| Binomial Heap  | `O(log n)`  | `O(1)` <sub><small>amortized</small></sub> | `O(log n)`  |
| Linked List  | `O(n)`  | `O(1)`  | `O(1)`  |
| Fibonacci Heap  | `O(log n)` <sub><small>amortized</small></sub>  | `O(1)` <sub><small>amortized</small></sub> | `O(1)` <sub><small>amortized</small></sub> |

- 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.](https://dev.to/jjb/part-9-learning-graphs-4859)
- Dijkstra's algorithm makes use of a primary queue in it's implementation, and makes heavy use of `insert` & `decrease-key` operations - as well some use of `delete-min`.
- 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](https://dev.to/jjb/part-7-learning-about-binary-heaps-289h) & [Learning Priority Queues.](https://dev.to/jjb/part-8-learning-priority-queues-28dc)
- As you can see in the above table, the Fibonacci heap greatly speeds up the `insert` and `decrease-key` operations
- The Fibonacci heap takes advantage of the fact that **batch** operations are more efficient
- Example: 
   - A binary heap's `insert` operation is `O(log n)`. But it can only take 1 element at a time. So if we `insert` `n` items into a binary heap this will take `O(n log n)`.
   - But to convert `n` elements to a binary heap via `heapify` (which accepts `n` elements, and represents our batch operation) only takes `O(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` & `decrease-key` operations as a result.
- 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 `min-root`.
- 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 `delete-min` is called.
- Notice how `insert` and `decrease-key` 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 to `delete-min`. 
- This means if you do a series of `insert` or `decrease-key`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 `delete-min` is called. 
- So using our example of doing a series of `insert`/`decrease-key` operations, if we followed those with a `delete-min` 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)
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/6up3lpfflcwolea5nnym.jpeg)
   - `delete-min`:
      - Removes the `min-root`
      - Children of `min-root` get promoted to the root list
      - Trees with the same degree (number of children) are merged together
      - The `min-root` pointer is updated
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/342zq5sm7ar4gmnoykgr.jpeg)
   - `decrease-key`:
      - 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 `delete-min` very slow - so it is best avoided
![Alt Text](https://dev-to-uploads.s3.amazonaws.com/i/s1o6vzi6nucbm7k1e0h8.jpg)

---


As always, if you found any errors in this post please let me know!