Fibonacci heaps - 斐波那契堆
http://www.keithschwarz.com/interesting/code/?dir=fibonacci-heap
This allows algorithms that rely heavily on decrease-key
* to gain significant performance boosts. For example, Dijkstra's algorithm
* for single-source shortest paths can be shown to run in O(m + n lg n) using
* a Fibonacci heap, compared to O(m lg n) using a standard binary or binomial
* heap.
*
* Internally, a Fibonacci heap is represented as a circular, doubly-linked
* list of trees obeying the min-heap property. Each node stores pointers
* to its parent (if any) and some arbitrary child. Additionally, every
* node stores its degree (the number of children it has) and whether it
* is a "marked" node. Finally, each Fibonacci heap stores a pointer to
* the tree with the minimum value.
*
* To insert a node into a Fibonacci heap, a singleton tree is created and
* merged into the rest of the trees. The merge operation works by simply
* splicing together the doubly-linked lists of the two trees, then updating
* the min pointer to be the smaller of the minima of the two heaps. Peeking
* at the smallest element can therefore be accomplished by just looking at
* the min element. All of these operations complete in O(1) time.
http://blog.pengyifan.com/a-java-implementation-of-fibonacci-heep/
http://www.sanfoundry.com/java-program-implement-fibonacci-heap/
FibonacciHeap.java
CHAPTER 21: FIBONACCI HEAPS
https://en.wikipedia.org/wiki/Fibonacci_heap
http://nlfiedler.github.io/2008/05/31/analysis-of-java-implementations-of-fibonacci-heap.html
斐波那契堆同二项堆一样,也是一种可合并堆。斐波那契堆的优势是：不涉及删除元素的操作仅需要O（1）的平摊运行时间。和二项堆一样，斐波那契堆由一组树构成。这种堆松散地基于二项堆，说松散是因为：如果不对斐波那契堆做任何DECREASE-KEY 或 DELETE 操作，则堆中每棵树就和二项树一样；但是如果执行这两种操作，在一些状态下必须要破坏二项树的特征，比如DECREASE-KEY或DELETE 后，有的树高为k，但是结点个数却少于2k。这种情况下，堆中的树不是二项树。
与二项堆相比，斐波那契堆同样是由一组最小堆有序树构成，但是斐波那契堆中的树都是有根而无序的，也就是说，单独的树满足最小堆特性，但是堆内树与树之间是无序的，如下图。
对于斐波那契堆上的各种可合并操作，关键思想是尽可能久地将工作推后。例如，当向斐波那契堆中插入新结点或合并两个斐波那契堆时，并不去合并树，而是将这个工作留给EXTRACT-MIN操作。
http://www.keithschwarz.com/interesting/code/?dir=fibonacci-heap
This allows algorithms that rely heavily on decrease-key
* to gain significant performance boosts. For example, Dijkstra's algorithm
* for single-source shortest paths can be shown to run in O(m + n lg n) using
* a Fibonacci heap, compared to O(m lg n) using a standard binary or binomial
* heap.
*
* Internally, a Fibonacci heap is represented as a circular, doubly-linked
* list of trees obeying the min-heap property. Each node stores pointers
* to its parent (if any) and some arbitrary child. Additionally, every
* node stores its degree (the number of children it has) and whether it
* is a "marked" node. Finally, each Fibonacci heap stores a pointer to
* the tree with the minimum value.
*
* To insert a node into a Fibonacci heap, a singleton tree is created and
* merged into the rest of the trees. The merge operation works by simply
* splicing together the doubly-linked lists of the two trees, then updating
* the min pointer to be the smaller of the minima of the two heaps. Peeking
* at the smallest element can therefore be accomplished by just looking at
* the min element. All of these operations complete in O(1) time.
http://blog.pengyifan.com/a-java-implementation-of-fibonacci-heep/
Operations | Linked List | Fibonacci Heap ------------------------------------------- insert | O(1) | O(1) minimum | O(n) | O(1) extractMin | O(n) | O(log n) union | O(1) | O(1) ------------------------------------------- decreaseKey | O(1) | O(l)* delete | O(1) | O(log n)*
- extractMin() deletes the node with minimum key from the heap.
- union(H) merge heap H and create a new one.
- decreaseKey(x,k) assigns to node x within the heap the new key value k, which is assumed to be no greater than its current key value.
- delete(x) deletes node x from the heap.
http://www.sanfoundry.com/java-program-implement-fibonacci-heap/
FibonacciHeap.java
CHAPTER 21: FIBONACCI HEAPS
https://en.wikipedia.org/wiki/Fibonacci_heap
http://nlfiedler.github.io/2008/05/31/analysis-of-java-implementations-of-fibonacci-heap.html
Please read full article from Fibonacci heaps - 斐波那契堆
