This structure can be used to implement a priorty queue, such as commonly used in Prim's and Djikstra's algorithm.
During the decrease key step of this data structure, nodes are marked if their child is moved. A "soft" data structure with a faster delete than this structure's was developed by Chazelle but relied upon corruption, while other attempts to improve this structure's large time constant resulted in "skew" and "pairing"varieties. A certain potential function associated with this data structure is equal to the number of roots plus twice the number of marked nodes, ensuring descrease-key and a lazy union each run in amortized constant time. The max degree can be bounded by a log base phi of the total number of nodes. This structure can be used to implement a priorty queue, such as commonly used in Prim's and Djikstra's algorithm. FTP, name this data structure developed by Fredman and Tarjan that consists of a forest of heaps whose size satsifies a certain relation named for an Italian mathematician.
During the decrease key step of this data structure, nodes are marked if their child is moved.
{Fibonacci Heap} [prompt on " {heap} " before mention]